SRP and proofs

[David Jablon <dpj%world.std.com@localhost>]

Mika,

To elaborate on your points, I've listed some reasons
why one should be careful when considering what
"provable" security means in this field.

I'll also note that the task of describing the relative security
of password methods is one part of the evolving IEEE P1363.2
standard for password-based cryptography.

The main purpose of reduction proofs is to define an equivalence class
for methods that includes at least one very-well-studied and unbroken
method.  The goal is to prove that if you break one, then you've broken
them all.

Some issues with today's proofs are:

1. Proofs in this field are new and complex.

2. Not many people have the tools or skills to verify or evaluate the
correctness of such proofs.  This is especially true for password-based
protocols.  Who can say whether any individual proof or proof model
is flawless?  Proofs are great, but elegant proofs are rare.

3. Proof models vary among researchers.  

4. Acceptable assumptions to some people may be seen as a weakness
to others.  It seems a matter of taste as to how and when to use a
random oracle assumption.

5. Even in the absense of a reduction proof, the benefits of using a
well-studied and unbroken method may be too great to ignore
when the method is compared to known-to-be-broken alternative.

Proofs are important to identify the common foundations and common
unresolved questions underlying all these methods.  They provide a basis
to be more confident in a method.  But we must acknowledge their limitations.
Proofs are just another level in the imperfect art of cryptography.

Finally, here are some amendments to the list of published results for
password protocol reduction proofs:  A 1999 paper by MacKenzie and
Swaminathan proved SNAPI secure based on RSA and a random oracle
assumption.  But as far as I know, a full version of the 2000 Bellare and
Rogaway paper was never published. Links to these are at
www.IntegritySciences.com/links.html.  I also know of one other
new paper that is yet to be published.

-- David


Mika Kojo wrote:
>> > The problem with SRP, when compared to some other password-AKE's, is
>> > that it doesn't provide a security proof in the standard models. [...]

Tom Wu wrote:
>> The only other password-based key exchange that has a security proof (in
>> the random oracle model) is PAK, and it's not free to my knowledge.  The
>> majority of the secure password protocols (EKE, SPEKE, etc.) fall into
>> the "unproven but unbroken" category.

At 11:09 PM 5/1/01 +0300, Mika Kojo wrote:
>There is also one by Rogaway et al. and a recent one by Katz et
>al. (and the latter seems to avoid random oracles). Perhaps the point
>is that provable security could be a factor when selecting new
>protocols, although not a decisive one (as for example random oracles
>have been criticized recently).
>
>This is not really SRP specific, the SSH2 key exchange scheme does not
>have a proof of security either.


---------------------------------------------------
David P. Jablon
dpj%world.std.com@localhost
www.IntegritySciences.com
www.Phoenix.com