Re: [Cfrg] What is the standard we are going to apply?

[Yoav Nir <[e-mail]>]

On Dec 24, 2013, at 5:34 AM, Alyssa Rowan <[e-mail]>
 wrote:

> 
> You, John, and others have mentioned a strong desire for protocols
> and/or primitives being evaluated to have well-vetted proofs:
> in standard model if possible, else random oracle; and side-channel
> resistance (i.e. suitability for constant-time implementation, etc).
> 
> That sounds to me like an excellent idea, wherever it is practical.
> 
> No matter what adversary might seek to interfere, and whether they're
> RFC3514 compliant or not when doing it, a protocol or primitive with a
> solid proof is more transparently, demonstrably effective than one
> without one.

I agree that given two similar proposed algorithms or protocols, the one with the security proof is the better choice. But please let's not over-state what these proofs actually show. The assertion "X is secure" is not one that can be tested. So all security proofs end up with a model of the protocol that simplifies out some aspects of the protocol, and a set of assumptions that seems (to the researcher) to be reasonable, but may or may not be correct in the real world, and a class of attack that seems important to the researcher (but other types may exist). So a proof that this class of attack cannot succeed under certain assumptions is important, but the protocol may still be vulnerable to other attacks, especially when used in a certain context, where the context may compromise the (otherwise excellent) algorithm, or by implementation details that allow side-channel information leak.

We have had several primitives and protocols with well-vetted security proofs that were later shown to be vulnerable. For many things, especially complex ones, we don't have a better method of vetting then saying "100 people looked at it, and 3 hackers + 2 cryptographers tried to break it for a whole week and they couldn't". Sad but true. The TLS renegotiation vulnerability was in a protocol that probably received more attention from researchers and hackers than any other. Thousands of people read the specification, implemented it, taught it, learned it, and wrote papers analyzing it and proving its security. And yet when after 15 years two people separately found the vulnerability, it was jaw-dropping obvious (after the fact).

What I'm getting at is that having someone present a primitive along with a security proof, and then having CFRG look at the proof and say "seems legit" is not a good enough process. As Stephen said in the other thread, we may be facing a time when NIST is no longer the gold-standard for vendors and standards writers. So we won't have the process we had 13 years ago, where NIST says "here's a new block cipher, we call it AES and it rocks", and then we all implement it in our standards and in our products. CFRG as it currently operates, or CFRG plus the requirement for security proofs is not a suitable replacement. I don't have an answer as to what is a suitable replacement. NIST has the resources to put some people to work full time on analyzing protocols and primitives (part of that is by borrowing expertise from the NSA). I don't know how a volunteer organization like IETF/IRTF can duplicate that kind of effort.

Yoav