# How realistic is a dictionary attack on a secure remote password protocol (SRP) verifier?

I'm deploying a secure remote password protocol implementation and I'm wondering what the consequences are when the client generated verifier gets leaked to an attacker. I've read Thomas Wu's paper and as nice as it is, it doesn't talk about that scenario. I also read RFC 5054 and it has the assertion:

If an attacker learns a user's SRP verifier (e.g., by gaining access to a server's password file), the attacker can masquerade as the real server to that user, and can also attempt a dictionary attack to recover that user's password.

If the client is using the verifier as assurance of the server's identity, I can see how that would go badly. It's the second assertion of a dictionary attack that makes me wonder.

x = H(s, P)
v = g^x mod n


How much effort would it take to solve for P without knowing x? It seems like the implied mod of n totally obscures x. And then, there should be many values of P that could generate a v, but a much smaller set that would pass the verification stage.

And if a dictionary attack could find the password, how is this better than a shared secret protocol? Is the dictionary attack mentioned in the RFC just saying "if I had an infinite speed computer I could really ruin your day?" Or does it mean it could run a dictionary attack on the client while pretending to be the server?

-

The security goal behind SRP is that an attacker that could either pretend to be a client (and attempt to log into a server that knows the key), pretend to be a server (and allow clients that know the key to attempt to log in), or actively monitor (and modify) the communications between a valid client and a valid server, would learn nothing from an exchange, except possibly whether a single password is valid or not. This last bit cannot be helped with a password-based authentication method, as the attacker could always take his guess at the password, and then proceed with the protocol with a valid server or client, and see if it succeeds. The point of SRP is that the attacker can't do any better than that.

Now, in the protocol, the value v is never sent over the wire, and so the attacker does not see it, and so a dictionary attack against that value is impossible (unless the attacker can rederive that value somehow, which is not believed to be possible).

On the other hand, the note you highlighted assumes that the attacker can do more than just work with the protocol; it assumes that he is also able to access the password files on the server. If he can do that, well, yes, he knows enough to impersonate a server, and he can also perform a dictionary attack on the password; namely for each password P' in his dictionary, he computes:

x' = H(s, P')
v' = g^x'


and check if v == v' (note: it is quite unlikely that you could stumble on a different password that also passes this check)

Note that this is not specific to SRP; for any password-based authentication method, if the attacker can learn everything the server knows, then he can impersonate the server, and in addition, he can perform an undetectable dictionary attack (for example, by simulating a client logging in with various passwords; this is undetectable because since this occurs entirely on the attackers equipment, you aren't informed that someone that someone is trying to log into the system with a long series of passwords).

As for why this is better than a shared secret protocol, well, an attacker can run a dictionary attack even if he didn't have direct access to the server's password files; with SRP, that sort of access is needed.

-
I added the implied modulus of n to the calculation of v. I think that makes the set of v < set of x. I don't understand the verification formula well enough to know that (B - g^x')^(a + ux') = (A · v^u)^b for all values of v = g^x' mod n. If it is for any values of where x != x' then isn't this just a fancy shared secret? –  Grant BlahaErath Mar 21 '12 at 5:21
@GrantBlahaErath: Well, because g is a generator of the entire group (that's one of the requirements of SRP), then it turns out the set of v is precisely the set of x; that is, g^x != g^x' (mod n) for any x != x' (mod n-1). In any case, attackers normally don't have direct access to either x, v, or the common value; hence they can't use these formulas directly in a dictionary attack (like they can with straight-forward shared secret models). –  poncho Mar 21 '12 at 13:39
@GrantBlahaErath The server (or anyone who compromised the server) has access to v (and s), which allows a dictionary attack to find P. But a direct deriving of v → x → P is impossible if the group has a hard discrete logarithm problem (for v → x) or the hash function is preimage-resistant (for x → P). –  Paŭlo Ebermann Mar 21 '12 at 20:28
Thanks both of you, that makes a lot more sense. Practically speaking, if the verifiers are obtained by the attacker, its only a matter of computation before the attacker discovers the original password. However, it would be more computation than recovering a table of crypto hashed passwords. –  Grant BlahaErath Mar 21 '12 at 22:00