Security of SRP-6a against impersonating server choosing small/wrong N

Question

I'm looking at an implementation of SRP (Secure Remote Password) that essentially follows the Stanford documentation (http://srp.stanford.edu/design.html). I'm worried about one aspect though: In the initial message exchange the server sends the parameters to be used (modulus $N$, generator $g$, salt $s$) to the client after potentially looking up these parameters per user.

A correct server would choose $N$ as a large safe prime and $g$ as a generator. Under these circumstances I can see why the further protocol will give no information to try more than one password per protocol execution to a) a passive attacker, b) a man-in-the-middle attacker, or c) an active attacker that impersonates a server but doesn't have a copy of the server's database of password verifier values (otherwise a brute-force attack is trivial).

However, given that the attacker is not likely to play by our rules, what would happen if an attacker that impersonates a server (but doesn't know the password verifier stored in the server database) choose bad values for $N$ and $g$?

These could be

• small $N$
• composite $N$
• non-safe prime $N$
• generator $g$ of a small subgroup in composite or non-prime $N$

Wouldn't the attacker in the server's position then be able to brute-force the discrete logarithm and learn the password-equivalent secret $x$ modulo their chosen small $N$ or in a small subgroup?

Answer 1

I don't see how the server can directly learn $x$; what a server would be able to is perform a single exchange with the client (recording the initial parts of the protocol), and then go through a dictionary, and test various passwords (that is, various possible $x$ values), and realize when he finds the right one.

The idea here would be to select a prime value $N$ where $N-1$ is smooth (that is, a product of small factors); this makes solving the discrete log problem modulo $N$ easy.

With that, when the client sends $g^a$ as its initial exchange, the server can immediately recover $a$. It then sends back random values for $B$ and $s$. The client then sends its verifier $H[H(N) \oplus H(g) | H(I) | s | A | B | K_{Client}]$.

After that, it's easy; if the server has a guess for the password, it can compute the corresponding $x$ value, and then the shared key that the client computes; $K_{Client}=H( (B − kg^x)^{a + ux} )$; where $B, k, g, a, u$ are known values, and $x$ depends only on the password. Then, we can go back to the verifier and recompute it based on the possible $K_{Client}$ value (as $K_{Client}$ is the only value that the server does not know; if the computed value matches the value that the client sent, then we have correctly guessed the password (or we found a collision in the hash function).

This isn't likely the only game we could play with a malformed group; it is likely to be the most serious.

The moral of this story: either the client must verify that the group proposed by the server is secure (both $N$ and $(N-1)/2$ are prime; $g$ is a generator, that is, $g^{(N-1)/2} = -1$ and $g \ne -1$); or the client needs not to work with arbitrary $N$, $g$ values, but instead only with preconfigured ones that it knows are secure.