How secure is the SRP that Blizzard uses to protect passwords?

Question

Blizzard very recently announced that their network was compromised, but they assure users in their statement that the password information that the attackers had access to was saved in a secure way:

We also know that cryptographically scrambled versions of Battle.net passwords (not actual passwords) for players on North American servers were taken. We use Secure Remote Password protocol (SRP) to protect these passwords, which is designed to make it extremely difficult to extract the actual password, and also means that each password would have to be deciphered individually.

I looked up SRP, and it seems to be a method of exchanging passwords securely. I'm familiar with using hashes to store passwords, but I couldn't find out how the SRP Blizzard uses compares to other common methods of hashing passwords like PKBDF2, bcrypt or scrypt?

How hard would it be to bruteforce (or use a dictionary attack) against passwords protected by SRP?

Answer 1

SRP is designed to protect the transmission of the password against brute-force attacks, even in case the password could be easily bruteforced.

However, if some Blizzard authentication server was compromised, the relevant attack vectors are different. Apart from the storage-scheme, the adversary can also listen in to ongoing transactions and, in parallel, store the temporary DH secrets generated by the SRP servers. The latter attack is a bit complicated and requires extensive preparation by the attackers, however, it would surely leak any logins used to authenticate to the compromised system.

The more traditional attack vector is the verification values. In SRP, the verifier values on the server side are not traditional hashes but results of an exponentiation, like in Diffie-Hellman.

To my knowledge there is no detailed analysis of SRP vs. PBKDF2 or bcrypt. Somewhere on the SRP site (srp.stanford.edu) I once saw a note that people implemented a bruteforcer and found the required bruteforcing effort to be similar to traditional bruteforcing of hashes.

This is kind of expected: It is known that such exponentiations are hard to invert, just like a hash function. Assuming Blizzard implemented a standardized protocol like RFC2945 and did not try to invent the details on their own, these verification values will also contain a salt to make rainbow-tables impractical.

The main difference then is in the effort of bruteforcing individual verification values. Here, systems like bcrypt/PBKDF2 employ a scaling factor to increase the computational effort per password guess. The SRP schemes I know do not explicitly support this. Exponentiation is typically a bit more costly to compute than a hash, but this depends on the group (modulus) in which you're operating. I think increasing the modulus of the verification value in SRP is easily possible, but it will also increase the computation effort for 2 other exponentiations per peer that have to be done in every protocol run.

Update: Looking at RFC2945 once more, the password and salt is first hashed and then exponentiated. It would be easy to use PBKDF2 here instead of just hashing to implement a scaling factor for the bruteforcing effort without much impacting the rest of the protocol. Additionally, even when a small/unsuitable exponent N was chosen, the scheme is still as secure as a simple challenge-response-based pw-authentication.

Overall, Blizzard is probably a bit lucky as their kind of pw-storage is very uncommon and appropriate bruteforcers are not commonly available. However, for a determined attacker the SRP way of storing secrets is no more secure (possibly slightly less secure) than the state-of-the-art approach with a decent anti-bruteforce scaling factor. That being said, I applaud Blizzard for using some state-of-the-art crypto for their password-authentication, since online-bruteforcing is typically much more problematic.

Answer 2

You might find this informative: http://www.opine.me/blizzards-battle-net-hack/

In short, Blizzard's implementation of SRP uses SHA1 as the hash, and there is also a modexp operation, which is the 'slow' part. Extrapolating from an Intel whitepaper, a 256-bit modexp would run at about 400,000 ops / sec on an i7-2600. Based on actual testing with a c1.xlarge instance on EC2 ($0.66/hr) you can check about 100 billion passwords for $100.

Since passwords are salted, each password must be attacked individually. So you can test the top 1,000,000 passwords in a dictionary against 100,000 users for $100 if the modulus is 256-bit. A 1024-bit modulus increases the cost by 64x.

EDIT - Apparently, it may be possible to reduce the complexity of an attack down to nothing more than salted SHA1: http://www.opine.me/srp-to-sha1/. This does not apply to a 1024-bit modulus (as it used in Battle.net v2).

Answer 3

SRP is a PAKE protocol. It is totally separate from the hash used. SRP uses a hash function as a cryptographic primitive. A real hash must be used , for example PBKDF2 or bcrypt, to implement this primitive as no perfect hash function is known. As the password is always hashed and salted in both transit and storage, this being a requirement of SRP, the weakest element is the hashed salted password. This obviously assumes that there are no flaws in the protocol itself, i.e. bad choice of primes, random numbers or a pass-the-hash attack.

Answer 4

For Warcraft 3, the first Blizzard game introduced SRP (older games used challenge-responce), it's not secure at all - you only have to find discrete logarith in 256 bit prime field to get password hash x, which is then enough to log in, or you can use it to bruteforce passwords with high speed.

The fundamental question remained, is this a practical attack vector, and how bad is it really? Algorithms which can efficiently perform discrete logarithms on large values are a subject of significant research, however, there aren’t exactly ‘script kiddie’ tools readily available to perform the computation. GDLOG is ‘an open source implementation of the General Number Field Sieve algorithm for discrete logarithm problem’. It’s actually overkill to use GNFS to compute the discrete log of a 256-bit number, and it took Sam only two hours on a single machine to complete the initial precomputation. At that point, individual discrete logs which recover x from v take variable time, “ranging from 15 seconds to several minutes depending on our luck.” Sam noted that there is significant potential to improve the performance here.

For Battle.Net 2.0 games like WOW and SC2, 1024 bit prime is used, discrete logarithm for that size should be unsolvable now, but bruteforce is still possible. Remember that hashes and verifiers are salted.