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

[Daniel Franke <[e-mail]>]

On Fri, Jun 19, 2020 at 3:13 PM Mihir Bellare <[e-mail]> wrote:

>
> With regard to requirements for the mode, I would suggest to also consider
> adding nonce hiding.
>
> AEAD is understood as providing message privacy for any choices of nonces,
> as long as they don't repeat. (Ignoring the nonce-misuse aspect, which is
> orthogonal to what follows.) But, as pointed out in [BNT19]
> <https://eprint.iacr.org/2019/624>, this isn't really true. There are
> choices of non-repeating nonces that, if transmitted with the ciphertext as
> necessary to allow decryption, compromise message privacy. This does not
> contradict the AEAD definition, because the syntax of the latter gives the
> decryptor the nonce and leaves the implementer to ensure it gets there.
> Nonce hiding AE (which has a modified syntax and security definition, as
> per the above paper) fills this gap.
>
> This problem does not arise with random nonces. But the promise of AEAD
> was to provide privacy with arbitrary nonces. A standard should either do
> this fully (nonce hiding) or come with restrictions to only use, say,
> random nonces.
>
> Nonce hiding is also of interest for anonymity and meta-data privacy. With
> regular AEAD, nonces that are sequence numbers can (if visible to the
> adversary) reveal information, as pointed out by Bernstein
> <https://groups.google.com/g/crypto-competitions/c/n5ECGwYr6Vk/m/bsEfPWqSAU4J> and
> CHAE <https://chae.cr.yp.to/whitepaper.html>. This is prevented in part
> by nonce hiding.
>

 This was, indeed, quite the inconvenience when we were designing Network
Time Security. We had to mandate random nonces in order to satisfy our
privacy goals, and then we had to choose AES-SIV as the MTI AEAD algorithm
because random 12-byte nonces generated in response to replayable requests
lead to a non-negligible risk of collision. A standard for nonce hiding
would have been very useful to us.