Does impersonating an SRP server give you enough information for an off-line dictionary attack?

Question

In a comment to an answer I wrote to another question, CodesInChaos wrote that:

"Problem with SRP is that an attacker who impersonates a server learns the password hash, enabling offline search."

and further that:

"If the server successfully impersonates a legitimate server [...] they learn the public key of the client. Knowing the public key allows a password guessing attack, which is only partially mitigated by using a good password hash."

This initially surprised me, since I'd somehow assumed that SRP was designed to avoid this kind of attack scenarios. However, upon a closer review of the SRP design specifications, it does seem to me that this attack does work, and in fact seems unavoidable given the SRP design.

The point is that, to complete the authentication process, the client and the server must prove to each other that their keys match. In SRP, the client is the first to send its proof (and the SRP design spec insists on this; I'm not sure what attack would be enabled if this were not done, but I assume there must be one, or the spec wouldn't be so explicit about it). But this proof value must be something both the client and the (legitimate) server can compute, and thus it must be entirely determined by:

• values chosen by the client and sent to the server during the authentication process,
• values chosen by the server and sent to the client during the authentication process, and
• the password and/or the verifier (which itself is determined by the password).

Thus, having received the client's proof, an attacker spoofing the server can now try to guess different passwords, keeping the other values the same, and see which password yields the same proof.

A technical detail to note here is that, in earlier phases of the SRP authentication process, the server is supposed to provide the client with the salt $s$ and public ephemeral value $B = kv + g^b$, which depends on the verifier $v$.

The first is not actually an issue for an impostor, since not only does SRP assume that the client won't verify the salt supplied by the server, but even if it does, obtaining the correct salt from the real server requires no authentication. The second looks like it could be an issue, but as far as I can tell, it actually isn't: since the server never needs to (and indeed must not) divulge either $b$ or $g^b$ to the client, the impostor is can just pick any $B$ value they want without the client having any way to verify it.

---

Now, so far, everything looks clear. But what's confusing me is the section "Computation of $B$" from the original SRP-3 paper (Wu, 1998), which, in explaining why $B$ is not computed simply as $B = g^b$, first describes what looks like exactly the attack outlined above and then goes on to say:

"Since this attack comes from an impostor who does not know $v$ (anyone who does know $v$ can already perform a dictionary attack), one way to thwart it is to force the host to commit to its value of $v$ in Step 4. [...]

"Modular addition appears to be the simplest operation that leaks no information about $v$ while at the same time enabling SRP to resist a dictionary attack by a fake host."

What I don't see is how including $v$ in the computation of $B$ would actually "force the host to commit to its value of $v$", since there's no way the client can actually verify that $B$ was computed in the specified manner. Or maybe there is, and I'm just missing something?

So is the argument given by Wu in that section just complete nonsense, or is there actually something to it? And if there isn't, is there any reason why the verifier $v$ should be included in the calculation of $B$ in SRP? And, most of all, is SRP actually resistant to dictionary attacks by fake hosts, as the 1998 paper seems to claim, or isn't it?

Answer 1

Suppose the server did not include $v$ in the computation of $B$. In such case the following events have happened:

1. The server has sent a salt value $s$ to the client. We might assume it is authentic (because it is easy for the fake server to get it from the real server). The client re-calculates its long term private key $x$ such that $v = g^x$.
2. The client has generated a fresh random ephemeral key pair $A = g^a$ and sent $A$ to the server.
3. The server generates a random $u$ and a random $B$ and sends them to the client. The server might, or might not, know the value $b' = log_g(B)$.
4. The client calculates $S = (B-g^x)^{a+xu}$ and sends a proof of $S$ to the server.

Let's assume the fake server aborts the protocol at this point and attempts to mount an offline dictionary attack on the client password, in order to find the $x$ value.

Now, the problem is that the server is supposed to calculate $S = (Av^u)^b$, but that would require, for each guess at $x$, finding a value $b$ such that $g^b = B - g^x$. The "SRP assumption", if there is one, is that this is as hard the discrete log problem.

Conversely, should the fake server instead try to simulate the client calculation of $S$, it would require also guessing the ephemeral client private key $a$.

Is there any way around this? Yes, there is, but it requires that the server sends $B = 0$ and the client doesn't check for this. If $B = 0$, then we might infer that $b = x + (p - 1)/2$ (where $p$ is the prime field modulus). In such case $B = g^x + g^xg^{(p-1)/2} = g^x + g^x(-1)$, provided that $g$ is a generator of $\mathbb Z^*_p$. The offline calculation of the fake server, in such case, collapses to $S = (Ag^{ux})^{x + (p - 1)/2}$. This has only one unknown.

---

Edit: It might be noted, with regard to the "SRP assumption", when e.g. $g = 2$ there are couple of special cases when the assumption is false. For instance, for arbitrary values $z$, ${2}^{z+1} = {2}^z + {2}^z$ and ${2}^z = {2}^{z+1} + 2^{z+(p-1)/2} \pmod p$.

As far as I can tell, all this means, is that if the server sends $B = 2v$ or $B = p-v$, it means that the server already knows both $v$ and $x$ and has selected $b = x$ or $b = x + (p-1)/2 + 1$ respectively. Hence, the server commits to $v$, but fails to hide it, or, alternatively, the server actually commits to $x$.

Answer 2

But this proof value must be something both the client and the (legitimate) server can compute, and thus it must be entirely determined by:

• values chosen by the client and sent to the server during the authentication process,
• values chosen by the server and sent to the client during the authentication process, and
• the password and/or the verifier (which itself is determined by the password).

Maybe I'm reading the spec or your question wrong, but I think there is one value that is known by the client but not the server: $a$ The server only knows $A$, which is computed by $g^a$

I don't know if that protects against the attack you're talking about.