Code Poetry
and Text Adventures

by catid posted (>30 days ago) 6:55pm Sat. Jan 4th 2014 PST
The Tabby project (http://github.com/catid/tabby) is going great so far.  It seems to provide optimal PKI handshakes.

The next obvious step is password authentication.  If I'm going to unseat SRP6a from its throne there needs to be a pretty good argument in favor of its successor.

The disadvantages of SRP6a right now are:

+ Lack of integration with PKI.
+ Slow performance: 256-bit exponentiation without any useful tricks to speed it up and a 3072-bit modulus.  And multiple exponentiations required per protocol run.
+ No deniability.  The user's name is sent in the clear if it's not embedded inside of a secure tunnel, so he cannot later deny that he attempted to log in.

Now I'll introduce a more obscure protocol that can be written using elliptic curve math: SPAKE2+ by Dan Boneh, which is in turn based on SPAKE2 described thoroughly in Abdalla's thesis (http://www.di.ens.fr/~mabdalla/papers/hdrthesis.pdf).  These schemes have security proofs, which make them great starting points.

Choose U,V random public points.  No one knows the corresponding private keys.

Client generates password:
pw = "username : realm : password"
salt = 64-bit nonce
pi = scrypt(pw, salt)
pi_0 = H(pi, "server")
pi_1 = H(pi, "client")
L = pi_1*G

To create an account, the client sends "username, salt, pi_0, L" to the server.

Server Database contains:
username [variable length]
salt [8 bytes]
server verifier: pi_0 [32 bytes]
client verifier: L [64 bytes]

Now a client wants to connect to the server.

Client transmits:
c2s username

Server transmits:
s2c salt

Client Online Processing:
pw = "username : realm : password"
pi = scrypt(pw, salt)
pi_0 = H(pi, "server")
pi_1 = H(pi, "client")
Choose x = [1, q-1]
X = xG
X' = X + pi_0*U

Client transmits:
c2s X'

Server Online Processing:
Choose y = [1, q-1]
Y = yG
Lookup database entry for username, recovering "salt, pi_0, L".
N = yL
X = X' - pi_0*U
Z = yX
h = H(pi_0, X, Y, Z, N)
Y' = Y + pi_0*V

Server transmits:
s2c Y', H(h)

Client Online Processing:
Y = Y' - pi_0*V
N = pi_1*Y
Z = xY
h = H(pi_0, X, Y, Z, N)
Verify H(h).

Client transmits:
c2s h

Now I'll describe how to integrate this into Tabby, and also optimize it slightly using new math introduced by Elligator (http://elligator.cr.yp.to/elligator-20130828.pdf).

Note that the key insight for SPAKE2+ is that a point can encrypt another point in the EKE style if the private key for one of the points is unknown.  Generating a point deterministically without knowledge of its private key can be accomplished with Elligator.  The pi_0*U and pi_0*V point encryption can be done with Elligator instead, which requires much less computation and closes the U,V backdoor problem mentioned above.

Elligator (or equivalent) is used to decode a random value into a point without knowing the private key for that point w.r.t. the generator point.  This is an improvement on SPAKE2+, because the Elligator decoding speed is faster than a full point operation, while also avoiding the issue with SPAKE2 that all of its security rests on a single Elliptic Curve Discrete Logarithm Problem, instead of a new ECDLP for each instance.

Furthermore, the value of L itself can become the server's identifier, which saves some space on the server and simplifies the protocol because then the client only needs to prove knowledge of the private key of L.  And the server cannot do that without brute-forcing the password, so the augmented property holds.  This is not unusual.  It can be considered another step in the password hashing process and it fits the SPAKE2+ model too.  Also, SRP6a uses a modexp result as its verifier too, so there are lots of good reasons for doing this.

And the server can send an encrypted point challenge when it replies with the salt to save one protocol round.

The result is a protocol that requires fewer operations than SRP6a in the same number of rounds:

Client generates password:
pw = "username : realm : password"
salt = 64-bit nonce
v = scrypt(pw, salt)
V = vG

To create an account, the client sends "username, salt, V" to the server.

Server Database contains:
username [variable length]
salt [8 bytes]
verifier V [64 bytes]

Now a client wants to connect to the server.

Client transmits:
c2s username

Server Online Processing:
Lookup database entry for username, recovering "salt, V".
e = H(username, salt, V)
E = Elligator(e)
Choose random x = [1, q-1]
X = xG
X' = X + E

Server transmits:
s2c salt, X'

Client Online Processing:
pw = "username : realm : password"
v = scrypt(pw, salt)
V = vG
e = H(username, salt, V)
E = Elligator(e)
X = X' - E
Choose random y = [1, q-1]
Z = (v + y)X
Y = yG
Y' = Y + E
PROOF = H(E, SP(server's public key), Z)
CPROOF = Low 32 bytes of PROOF.

Client transmits:
c2s Y', CPROOF

Server Online Processing:
Y = Y' - E
Z = x(V + Y)
PROOF = H(E, SP(server's public key), Z)
Verify CPROOF.  Abort if CPROOF does not match low 32 bytes of PROOF.
SPROOF = High 32 bytes of PROOF.

Server transmits:
s2c SPROOF

Client Online Processing:
Verify SPROOF.  Abort if SPROOF does not match high 32 bytes of PROOF.

This protocol requires that the server stores a 64 byte elliptic curve point for verification instead of a 32 byte password hash.  The advantage is that there is no existing brute force tool that can break a password hash protected by elliptic curve math and it further protects the password from weaknesses in the hash function itself.

This requires that the client regenerates V during the protocol.  However, this is offset by the fact that scrypt is used, which is designed to take a long time.  To brute-force the password requires generating V in any place in this protocol, so it can be considered part of the scrypt process, and is essentially free.

Unfortunately I feel this is sufficiently diverged from SPAKE2+ that it is a new protocol and should require a new security proof.

So, did I solve any of the disadvantages of SRP?  Aside from the inefficiencies I noted, It doesn't look like it.  Unless it's embedded into a Tabby session it lacks deniability and PKI integration.  At least since it will be packaged with Tabby it will solve those issues when used in real applications.

There is a flaw in this protocol that leads to an offline dictionary attack from the server's first response of X'.  X is always of order q, but Elligator generates points E of order 4q.  And the sum is sent in the clear.  So for example, if X' = X + E is of order q, then you can eliminate all passwords that do not lead to a point of order q.  Not sure how to fix this exactly.  The Elligator paper appears to recommend selecting the generator point from a random set of 4 points.  Another option I see is to multiply the Elligator output by 4, which guarantees the result is a point of order q.

Another area to pay attention to is how it is incorporated into the Tabby protocol.  I envision it being nested within a PKI-protected authenticated encryption scheme to allow for deniability, so that the client's username is not sent in the clear.  The issue that can happen is that if the server's public key is self-signed, then MitM is possible, and the attacker can relay the password protocol through to the real server to trick the user into thinking the attacker knows the password.  To prevent this, the server's public key makes an appearance in the final Z hash.  If the client is expecting the MitM public key, then the server will not verify correctly.

Sadly, deniability is lost when the server's public key is self-signed because a MitM would be able to watch the exchange up until the final server proof message, which would tell the MitM that the user knows his own password.  So if the server's public key is not known ahead of time, an active attacker can determine if the client owns the account, despite that the client will discover the subterfuge.

EDIT:

There is a flaw in this protocol that defeats the "augmented" property.  Latest Tabby fixes the issue.
last edit by catid edited (>30 days ago) 3:50pm Thu. Jan 16th 2014 PST