Weakness of SRP after server compromise

Question

From SRP section 3:

The host stores user passwords as triplets of the form

{ <username>, <password verifier>, <salt> }

Password entries are generated as follows:

<salt> = random()
x = SHA(<salt> | SHA(<username> | ":" | <raw password>))
<password verifier> = v = g^x % N

Where g and N are agreed upon in advance.

They claim resistance against server compromise, but if an attacker gains access to the password verifier v, how much work is required per guess, to perform an offline brute force dictionary attack?

If I'm not mistaken, the work required for each password guess is two iterations of SHA, and then raising a single large exponent, and computing a single large modulo-division. This is not comparable to pbkdf2, bcrypt, scrypt, or similar, and probably shouldn't be considered a strong enough rate-limiter to protect a low entropy password.

Answer 1

From the Security Considerations -section of the RFC:

Even if the host's password database were publicly revealed, the attacker would still need an expensive dictionary search to obtain any passwords. The exponential computation required to validate a guess in this case is much more time-consuming than the hash currently used by most UNIX systems. Hosts are still advised, though, to try their best to keep their password files secure.

So not much security is claimed in the case of password compromise. A dictionary search is possible, just deemed expensive, which it arguably was back then.

The "hash currently used" presumably means DES-crypt (bcrypt was new and as yet rare), which uses 25 iterations of slightly modified DES with only 56 bits of the password used. You can see how even two iterations of SHA-1 followed by a modular exponentiation could be better.

Answer 2

Although the RFC2945 for SRP specifies SHA1 explicitly, and allows you to choose values for your g and N, I looked through the BouncyCastle implementation of SRP6, and it allows you to specify your digest, and they provide standard group parameters. So, I used Sha256Digest and ran some benchmarks of Srp6StandardGroups.rfc5054_3072 and Srp6StandardGroups.rfc5054_2048.

I generated a verifier for a known password, and then scripted a brute force attack against that password, which will invariably find the right password after 100 incorrect guesses. One time, I used the debugger to step through the code, to confirm exactly which operations it's doing. I confirmed that the work per guess is two iterations of the digest function, and then a call to BigInteger.ModPow(), which calls ModPowBarrett() or ModPowMonty(), which I assume to be performance optimized implementations of simultaneously raising to a power and getting modulus of big integers.

In windows .NET, on my i7 processor, I measured about 13ms per guess with the 2048 group, and 30ms per guess with the 3072 group. I don't know if other libraries would outperform BouncyCastle, and I don't know how much acceleration could be gained with specialized hardware (GPU, etc).

I then repeated the test, but instead of giving the password and guesses directly to SRP, I used Rfc2898DeriveBytes() with 10,000 iterations to get pbkdf2 of each password before generating its verifier. This brought the cost up: around 80ms spent on pbkdf2, and 30ms on verification, for each guess in the 3072 group. The same code (in fact the same binaries) perform a little worse on mono (literally on the same system, on the same i7 processor). In mono, the above configuration gave me around 84ms spent on pbkdf2, and 77ms spent on verification, per guess.