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

- Client chooses $q$ and $N = 2q+1$ (both primes)
- 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.* - The server then stores:
- $v$ (the verifier)
- $s$ (the salt)
- $i$ (the username to index this stuff)
- Discards:
- $x$ (the hash)

- Client sends its username to the server
- Server looks up the verifier ($v$) and salt ($s$)
- Server sends the salt back to the Client
- Client computes $x=Hash(s,password)$
- Client generates a random number ($a$)
- Client sends $A = g^a$ to the server
- Server generates its own ephemeral key in the form $B = v + g^b$, where $b$ is a random number
- 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)$

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

- Tom Wu's Paper on SRP (full gore)
- Stanford - Competitive Analysis of SRP
- SRP Protocol for TLS Authentication [RFC]
- Quora discussion about SRP mainstream usage

***cough** Some people's comments in there are really stupid* - Tom Wu's interview about SRP
- Stanford - SRP protocol design

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