13

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?

Mad Scientist
  • 791
  • 5
  • 18
  • According to this, they're using something loosely resembling an HMAC with SHA1: http://us.battle.net/d3/en/forum/topic/6307741150 . It is probably much easier to brute force than if they'd used HMAC with scrypt or bcrypt. (Using SRP is nice, though.) – Kevin Cantu Aug 10 '12 at 17:36
  • Related: [What steps can you take to make offline cracking of srp harder?](http://security.stackexchange.com/q/18844) – Gilles 'SO- stop being evil' Aug 18 '12 at 10:40

4 Answers4

11

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.

Bruno Rohée
  • 5,221
  • 28
  • 39
pepe
  • 3,536
  • 14
  • 14
  • Somebody should point out that if one of the attack vectors is basically to "listen" in on the ongoing transaction then Blizzard has a bigger problem then a secured form of our passwords being leaked, of course this is very unlikely, it also would mean that an attacker could listen no matter what method was used to secure the password. – Ramhound Aug 10 '12 at 11:57
  • This article makes for interesting reading: http://opine.me/blizzards-battle-net-hack/ – Polynomial Aug 10 '12 at 12:05
  • 1
    @Ramhound: Typically, the credential used to perform more and other transactions is considered more critical than the transaction itself. – pepe Aug 10 '12 at 12:47
  • @Polynomial: The article seems a little biased to me. How many compromises do we know of where some DB was actually created using bcrypt-like technology with decent scaling factor? Doing this is probably also makes regular authentication quite expensive for large-scale providers. The only (conservative) way around this are HSMs, but they are either very expensive or very slow. – pepe Aug 10 '12 at 12:55
  • @pepe Expensive, of what order? Hundred, thousands of dollars? – curiousguy Aug 13 '12 at 18:02
  • pepe: John the Ripper now includes support for Blizzards version of SRP :-). @curiousguy: Generally in the five-figure range. Also most HSMs are intended for secure key storage and are pretty slow. You can get crypto accelerators from companies like Cavium, but they're also pretty expensive, you'd need to do custom programming to use them against SRP, and they're designed to speed up particular protocols like TLS and IPsec, so if you're not wanting to do offload of those then things get a lot less fun. – Dave Aug 16 '12 at 04:54
5

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

JeremyS
  • 81
  • 2
1

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.

forest
  • 64,616
  • 20
  • 206
  • 257
jhoyla
  • 439
  • 2
  • 6
0

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.

Smit Johnth
  • 1,709
  • 4
  • 17
  • 23
  • According to another answer they use single iteration SHA-1. That's a really bad choice for password hashing, even with a salt. Any sane SRP implementation needs a password hash like PBKDF2 or scrypt. – CodesInChaos May 22 '13 at 21:14
  • @CodesInChaos that doesn't really matter in case of SRP - if you'll find discrete logarithm and find the password hash, you don't need the password anymore, you can use the hash to log in. If you can't find it, you have to calculate modpow() for each password and verifier which is slow enough. – Smit Johnth May 22 '13 at 22:05
  • One modpow per password isn't that expensive with a fixed base. Certainly not comparable to scrypt with a decent work factor. – CodesInChaos Aug 15 '13 at 12:19
  • @CodesInChaos is there a difference if the base is fixed? – Smit Johnth Nov 26 '13 at 07:55
  • With fixed base you can do some pre-computations which speed up the computation a bit. – CodesInChaos Nov 26 '13 at 08:36
  • @CodesInChaos interesting, can you explain it? – Smit Johnth Nov 26 '13 at 15:21
  • One article about pre-computations to accelerate fixed base ECC: [Faster curve25519 with precomputation](https://www.imperialviolet.org/2013/05/10/fastercurve25519.html). Similar techniques apply to fixed base exponentiation in finite fields. – CodesInChaos Nov 26 '13 at 15:25
  • How much ressources do you need and how much does it speed up? – Smit Johnth Nov 26 '13 at 16:15
  • "Those rough costs suggest that the Twisted Edwards precomputation should be 3.6x faster, which is promising!" - not **that** much, but it's worth mentioning on SRP page. – Smit Johnth Nov 26 '13 at 16:25
  • @CodesInChaos This answer is a bit confusing. Sure, finding the discrete logarithm in a 256 prime field could be easy, but in a larger field it is not. Diffie Hellman depends on this problem being hard. If your point is that Blizzard used a small field, I don't think it is clear from your answer. – user239558 May 08 '14 at 09:12
  • @user239558 SHA256 is first pre-image resistant, but it's still a bad password hash since it's cheap to compute, making offline password guessing attacks cheap. It's similar with computing `G^x mod p` in a finite field. Solving this for x is hard (the discrete logarithm problem) which corresponds to the pre-image resistance of SHA2. But it's still bad, since computing `G^x mod p` is cheap. You need to use scrypt(password, salt) private key/exponent, not sha1(password, salt). – CodesInChaos May 08 '14 at 09:21
  • What CodesInChaos probably meant is that modexp with constant g and N can be fasten up, opposite to hash scrutinizing functions. – Smit Johnth May 12 '14 at 01:19