2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Ahh, thanks, you've solved the confusion in my head. I was thinking of an attack I saw presented somewhere (don't remember) where the attacker progressed by guessing $x$ mod 17, then $x$ mod 257, etc. and in each step only having to try a couple of additional bits due to knowledge from the previous exchange. I now see that that doesn't apply here, in part due to the many hashes. And yes, just breaking $a$ and doing a direct brute force on the password is plenty sufficient and an even worse attack, since, among other things, SRP is supposed to be used when the password entropy is low. $\endgroup$ – Henryk Plötz Oct 8 '15 at 19:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.