5
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ BTW: you don't have to separately test the primality of $N$; if $q$ is prime, and $g$ passes the listed generator tests, then that implies that the values $g^0 \bmod N, g^1 \bmod N, g^2 \bmod N, ..., g^{N-2} \bmod N$ are all distinct, and that can happen only if $N$ is prime $\endgroup$ – poncho May 10 '16 at 19:22
  • $\begingroup$ I don't know (yet?) about other checks to make so I can only address your primalty test question here. Usually you'll use Miller-Rabin with sufficiently many rounds to get high certainity that a number is indeed a prime. If you want to be dead-sure (which you don't have to because $<2^{-256}$ error rate is just as good) you can also use the AKS algorithm. $\endgroup$ – SEJPM May 10 '16 at 19:30
4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Thank you so much =^-^= The $a, b < \log_g N$ check you list makes sense; it forces $g^a$ and $g^b$ to "wrap" $\pmod N$. $\endgroup$ – Myria May 11 '16 at 19:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.