In this blog we’ll look at an interesting vulnerability in some implementations of a widely used authentication protocol; Secure Remote Password (SRP). We’ll dive into the cryptography details to see what implications a little mathematical oversight has for the security of the whole protocol.
This vulnerability was discovered while evaluating some different implementations of the SRP 6a protocol.
The problem was initially identified in cSRP (which also affects PySRP if using the C module for acceleration), and was also found in srpforjava. It's not clear how many users these projects have, but regardless the bug is interesting enough to discuss by itself.
SRP: What is it good for?
SRP is a popular choice for linking devices or apps to a master server using a short password or pin code. SRP is often used for authentication that involves a password, like in mobile banking apps (for instance the ING mobile banking app in the Netherlands) but also in Steam.
Quote from http://srp.stanford.edu/: "The Secure Remote Password protocol performs secure remote authentication of short human-memorizable passwords and resists both passive and active network attacks."
In other words, being able to read and mess with network traffic of a legitimate client does not help an attacker log in. The fastest way to break in is to just try every possible password. The server can prevent this using rate limiting or by locking accounts.
SRP in three steps
The protocol consists of three stages:
- Client and server exchange public ephemeral values.
- Client and server calculate the session key.
- Client and server prove to each other that they know the session key. This can optionally be integrated with the normal communication that happens after authentication.
For the purpose of this blog only the first part of the protocol is relevant. In this stage the client sends its ephemeral value along with a username, and the server responds with its own ephemeral value and the random salt value for the given user.
How SRP checks your password
In the first part of the protocol the client and server exchange "ephemeral values", which are large numbers calculated according to the SRP protocol. These values actually play multiple roles at once in the SRP protocol. This is how it performs authentication and establishes a shared session key in just one round trip!
The first role is as a kind of key exchange in a way that is similar to how Diffie-Hellman key exchange works. In Diffie-Hellman both parties generate a random number "r" which is their private value, and use this to generate a public value using the formula (g ** r) % N, where g and N are public fixed parameters. In SRP the client generates its public value in exactly this way, but the server does something slightly different.
In SRP the Diffie-Hellman key exchange is altered to additionally force the client to prove that it knows the password for a certain user. One way to think of this is that the server alters its public value based on the password for the given user, and the client needs to compensate for this alteration in order to derive the same session key as the server. The client can only perform this compensation if it knows the password.
In order to perform this calculation the server uses a "verifier" value for the desired user. In many ways a verifier is like a password hash. It is only derived from the username, the password, and the salt. Since the username and salt are stored in plain text on the server and are sent in plain text over the network, the password is the only unknown part and an attacker can generate verifiers for every possible password until he finds a match. Since a verifier is generated using only a single hash operation and a modular exponentiation in most SRP implementations, it is fairly easy to brute force compared to modern password hashing methods like scrypt.
One other way this "verifier" value is like a password hash, is that it’s not sent over the network, and even if it is stolen from the server, a hacker can't use it to log in directly. Because of how it’s generated the server can use it to calculate its public ephemeral value, but a client can’t use it to calculate the session key. A client needs the actual password for that.
How the hacker gets your password: the bug
Warning: math ahead! It helps if you understand some algebra, but hopefully it's not required.
Now we come to the actual bug, which is in the calculation of the server's public ephemeral value. This is the formula to calculate this value:
B = (k * v + ((g ** b) % N)) % N
The ((g ** b) % N) part is just the standard Diffie-Hellman calculation of a public value from the private random value b. The values g and N are the public Diffie-Hellman parameters.
The addition of k * v is the extra adjustment for authentication in the SRP protocol. The value k is calculated by hashing the (public) g and N values (so k is also public), while v is the verifier for the user that is logging in.
In the buggy implementations, the actual calculation for B is slightly different:
B' = k * v + ((g ** b) % N)
In other words, the final reduction modulo N is missing. As it turns out, that is actually very important! Because B has this final modulo operation, the public Diffie-Hellman value and the value derived from the verifier are hopelessly mixed up, and we can’t separate the two at all anymore.
But what about B'? Well, we can divide it by k.
B' = (k * v + ((g ** b) % N)) / k
Let’s define i and j as the unknown quotient and remainder of dividing the public Diffie-Hellman value ((g ** b) % N) by k:
((g ** b) % N) = k * i + j
B' = (k * v + (k * i + j)) / k
By definition j is smaller than k so we disregard it:
B' = (k * v + k * i) / k
B' / k = v + i
Lets write |B| for the (approximate) length of B in bits. I’m going to ask you to just take my word for it that values that came from a modular exponentiation ((g**x) % N) (like v) are about as long as N (say 2048 bit), and values resulting from a hash (like k) are about as long as whatever the size of that hash function’s output is (say 256 bits).
Now we know these things about the lengths of v and i:
|v| ~= |N|
|i| ~= |N| - |k|
In words: v is 2048 bits, while i is (2048 – 256) bits long. So the value i is about 256 bits shorter than v.
Take a look at B' / k again with that in mind:
B' / k = v + i
This means that the top 256 bits of B’ / k are equal to the top 256 bits of the verifier v! In other words, the server leaks the top 256 bits of the verifier.
What is that good for? Well, the odds of two different verifiers having the same top 256 bits are impossibly small. This means that these top 256 bits are enough to check whether two verifiers are equal, which means we can perform offline password cracking using this leaked part of the verifier.
Note that all bit lengths are approximate, and in any case the values 2048 and 256 depend on the Diffie-Hellman parameters and hash function used.
In short
Because of this bug the server will send a value equivalent to a password hash to any client that wants to log in. This can then be cracked offline, which totally breaks the guarantees of the SRP protocol.
The fix
Tom Cocagne, the maintainer of cSRP, was very quick to fix the affected code after we reported the bug. The fix is to perform the missing modulo operation.
The author of srpforjava was contacted later, after we discovered that this library was also affected. We’ve sent a patch, but this is not applied yet.
Both libraries haven’t had a new release in a long time, and it’s difficult to determine who’s using these libraries. Hopefully this blog post will reach them.
Because the client performs all operations modulo N, the fact that the server now returns different B values does not affect the normal operation of the protocol at all. Clients are compatible with both the patched and unpatched server.
Do not try this at home
This article tries to explain SRP in a simplified way. Please do not go and implement SRP yourself. In fact, please do not implement any cryptography code unless you are an expert! When it comes to cryptography, every detail matters. Even the ones the textbook doesn't mention.