[noise] Ciphertext-indistinguishability from random noise with Poly1305?

[Trevor Perrin]

On Mon, Feb 12, 2018 at 5:53 PM, Keziah Elis Biermann
<keziah at kizzycode.de> wrote:
>> Probably we should change the spec requirement to require all bytes of
>> the ciphertext except the last 16 to be indistinguishable, which is
>> what the default REKEY() function requires.
>
> This would be the easy solution, but IMHO it would be cleaner to
>  – require that the underlaying cipher-construction (e.g. AES-CTR for AES-GCM) is a strong PRF/PRP
>  – require that the authentication-tag is appended to the encrypted bytes
>
> This would ensure that (if you encrypt 32 bytes) the first 32 bytes of the ciphertext are always indistinguishable from random data if you don't know the key.

That wouldn't work for things like SIV, where the ciphertext starts
with a "synthetic nonce", instead of ending with an authentication
tag.  But I'm not sure this synthetic nonce necessarily fulfills the
indistinguishability requirement I described, either.

Maybe we could draw a sharper distinction between "authentication tag"
AEADs and "SIV-like" (or "other")?

In the former case, we can automatically synthesize the REKEY
operation by taking the first 32 bytes from encryption of zeros.  This
is efficient for typical AEADs which do encryption, then
authentication, since REKEY can skip the authentication-tag
calculation.

In the latter case, REKEY would have to be explicitly defined.  But if
we want an efficient REKEY with SIV we'd have to do that anyways,
since SIV does authentication then encryption, so it makes sense to
define a more efficient REKEY that skips the authentication step.  For
example, in AES-GCM-SIV I think we could take the new key as an
additional output from the derive_keys function:

https://datatracker.ietf.org/doc/draft-irtf-cfrg-gcmsiv/?include_text=1

Trevor