Secure Remote Password Protocol (SRP)

What is SRP?

A "strong" password authentication protocol created by Tom Wu to address a case where both sides only share a weak, human-readable passphrase



Heavy details of the technicals I'm about to get into below can be found here

The Setup

  1. Client chooses $q$ and $N = 2q+1$ (both primes)
  2. Client chooses small random salt and computes:
    • $x = Hash(salt,password)$
    • $v = g^x$
      Note that g is the cyclic group $\mathbb{Z}_n$, see this slide for more details.
  3. The server then stores:
    • $v$ (the verifier)
    • $s$ (the salt)
    • $i$ (the username to index this stuff)
  4. Discards:
    • $x$ (the hash)

Subsequent authentications

  1. Client sends its username to the server
  2. Server looks up the verifier ($v$) and salt ($s$)
  3. Server sends the salt back to the Client
  4. Client computes $x=Hash(s,password)$
  5. Client generates a random number ($a$)
  6. Client sends $A = g^a$ to the server
  7. Server generates its own ephemeral key in the form $B = v + g^b$, where $b$ is a random number
  8. Server returns $B$ and another random number ($u$) called a random scrambling parameter

Both sides now compute this a common value $S=g^{ab+bux}$

Server side derivation: $g^{ab+bux} = (g^{a+ux})^b = (g^a.g^{ux})^b = (A.(g^x)^u)^b = (A.v^u)^b$

Client side derivation: $g^{ab+bux} = (g^b)^{a+ux} = (B-v)^{a+ux} = (B-g^x)^{a+ux}$

Using their respective computed $S$ from the previous slide

  • Client sends the server:
    $message1 = Hash(A,B,S)$
  • Server sends the client:
    $message2 = Hash(A,message1,S)$

What are its strengths?

or what threats does it mitigate?
  • Client side: you can keep your password in key-derivation function output form.
  • In transport the raw password is never used.
  • Server side: no actual passwords need to be stored, just the verifier and salt.
  • You can go further to derive a secure session key from the initial exchange.



see references page for more details

Cool follow up things to read if you're interested

Primitive Root Modulo N

aka, what does this fracking mean?!

In specific relation to the generator set $\mathbb{Z}_n$

coprime's of n are all the numbers ($k$), less than $n$ that satisfy $gcd(n, k) == 1$

The primative root(s), are the select few of those that have the same periodicity as the set.

e.g. $\mathbb{Z}_{11}$ has coprimes of {1,2,3,4,5,6,7,8,9,10}
x $x^1$ $x^2$ $x^3$ $x^4$ $x^5$ $x^6$ $x^7$ $x^8$ $x^9$ $x^{10}$
1 1
2 2 4 8 5 10 9 7 3 6 1
3 3 9 5 4 1
4 4 5 9 3 1
5 5 3 4 9 1
6 6 3 7 9 10 5 8 4 2 1
7 7 5 2 3 10 4 6 9 8 1
8 8 9 6 4 10 3 2 5 7 1
9 9 4 3 5 1
10 10 1

So we can see that {2,6,7,8} are the primitive roots of $\mathbb{Z}_{11}$

This is important from the crypto side to ensure the inversion is as difficult as possible.

Here's the thing an attacker would need to solve:
$ g^x \bmod 11 = result $
where $x$ is the hashed password

The fact that $N$ is prime is also of relevance as it ensures that the size of the congruent class is $N-1$.
If it wasn't prime the congruent class could be small, and in some cases no primative roots would exist, e.g. N=15

back to SRP Setup page