# Weakness of SRP after server compromise

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()
<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.

• IIRC SRP doesn't mandate HMAC (although most standards do), but uses some PBKDF (which is defined by a function accepting a password and a salt). – SEJPM Oct 11 '15 at 18:09
• @SEJPM : $\:$ I don't see any mention of HMAC in the question. $\;\;\;\;$ – user991 Oct 11 '15 at 18:15
• @RickyDemer, well, yes. I called the nested hashes "HMAC" although they aren't, but rather some more custom version. It looks like an adapted version of NMAC. But my comment still holds (= standard mandate something similar as described here, which could be called "garbage" for password hashing) – SEJPM Oct 11 '15 at 18:50
• The RFC specifically says SHA means SHA1, 160 bit. – Edward Ned Harvey Oct 11 '15 at 18:54
• How much work is required to break this? Marginally more (2x) than required to break simple SHA+salt passwords, meaning you can do at least 30 billion guesses per second. (probably more) – SEJPM Oct 11 '15 at 20:34

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.

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.

• A captured verifier is pretty lethal for low entropy passwords. Thinbus JavaScript SRP with SHA256 + Nimbus Java SRP on the server is fast enough for web browser usage (see online demos) and in use by a major online retailer in Europe. Using a not-so-powerful client like a browser javascript engine means that a little stretching of the raw password (a trivial enhancement) isn't going to beat GPU or FPGA accelerated cracking array doing an offline dictionary attacks on a captured verifier. Thats an arms race you loose. Encrypted the verifier in the DB with AES to protect off-host backups. – simbo1905 Nov 4 '15 at 21:58
• Intel provide hardware accelerated SHA1 and SHA256 instruction sets see software.intel.com/en-us/articles/intel-sha-extensions – simbo1905 Nov 4 '15 at 22:33
• hashcat.net/oclhashcat claims SHA256 on GPU of 4,976,000,000 hashes per second on standard PC graphics card hardware. – simbo1905 Nov 4 '15 at 22:35