SRP vulnerability when using a 256-bit modulus

Note to reader: This SRP vulnerability applies only if a 256-bit modulus is being used. For example, in Blizzard’s 2 protocol, the modulus is 1024-bit [1].

In my prior blog post, I explained how an attacker can use a dictionary attack to try to guess users’ passwords based on the recent Blizzard data breach, where they were using SRP to store the passwords. Some readers have pointed out, it is significantly slower to dictionary attack SRP than raw SHA1, so SRP at least protects users who have chosen strong / random passwords. However, depending on the bit-length of the modulus, there may be an improved technique which could allow significantly faster attacks.

We know that SRP takes a hash of the username, password, and salt, and produces a value x.  Then it runs that through a modular exponentiation, as: v = g^x % N.  In this case, ‘g’ and ‘N’ are known to an attacker.

From the source code of Emulators (prior to SC2) we know that the hash is SHA1, g = 47, and we know the 256-bit value of N. Is it then possible to compute the discrete logarithm of g^x % N, and in doing so, recover the original hash value x?

“It is actually much easier to break those keys than this blog claims. 256-bit discrete logarithms (why just 256 bits, Blizzard???) are solvable in a few minutes; once the first log is solved, solving another one is almost instantaneous. Therefore, solve all the logarithms to obtain x, then bruteforce the SHA-1’s at much higher speed.”

— Anonymous

If it is possible with only a few days of computation to recover all of the original SHA1 values (recover x from v), then it now becomes possible to dictionary attack each individual users’ password at the full SHA1 hashing rate, up to 2.5 billion passwords per second. This would significantly increase the risk to users’ passwords; even 48-bit entropy passwords (9 character case-insensitive alphanumeric) could be cracked in a day on average.

It appears that attackers may have even been researching this technique since August, 2011:

I contacted several researchers in this field, and managed to connect with Samuel Neves, a PhD student in the Department of Computer Engineering at University of Coimbra, Portugal.  I had seen his response to ‘How to Practically Find Solutions to a Discrete Logarithm‘ on Stack Overflow’s Crypto exchange, which was also posted August, 2011 and features the specific ‘N’ value previously used by Blizzard.

Sam was able to confirm that given a 256 bit-length modulus, it is possible to recover the values from v, and with his permission I have quoted him at length throughout the remainder of this post.

We know that in index calculus the largest computation (that is, finding the logs for most small primes) only has to be done once, and can be done beforehand. After that, solving arbitrary logs is a matter of finding a smooth representation for g^x, which can be achieved by multiplying small primes by this number until we hit a smooth result.

— Samuel Neves, PhD Student, University of Coimbra

There’s a further implication of this, which goes to the heart of what SRP is designed to prevent; if you are able to hack the modexp by performing a discrete logarithm, “then you don’t even need to hack the server to be able to perform dictionary attacks: just sniff a handshake, and verify whether S = (B – g^x)^(a + u*x) is valid for guessed x = H(s, P) (You can find a by finding the log of A=g^a). This may be improvable for speed, but the point stands.”

If the discrete logarithm is solvable, you don’t even need to hack the server to be able to perform the attack.

[Updated 8/18/12] A third attack vector is available if you are able to compute the discrete logarithm and you have access to the validator database.  Once you reverse the encryption and retrieve each users’ hash value x, you can use as a password equivalent, and log into the server using only x.  This is possible because all the client has to do is compute: S = (B – g^x)^(a + u*x).  B, g, a, and u are all known quantities to the SRP client.  If you can calculate from by performing the discrete logarithm, you can login as the user without even cracking the user’s password.

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

If your goal is gaining access to the targeted server, then you’ve already won.  You can use the value that you recovered from and login directly as that user.  If what you’re actually after is the users’ password, you still have work to do.

If it takes 15 seconds to recover each x using this technique, then you can either spend that time testing 6 million passwords using the original technique (which calculates the 256-bit modexp), or you can undo the modexp, and then start attacking the hash at 2.5 billion tests per second. So if an attacker is willing to spend 10 minutes of computing time attacking each password:

  • Attacking v by performing the 2 SHA1 hashes and a 256-bit modexp(): ~240 million passwords checked in 10 minutes
  • Reverting into x and then attacking the SHA1 hash: ~1.5 trillion passwords checked in 10 minutes

In light of this, there are two three key take-aways:

  • An attacker can login as any user if they are able to steal the verifier database and a 256-bit modulus is being used, by exposing x, a password equivalent
  • Both dictionary and brute force attacks against users’ passwords are demonstrated to be possible against 256-bit SRP, by recovering the hash value from v, and then using a GPU to attack the hash using two rounds of SHA1 per test.
  • Dictionary attacks, and potentially brute force as well, against a users’ password are demonstrated to be possible against a simple network trace of 256-bit SRP, by finding the discrete log of ‘A’, if the SRP exchange is sent in the clear, or if the SRP exchange is otherwise recoverable.

The fundamental concepts behind SRP (which is linked to Diffie-Hellman) are still sound, but there are two steps which must be taken for any SRP implementation to be secure against these attacks:

  1. The bit-length of the modulus ‘N’ must be at least 1024-bit to prevent an attacker from computing the discrete logarithm
  2. The hashing step currently defined as a two-step SHA1 in RFC 2945 must be replaced with at least PBKDF2, bcrypt, or scrypt, with an appropriate iteration count / tuning parameters to deter from dictionary attacks

Implementers may also consider adding an additional layer of protection against network sniffing, for example by using TLS on top of SRP.

Using 256-bit SRP “is as if some website was using HTTPS, but with a 256-bit RSA certificate, which doesn’t do you much good. Weirdly enough, despite integer factorization and the discrete logarithm having similar hardness, integer factorization has had much higher exposure, leading to more awareness and conservative choices on RSA keys.”

A note on disclosure of this vulnerability in light of the recent Blizzard data breach: After I saw the comment about using discrete logs, and then found evidence of attackers actually trying to apply the specific technique, it’s reasonable to conclude that this technique is already out in the open. Since this technique exposes a practical attack against 256-bit SRP given a simple network trace, it is critical that anyone managing an SRP-based authentication system understand this vulnerability. A reader has also pointed out that Blizzard’s 2.0 protocol uses SRP6a with a 1024-bit modulus, so this technique would not apply to Bnet 2.0.

Thanks to the anonymous Redditor who posted the original comment alerting me, and to Mr. Neves for his help in substantiating these claims.

[1] SRP6a code being used in a Bnet 2.0 Emu with a 1024-bit N –  (Thanks, Nicolas for pointing me to this)

[ 2] Some interesting trivia, here is a discussion between the creator of SRP and the creator of John the Ripper, discussing how SRP will not age well in terms of resisting dictionary attacks… 12 years ago:  Thanks, @JokFP.