[2148] in cryptography@c2.net mail archive
More on SRP
daemon@ATHENA.MIT.EDU (Marcus Leech)
Fri Feb 20 17:03:39 1998
Date: Fri, 20 Feb 1998 14:56:18 +0100
From: "Marcus Leech" <Marcus.Leech.mleech@nt.com>
To: cryptography@c2.net
The SRP paper implies that even if an attacker captures v,
the verifier, that the attack cannot compute the password
easily. I believe this, also, to be a false and misleading
claim.
Under the attack scenario, we assume that the attacker has
captured 's' via simple eavesdropping, and has captured
the corresponding verifier, 'v'
The problem, then, becomes how to determine the secret
value 'x', given only s, and v. Recall that x is
produced by computing:
x = H(s,P)
The verifier is produced by computing:
v = g^x mod n
[g and n are 'common', just like in D-H]
The assumption of non-invertibility in D-H holds only
because 'x' is typically large (some significant fraction
of the size of the modulus), and because it is random.
Only one of these assumptions holds for SRP--I'll assume here
that the 'H' function is something like SHA-1 or MD5.
Finding 'x', given only 'v' and 's' is computationally not
that hard, assuming that 'P' is low entropy. I simply
compute:
x' = H(s,P')
v' = g^x' mod n
for all values of P' in my dictionary/generator. Guesses
generated in this way can be tested against the real protocol.
The rate-limiting step here is the modular exponentiation,
which for the attack can be optimized relatively cheaply
by constructing a hand-optimized modexp that only knows how
to do modexp with a fixed based and modulus (the targets).
My lowly HP9000/712 can do one or two 1024-bit modexps
per second, which gives about 80K-160K trials per day for
a single workstation. For an input password space of
entropy 20 bits or so, I can find the password in under
ten days, with a single workstation.
Once I've determined the password, P, I can masquerade as
the victim.
Is there a flaw in my logic? Could it possibly be this
simple?
While I enjoy cryptographic curiosities as much as the other
readers of this list, I also have real, pragmatic security
problems to solve.
Proposals of this sort made to a public standards body, such as
the IETF, must have some clear, undeniable advantage over
other solutions in the same problem space. I don't think
that SRP qualifies.
