SRP-6 vulnerabilities when N is small

Question

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?

Answer 1

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

Answer 2

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.

Answer 3

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.