Optimal variable sizes in the Secure Remote Password protocol

Question

I am implementing the Secure Remote Password protocol:

  U = <username>              -->
                                 <--    s = <salt from passwd file>
  a = random()
  A = g^a % N                 -->
                                     v = <stored password verifier>
                                     b = random()
                              <--    B = (v + g^b) % N
  p = <raw password>
  x = SHA(s | SHA(U | ":" | p))

  S = (B - g^x) ^ (a + u * x) % N    S = (A * v^u) ^ b % N
  K = SHA_Interleave(S)              K = SHA_Interleave(S)

What size of numbers should I be setting for all the variables? RFC 2945 recommended that u be 32-bit but no lower. N is 4096-bit, g = 2.

My aim is to maximize security without any unnecessary expense. How big should s, a, b and u be? Last but not least, what is the optimal length for the session key K, which will be used by an AES cipher?

Edit: SHA_Interleave(S) returns the SHA hash of every other byte concatenated with the SHA hash of the remaining bytes, thus doubling the length pf the result. Would SHA256 suffice? What size key am I after for AES?

Answer 1

RFC 5054 has a bit more precise recommendations. To be coherent, one must try to achieve a given "security goal" expressed in bits as a parameter t: namely, that the system is secure against attacks which have a computing power up to 2^t elementary operations. The traditional value for t was 80 bits, but advances in technology make available computing power uncomfortably close to that limit. Since cryptographers just love powers of 2, it is now customary to use 128 bits as security goal. Even with an over-optimistic estimate of how long Moore's law will keep on and what it means, 128 bits are still safe for at least the next 40 or 50 years, and beyond that predictions are rather meaningless.

To get t bits of security, you should have the following:

• The Diffie-Hellman private elements (here a and b) should have size at least 2t bits (hence 256 bits -- that's what RFC 5054 recommends, by the way).

• The involved hash functions should have output size at least 2t bits in all generality, also shorter output size are tolerable in many cases (2t bits of output are about having 2^t resistance to collisions, but in many cases collisions are not an issue, we just want 2^t resistance to preimages, and for that t output bits suffice).

• Symmetric encryption keys and MAC keys should have length at least t bits (and AES can work with 128-bit keys).

• Ideally, salts should have length 2t bits so that risks of having a collision (two identical salts for distinct users) are lower than 2^-t, but you can have shorter salts because the server can control how many users it may have, and it will certainly be much slower than 2¹²⁸ (here, we are talking about the computing power of the server, not the computing power of the attacker).

• The value u, as an online challenge, should have length t bits, but there again, a shorter value is perfectly tolerable because the size of u can be exploited only in online attacks: with a 32-bit u, an attacker has a 1 in 4 billions chance of pulling off an impersonating attack, but every failure is visible to the client and server. There again, the server will have some trouble serving billions of requests in a short time, and will certainly not do it discretely. Also, the attacker could also try to guess the password itself, under the same online-check conditions, so it is rather meaningless to have a u longer than the expected average password entropy -- and 32 bits of password entropy are already an optimistic figure.

• n (the prime number) should be large enough that discrete logarithm modulo n has difficult at least 2^t. Such "difficulty" is hard to estimate since it works on costs which are of distinct nature than what is used to, e.g., break symmetric encryption. Nevertheless, there are tentatives. 4096 bits are quite an overkill; I would personally be quite happy with 2048 bits.

SRP results in a shared secret value S, which is then extended into symmetric key material through a Key Derivation Function. SHA_Interleave() is a proposal for such a KDF. In RFC 5054, the KDF defined in TLS is used instead (under the name "pseudorandom function"). For proper data tunneling, you will want four 128-bit symmetric keys: an encryption key and an integrity check key in both directions. If you use a combined encryption-and-integrity mode, then you only need two 128-bit symmetric keys (one in each direction).

This really looks like you are reinventing TLS with SRP, something which is hard to get right at so many levels that you really should use the genuine TLS instead.