Problems with the SRP Protocol paper?

[Jonathan Herzog]

Greetings--

A new list-member here, so please forgive me if this is off-topic or  
has been discussed before. However, I've recently discovered a  
problem with the proof of security for the Secure Remote Password  
(SRP) Protocol, and Ivan Krstic recommended that I ask about it here.

In particular: The SRP protocol is a password-based authenticated key- 
exchange protocol that has been recently added to the TLS standard  
[RFC 5054] and the IEEE standard P1363.2. It is based on Diffie- 
Hellman, and claims to have all sorts of security properties.  
However, the original paper on the protocol [Wu, 1997] is somewhat  
unsatisfying from a mathematical viewpoint. First, it fails to  
rigorously define the properties the protocol is to meet, and gives  
only English-language intuitions. Secondly, it sometimes fails to  
argue that the protocol meets even those intuitions. Lastly, some of  
the crucial arguments of security are flawed in deep, deep ways.

The first two types of problems above are perhaps forgivable: the  
paper was published back in 1997 and cryptographers are still arguing  
today about how exactly to formally define security for these kinds  
of protocols. The last problem, however, is more worrisome. In  
particular, the 'proof' of security for SRP shows (correctly) that in  
certain cases, the problem of breaking SRP is exactly the same as  
breaking Diffie-Hellman. That is, Diffie-Hellman is a *special case*  
of SRP. Therefore, if one can break *all* instances of SRP, then one  
can break Diffie-Hellman and thus SRP is as secure as Diffie-Hellman.

However, this last step is wrong, at least in the area of  
cryptography. If we were talking about NP-completeness, then yes,  
this argument would work. But in crypto, we can't necessarily judge a  
crypto primitive by its hardest case.  We need to talk about the  
ability of the adversary to break a non-negligible *fraction* of  
cases. After all, the above 'proof' of security leaves open the  
possibility that it is easy to break those instances of SRP (the vast  
majority, actually) which *don't* directly encode a Diffie-Hellman  
problem.

Of course, this flaw in the proof can be fixed. It is straightforward  
to do the proof right, and to show that a random instance of a Diffie- 
Hellman problem can be transformed into a random instance of the SRP  
protocol. But the flaw in the paper is worrisome. Is this a known  
problem that has been addressed by later literature? Does anyone know  
of an analysis of SRP that measures the protocol against any of the  
recently-formulated definitions of security [Bellare & Rogaway 1994;  
Bellare, Pointcheval & Rogaway 2000, Canetti et al 2005]? In other  
words, do we know more about the security of SRP than is contained in  
the original 1997 paper?

Thanks.

--
Jonathan Herzog
Cryptographic consulting
jherzog at jonathanherzog.com
www.jonathanherzog.com

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com