SRP Won’t Protect Blizzard’s Stolen Passwords

Blizzard announced today they they have suffered a major data breach, and sensitive user data was stolen from their servers.  According to their statement the specific data stolen includes email address, the answer to the personal security question, and information relating to two-factor authentication. They also lost their SRP server-side verifier database, which is the database they use to verify user passwords.

And despite what Blizzard is claiming, I believe the majority of their users’ plain text passwords have been exposed as well.

We also know that cryptographically scrambled versions of 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.

–Mike Morhaime, President, Blizzard

The creators of Secure Remote Password, or SRP, call it a “verifier-based, zero-knowledge protocol resistant to dictionary attacks.” It is a protocol designed to allow a client to authenticate to a server using a password, while keeping that password secure from anyone who might intercept the messages between the client and server.

SRP stores verifiers on the server, instead of passwords, or password equivalents. SRP is also ‘resistant to dictionary attacks’, but the dictionary attacks that SRP resists are not the type of dictionary attack you perform after you steal the verifier database, but rather “dictionary attacks mounted by either passive or active network intruders.”

So if SRP doesn’t store passwords on the server, or even password-equivalents, what is SRP actually storing on the server, anyway? It’s all laid out in the whitepaper on SRP published by Thomas Wu in 1998, as well as RFC 2945:

To establish a password P, a user picks a random salt s, and computes:

  • x = SHA1(| SHA(username | “:” | P))
  • v = g^x % N

The server stores v and s as the user’s password verifier and salt. The values ‘g’ and ‘N’ are “well-known values, agreed to beforehand.” Blizzard has published these values and programmers can use them to interface with Blizzards systems.  In other words, the attacker knows ‘g’ and ‘N’. [1]

What the attacker was able to steal from Blizzard is the verifier database which is the set of { usernamev, s } for each user.

Anyone who does know v can already perform a dictionary attack.

–Thomas Wu, Creator of SRP

As Thomas Wu says himself in the whitepaper on SRP, “anyone who does know v can already perform a dictionary attack.” The point of the protocol is not to protect passwords from being dictionary attacked if the verifier database is stolen. The protocol does a tremendous job of protecting the password exchange itself from network eavesdroppers. That’s more than we can say for competing protocols such as MS-CHAPv2, which is an example of a password validation protocol which can be cracked using just a network trace.

Whoever stole the data will use a dictionary attack to compute the verifier value for each password in their dictionary, for each user that they have data on. If the calculated value v matches the in the database they stole, then they’ve discovered that users’ password. For each guess, the attacker must compute two SHA1 hashes to calculate ‘x’, which runs extremely fast (around 1billion hashes per second).  Then, they compute ‘v‘  by running a modular exponentiation (modexp).

[Updated 8/12/12]  Different versions of used different bit-lengths of ‘N’ – either 256-bit or 1024-bit.  I don’t know at this point if the verifier database that was stolen consisted of a mix of values derived using 256-bit and 1024-bit ‘N’, or all 1024-bit.  A dictionary attack using a 1024-bit based modexp() will be about 64x  slower than an attack using a 256-bit modexp(). [End Update]

A recent Intel benchmark shows performance of 1024-bit and 512-bit ME on their i7 -2600 CPU (from 2011). Based on these numbers, I would extrapolate that the attacker can probably run 1,800 1024-bit ME’s per second, or ~100,000 256-bit ME’s per second,for each CPU core they dedicate to the attack. At this rate an attacker can reasonably check 100,000 of their top passwords against 400,000 usernames, per day. Since the attack occurred, millions of users’ passwords have likely already been cracked. [2]

Unless Blizzard has previously strengthened their verifier database by selecting their own, more expensive hashing algorithm—such as bcrypt set at an onerous difficulty—then each users’ password can be individually dictionary attacked at well over 100k guesses per second. Combined with Blizzard’s reduced entropy password policy (case insensitive, reduced alphabet), this means that it is highly likely that the vast majority of passwords stored in their database have already been cracked by the attacker.

The prospect of an attacker holding your email address, password, and security question/answer is troublesome, to put it mildly. Blizzard is incorrect in claiming that SRP “is designed to make it extremely difficult to extract the actual password” after the verifier database is stolen. That they would make this statement is at best misleading and inaccurate, and dangerous if users believe their passwords are still actually safe.

I implore anyone who is a member of immediately ensure your old password is not being used on any other sites, and you should never use that same password again. You should also verify your secret question/answer that you used on is not reused elsewhere as well.

To Mike Morhaime and the Blizzard security team, I would request immediate retraction or clarification on your statement about the difficulty of extracting passwords from the stolen database.  The message to your users should be clear: your passwords have almost certainly been cracked, and you should take immediate action.

[Updated 8/10/12] – For those claiming on Reddit and elsewhere that this is sensationalism, I believe if you have the choice between giving the average user a false sense of security, and giving the elite user a false sense of insecurity, you should always choose the later. Compare “it’s extremely difficult for the attacker to extract actual passwords” with a more precise statement that they could have given:

From the database they stole, the attacker can likely test at least 100 billion passwords per day, and they will successfully crack at least every password which can be found in a ‘Top 1 Million Passwords’ list.

Blizzard will devote significant computing resources to proactively identify any weak passwords in our database, notify affected users that their passwords have been compromised, and require those users to choose a new password.

— A proposed alternative statement which Blizzard could have made

How would the average user respond to one statement versus the other?  My concern is that the average user reading Blizzard’s current press release might not appreciate the potential that their password has been compromised.  [End Update]

I would like to say, it’s not entirely Blizzard’s fault that their network was compromised. Such a compromise is, in fact, inevitable.  Clearly Blizzard would be acutely aware of the extraordinarily valuable target that they present to attackers. They are almost certainly under constant attack from multiple parties.

The sad truth is that the state-of-the-art ‘best practices’ in the industry currently fail to adequately protect users’ passwords from being stolen. It is my personal mission, and the mission of my company TapLink, to ultimately provide the software, infrastructure, and education which will allow companies, large and small, to successfully defend from this sort of attack.

[1] – A complete writeup of the 1.0 SRP impementation tells us that  ‘g’ is 47 and ‘N’ is a 256-bit value.  In Bnet 2.0 ‘g’ and ‘N’ are also known, but ‘N’ is increased to 1024-bit length.

[2] – Note the performance numbers in the Intel report are for a single core, not per CPU – so it’s actually 400k/sec per i7-2700.  I also tested further on Amazon EC2; with a c1.xlarge Amazon EC2 instance ($0.66/hr) based on benchmarking with ‘openssl speed’ you could check approximately 100 billion passwords for $100 if 256-bit N was used. So, for example, you could try 1,000,000 passwords against 100,000 users for $100. This is not what I would call “computationally very difficult and expensive.”  [Update 8/12/12] For a 1024-bit N used in Blizzard’s latest protocol, it would cost approx $6,400 to test 100 billion passwords.