Re: [Cfrg] Do we need a selection contest for AEAD?

["Blumenthal, Uri - 0553 - MITLL" <[e-mail]>]

As I said, some of us do not need nonce hiding, and do not want to pay the performance/complexity price for having it.

 

From: Cfrg <[e-mail]> on behalf of Mihir Bellare <[e-mail]>
Date: Wednesday, June 24, 2020 at 14:45
To: Paul Grubbs <[e-mail]>
Cc: CFRG <[e-mail]>
Subject: Re: [Cfrg] Do we need a selection contest for AEAD?

 

 

it might be good to have the first round be more of a "meta-competition" for discussing and prioritizing requirements and use cases.

 

Responding here both to the above and to Thomas's post about Deoxys. I think we need to step back to consider that what we call AEAD is not providing the message privacy that we think it is, and how that affects standardization. 

 

RFC 5116 says:  "there is no need to coordinate the details of the nonce format between the encrypter and the decrypter, as long the entire nonce is sent or stored with the ciphertext and is thus available to the decrypter ... the nonce MAY be stored or transported with the ciphertext ... "

 

What [BNT19] points out is that if you send the nonce with the ciphertext, for certain choices of nonces, you can compromise privacy of the message. This is kind of obvious in retrospect; the nonce can be message dependent. The difficulty is that in AEAD (which we call AE1), the nonce is assumed magically provided to the decryptor; the AEAD model does not say it is safe to transmit it.  [BNT19] defines a stronger AE2 goal which does what AEAD seems to have been understood to do, namely provide message privacy for any (non-repeating) choice of nonces, even if they are transmitted. This is done via nonce hiding, so the latter is not just about hiding the nonce itself (which is an added benefit) but, even before that, about hiding the message when nonces are visible. 

 

Message-dependent nonces are not a likely choice, but they are allowed under RFC 5116. If one continues to use AEAD, I think in future standards, language as used in RFC 5116 should be changed to say that it is only with nonces that do not depend on the message (like random numbers or sequence numbers) or nonces that are not transmitted. But it is a burden for implementers to have to figure out if their nonces are conforming. With AE2, they don't need to; any (non-repeating) nonce choices, even message dependent, are fine.

 

On Tue, Jun 23, 2020 at 10:31 PM Thomas Peyrin <[e-mail]> wrote:

For nonce-hiding, I wonder if/how the constructions in https://eprint.iacr.org/2019/624.pdf could be applied on top of these modes optionally.   

 

As above, it isn't just for nonce hiding that one would want to apply the above; it is to have message privacy even for transmitted nonces, meaning what AEAD was thought to provide. I think the goal for Deoxys and future AE schemes should be AE2 for this reason. 

 

 As to the methods, yes, one could use them to get AE2. But the bounds mostly admit a birthday term. You seem to have worked to get good bounds for Deoxys, so perhaps one could find a direct way to get AE2 for Deoxys without sacrificing something in the bounds?

 

Mihir