Using Secure Remote Password without embedding the modulus

Question

The SRP protocol as described by the author assumes that the large safe prime modulus and generator are embedded into the client and server rather than being transmitted as part of the protocol. However, the author suggests in this section that the protocol can be modified to allow the modulus and generator to be chosen by the server and transmitted as part of the protocol rather than embedding them in the implementation. I would prefer that for several reasons.

So what's confusing me is that the server is supposed to store the client's password ahead of time in the form g^H(s, P) mod n, where g and n are the generator and modulus, H is a cryptographic hash, s is a salt (also kept by the server) and P is the plaintext password. Now in the security analysis section there is a reason given that g^H(s, P) mod n is stored rather than simply H(s, P), so that stolen database entries cannot be used. x = H(s, P) is seen as the client's private key. So if g and n can change from session to session, how can this possibly work without the server directly storing x?

Answer 1

You may want to use RFC 2945 and 5054 (description of SRP, and of how to use SRP with TLS, respectively); they are a bit more "down to the wire" than the mathematical description from the author.

When the SRP author states that the server may choose the prime n and send it to the client, he does not mean that the server may choose a new prime n for every session; the same n must be used when the user password is first chosen (and v stored by the server) and when a key is exchanged. What the SRP author means is that an authentication session can begin by the server sending a n-value to the client and telling it "we shall use this n, which is the n which we used when the password was chosen". The client needs not be sure, security-wise, that this is indeed the same n, and not another n crafted by a fake server. In that sense, the value of n needs not be hardcoded in the client.

However, if the client needs not check that the value of n is the same than used beforehand (it will have to be the same for the protocol to succeed, but a distinct n sent by a fake server will not endanger the password confidentiality), the client must still make sure that n is proper, which implies, at least, to check that n and (n-1)/2 are prime. See for instance section 3.2 of RFC 5054. The bottom-line is that, for an efficient use of SRP, you really want to use a few hardcoded n values, which both client and server know.

Possibly, you could precompute 3 or 4 sets of parameters (values of n of distinct sizes, for paranoia/efficiency trade-offs), that the server stores, and in the client you store only the hashes of those values; when a password needs to be exchanged, the server sends n and the client verifies that its hash matches one of its hardcoded hash values. Alternatively, have both client and server store the values of n, and simply use short identifiers so that both client and server use the same value. Note that if the value of n depends on the user (a given server using several values of n concurrently, and must send the "right one" for a given user), then the protocol must arrange for the user to first state his name; this is the point of the "srp" TLS extension (section 2.8.1 of RFC 5054).

You cannot have the server change n for a given user after password choice, unless the server stores the password-equivalent value x = H(s, P), and SRP was designed precisely to avoid such storage.

Note that there is no security issue whatsoever of having several distinct users on a given server or distinct servers use the same n. A single n can be fit for the whole world. RFC 5054 (appendix A) lists a few n of sizes 1024 to 8192 bits.