Secure Remote Password Demystified

Secure Remote Password (SRP) is a protocol by which a user in a system is able to log in to that system without the system ever knowing or storing the user’s password.

Consider this description of the SRP protocol from cryptopals challenge 36:

Replace A and B with C and S (client & server)

C & S
 - Agree on N=[NIST Prime], g=2, k=3, I (email), P (password)
S
 - Generate salt as random integer
 - Generate string xH=SHA256(salt|password)
 - Convert xH to integer x somehow (put 0x on hexdigest)
 - Generate v=g**x % N
 - Save everything but x, xH
C->S
 - Send I, A=g**a % N (a la Diffie Hellman)
S->C
 - Send salt, B=kv + g**b % N
S, C
 - Compute string uH = SHA256(A|B), u = integer of uH
C
 - Generate string xH=SHA256(salt|password)
 - Convert xH to integer x somehow (put 0x on hexdigest)
 - Generate S = (B - k * g**x)**(a + u * x) % N
 - Generate K = SHA256(S)
S
 - Generate S = (A * v**u) ** b % N
 - Generate K = SHA256(S)
C->S
 - Send HMAC-SHA256(K, salt)
S->C
 -Send "OK" if HMAC-SHA256(K, salt) validates

This is supposed to be a simple summary of the exchanges between a client and server to securely authenticate a user. It’s a lot to take in, and it’s not super intuitive what is going on or how it’s supposed to work.

Here’s my best shot at summarizing this.

First, secure Remote Password (SRP) mostly concerns authentication ex-post-facto. It doesn’t concern registration, except for one thing: the server needs to have some way to authenticate that a user is who he claims to be without actually having the password. To do that, a server needs a “password verifier.” This is v.

Here’s where cryptopals confused me: They indicate in their challenge summary that the server is supposed to build v and salt. Well that makes no sense. If the client sends the plaintext password over the network in an unencrypted manner to begin with, what’s the point? You’ve already given away the game at that point. Solution: Have the client do it instead. The client comes up with v and salt and sends both of these values to the server for storage as part of a registration. Wikipedia agrees with me (or at least did when I wrote this).

From that point on, it’s really not too bad. The user is registered. When it comes time to actually log in, how is it that the client can prove he is the user he claims to be? Math.

The client comes up with A, an ephemeral key based on a one-time, random, private-key value a. A and the username get sent to the server. The server responds with the previously saved salt and an ephemeral public key B based on both v and another one-time, random, private-key value b. They each do math to come up with a new number S independently. If the numbers match, then it’s considered proven that the client is who he claims to be, and authentication is completed.

Now you’re thinking, “That’s nice, but that description doesn’t show how the math adds up. Can you show me?” I can do my best. Again, wikipedia has this math pretty awesomely summarized. One major difference between me and them, though, is that I’m going to retain the mod operation rather than condensing it down. Admittedly, it’s unwieldy, but in languages like java, it’s important to understand these operations can be done with BigInteger#modPow and not just BigInteger#pow. So, I kept the mod operations in this math. If you want to see a version without, check wikipedia.

Ok. Here we go…

There is a desired end value S that both the client and server should be able to independently calculate:

S = (g^b mod N)^{(a + ux)} mod N

Client –> Server

Client: I want to log in. Here is my username and a public key A.

Server

The server knows k, g and N. It also knows its own key b. It just received a username from the client and can retrieve a previously saved v from storage. It also can build u with both public keys (as follows).

u = SHA256(A|B) <— This means “A concat B hashed into SHA256 and converted to an integer”

A = g^a mod N

v = g^x mod N

With these values, we can compute a value S that is mathematically equal to the prior definition of S.

S = [A(v^u mod N])^b mod N

substitute A and v for their values

S = [(g^a mod N)(g^x mod N)^u mod N]^b mod N

simplify by reshuffling the exponents … (base^z)^y = base^zy

S = [(g^a mod N)(g^ux mod N)]^b mod N

simplify by reshuffling exponents again … base^z * base^y = base^(z+y)

S = [g^{(a + ux)} mod N]^b mod N

swap the exponents … (base^z)^y = base^yz = base^zy = (base^y)^z

S = (g^b mod N)^{(a + ux)} mod N <— desired end value

Server –> Client

Server: I see your login request. Here is a salt and a public key B.

Client

The client gets B and salt from the server. It also knows k, N, g, and password. It obviously knows its own private key a. And, because it has both A and B, it can build u the same way the server did. Also, from salt and the password, it can rebuild v through intermediate x.

u = SHA256(A|B)

x = SHA256(salt | password)

v = g^x mod N

B = kv + g^b mod N

With these values, we can compute a value S that is mathematically equal to the definition of S stated above as well as the value of S computed by the server.

S = [B – k(g^x mod N)]^{(a + ux)} mod N

substitute B for its value

S = [kv + g^b mod N – k(g^x mod N)]^{(a + ux)} mod N

substitute v for its value

S = [(k(g^x mod N) + g^b mod N – k(g^x mod N)]^{(a + ux)} mod N

simplify … k(g^x mod N) cancels itself out

S = (g^b mod N)^{(a + ux)} mod N <— desired end value

Final authentication

Once the client and server have independently found the shared secret S, the client produces a hash of S and sends it to the server. The server independently produces a hash of S and compares. If they match, the user is authenticated.

You can see my implementation of the client and server on my github repo. I had fun implementing this.

Fatal flaw?

Look at the math again. Consider the question posed in challenge 37: what if the client sends a value of 0 for A? What does that do to the shared secret value S computed by the server?

S = [A(v^u mod N)]^b mod N
  = [0(v^u mod N)]^b mod N
  = 0^b mod N
S = 0

If a malicious client sends 0 for A, then S = 0, which means that the SHA256 value sent to the server for authentication just becomes a constant: SHA256(0), which enables anyone to log in without the password. If A is any multiple of N, then S = 0 because any multiple of a number N modulo N will equal 0.

Oops!