What security checks do I need for SRP-6a?

Question

I'm implementing an SRP-6a login system. What security checks do I need to do? Note that the modulus is sent to the client at algorithm startup.

Here is the list I have so far. I'm using the Wikipedia names for the variables.

• Verify that $N$ is an appropriate size.
• Verify that $N$ is prime.
• Verify that $q = \frac{N-1}{2}$ is prime.
• Verify that $g$ is a generator of $(\mathbb{Z}/N\mathbb{Z})^\times$ by verifying:
  • $1 < g < N-1$
  • $g^q = -1 \pmod N$
• Verify that $0 < A < N$.
• Verify that $0 < B < N$.
• Verify that $u \neq 0$.
• The server should not send its proof before the client provides its valid proof.

Regarding the primality checks, what algorithm should I use? Should I randomize the parameters during the primality check in order to prevent a false server from finding a composite that passes what the client checks?

Answer 1

This is a good question, but I would consider hardcoding a known good group. There does not seem to be an advantage to letting the server decide if you can afford to use high enough parameter values.

The SRP paper lists the following checks:

• "n is a large safe prime" (this is your first three points)
• "g is a primitive root of GF(n)" (your next point)
• "A > 0" (modulo n, which you make sure of by checking the upper bound)
• "B > 0" (ditto)
• "a, b > log[g] n" (missing)

(The ordering constraint in your last point is mentioned elsewhere.)

You are missing the last one from the paper, but it is not essential:

The probability of this happening is infinitesimal (less than 2^-1014 for 1024-bit n), but the check is trivial.

One of your checks is unnecessary:

Verify that $u \neq 0$.

This will never happen with a secure hash, and if the hash allows finding inputs that force this, you will have worse problems. (But it is a fast check, so no problem.)

---

Regarding the primality checks, what algorithm should I use?

Miller–Rabin is common. AKS is too slow in an interactive protocol. I would follow the recommendations from standards like FIPS 186 (pdf), if you must do this.

Should I randomize the parameters during the primality check in order to prevent a false server from finding a composite that passes what the client checks?

Miller–Rabin uses random numbers anyway. Also, by choosing the correct number of rounds (see above) you should be able to make the probability of a false positive low enough to make finding one impossible.