# SRP-6 vulnerabilities when N is small

I'm one of the developers of an application which uses SRP-6 as the authentication mechanism. The authentication part of the code is very old and uses N with only 256 bits (all arithmetic is done in modulo N). After receiving reports of stolen passwords we upgraded to SRP-6a with the size of N 1024 bits.

We are still investigating (both on the client and server side) how the passwords were stolen/broken. I know that SRP-6 with such a low N value is vulnerable to man-in-the-middle attacks and "two-for-one" guessing (SRP-6 Improvements and Refinements paper by Thomas Wu). The attacks were probably made only on the client side, but this made me very curious.

Would it be possible for an attacker to launch an offline dictionary/brute-force attack on the B public key:

B = (k*v + g^b % N) % N
N - 256 bits long
b - 152 bits long (random private key - generated using OpenSSL library)

Is it possible with modern technology? Could the attacker somehow predict or find out the random value b, extract v=g^x % N, then perform a discrete logarithm and find x?

-

"Would it be possible for an attacker to launch an offline
dictionary/brute-force attack on the B public key: ..."

That is possible if and only if the attacker can distinguish b's distribution from the uniform distribution on {0,1,2,3,...,N-3,N-2}. $\:$ If so, an attacker could compute verifiers v for candidate passwords, subtract kv from B mod N, and solve the resulting discrete logarithm instance to check the candidate passwords. $\:$ Otherwise, since N is prime and g is a generator mod N, the addition modulo N reveals a
uniformly chosen element of {0,1,2,3,...,v-1,v+1,...,N-2,N-1} and hides everything else about v.

"Is it possible with modern technology?"

The only way "modern technology" is relevant is to the
possibility of breaking a PRNG used to generate the b values.

"Could the attacker somehow predict or find out the random value b,
extract v=g^x % N, then perform a discrete logarithm and find x?"

If the attacker can "somehow predict or find out the random value b",
then the additional effort needed to find v is trivial.

-
Basically if someone could predict the random value "b", then it would be easy to compute "v" from the public key "B". What if someone does not know anything about b and he computes using a dictionary candidate "v" values, subtracts kv from B and tries to find the log of the result B - kv? If there is such a value, the initial chosen "v" value would be correct? –  xkyve Aug 19 at 10:45
If "someone ... B - kv" then succeeding at finding those logs would give candidate S values. $\hspace{.54 in}$ Probably not, since those logs will almost always exist. $\;$ –  Ricky Demer Aug 19 at 20:10

Solving a 256-bit discrete log is absolutely doable, and quite quickly, these days; there are public tools that can do it, though they may require some expertise to use.

On that note, even a 1024-bit modulus is not particularly conservative: it is generally agreed that well-funded organizations today could break logs of that size as well, but at a very large cost. The current minimum recommended modulus size for RSA, Diffie-Hellman, SRP, etc is 2048 bits.

That being said, I would also put my money on a client or server-side break-in before arriving at the conclusion that the log was being broken.

-

Being able to solve the discrete logarithm in SRP-6 allows an eavesdropping attacker to dictionary attack the password. It will not directly reveal a strong password or its hash. It requires the attacker to observe a successful authentication, $B$ alone does not suffice.

1. The attacker eavesdrops $s$, $A = g^a$, $B$ and $M_1$.
2. The attacker solves $a$ from $A$.
3. For each password guess $P$, the attacker calculates $M_1$ just as the user would.
4. If it matches, the password guess was correct.

From the point of view of cracking the password, this attacker is in the same position as one who breaks into the server and steals $v = g^x$, but isn't able to break the DL. (The latter could additionally impersonate a server as Ricky Demer mentions.)

With both $v$ and a too small modulus, no guessing is needed to derive $x$, allowing authentication or impersonation of either party.

-
How would that attacker impersonate the server without finding the password via 3&4? $\hspace{1.23 in}$ –  Ricky Demer Aug 19 at 9:27
@RickyDemer Which attacker? The one who breaks the discrete log in $v$ to get $x$? That's all the information the server has. –  otus Aug 19 at 9:32
The attacker that you say "is in the same position as one who breaks into the server and steals $v = g^x$, but isn't able to break the DL". $\;$ –  Ricky Demer Aug 19 at 9:54
@RickyDemer, oh, right, I was only thinking about logging in due to the OPs mention of stolen passwords, but I'll update the post to clarify. –  otus Aug 19 at 10:27