[Cryptography] Crypto Standards v.s. Engineering habits - Was: NIST about to weaken SHA3?

[John Kelsey]

More random thoughts:

The minimal inner protocol would be something like this:

Using AES-CCM with a tag size of 32 bits, IVs constructed based on an implicit counter, and an AES-CMAC-based KDF, we do the following:

Sender: 
a.  Generate random 128 bit value R
b.  Use the KDF to compute K[S],N[S],K[R],N[R] = KDF(R, 128+96+128+96)
c.  Sender's 32-bit unsigned counter C[S] starts at 0.
d.  Compute IV[S,0] = <96 bits of binary 0s>||C[S]
e.  Send R, CCM(K[S],N[S],IV[S,0],sender_message[0])

Receiver:
a.  Receive R and derive K[S],N[S],K[R],N[R] from it as above.
b.  Set Receiver's counter C[R] = 0.
c.  Compute IV[R,0] = <96 bits of binary 0s>||C[R]
d.  Send CCM(K[R],N[R],IV[R,0],receiver_message[0])

and so on.  

Note that in this protocol, we never send a key or IV or nonce.  The total communications overhead of the inner protocol is an extra 160 bits in the first message and an extra 32 bits thereafter.  We're assuming the outer protocol is taking care of message ordering and guaranteed delivery--otherwise, we need to do something more complicated involving replay windows and such, and probably have to send along the message counters.  

This doesn't provide a huge amount of extra protection--if the attacker can recover more than a very small number of bits from the first message (attacking through the outer protocol), then the security of this protocol falls apart.  But it does give us a bare-minimum-cost inner layer of defenses, inside TLS or SSH or whatever other thing we're doing.  

Both this and the previous protocol I sketched have the property that they expect to be able to generate random numbers.  There's a problem there, though--if the system RNG is weak or trapdoored, it could compromise both the inner and outer protocol at the same time.  

One way around this is to have each endpoint that uses the inner protocol generate its own internal secret AES key, Q[i].  Then, when it's time to generate a random value, the endpoint asks the system RNG for a random number X, and computes E_Q(X).  If the attacker knows Q but the system RNG is secure, we're fine.  Similarly, if the attacker can predict X but doesn't know Q, we're fine.  Even when the attacker can choose the value of X, he can really only force the random value in the beginning of the protocol to repeat.  In this protocol, that doesn't do much harm.  

The same idea works for the ECDH protocol I sketched earlier.  I request two 128 bit random values from the system RNG, X, X'.  I then use E_Q(X)||E_Q(X') as my ephemeral DH private key. If an attacker knows Q but the system RNG is secure, then we get an unpredictable value for the ECDH key agreement.  If an attacker knows X,X' but doesn't know Q, he doesn't know what my ECDH ephemeral private key is.  If he forces it to a repeated value, he still doesn't weaken anything except this run of the protocol--no long-term secret is leaked if AES isn't broken.  

This is subject to endless tweaking and improvement.  But the basic idea seems really valuable:  

a.  Design an inner protocol, whose job is to provide redundancy in security against attacks on the outer protocol.

b.  The inner protocol should be:

(i)  As cheap as possible in bandwidth and computational terms.

(ii) Flexible enough to be used extremely widely, implemented in most places, etc.  

(iii) Administratively free, adding no key management or related burdens.

(iv) Free from revisions or updates, because the whole point of the inner protocol is to provide redundant security.  (That's part of "administratively free.")  

(v)  There should be one or at most two versions (maybe something like the two I've sketched, but better thought out and analyzed).

c.  As much as possible, we want the security of the inner protocol to be independent of the security of the outer protocol.  (And we want this without wanting to know exactly what the outer protocol will look like.)  This means:

(i)  No shared keys or key material or identity strings or anything.

(ii) The inner protocol can't rely on the RNG being good.

(iii) Ideally, the crypto algorithms would be different, though that may impose too high a cost.  At least, we want as many of the likely failure modes to be different.  

Comments?  I'm not all that concerned with the protocol being perfect, but what do you think of the idea of doing this as a way to add redundant security against protocol attacks?  

--John