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

[Trevor Perrin]

On Wed, Feb 14, 2018 at 9:14 AM, Samuel Neves
<samuel.c.p.neves at gmail.com> wrote:
> The first 32 bytes of the ChaCha20 stream are used to derive the two
> one-time Poly1305 keys, r and s. They are not used to encrypt
> plaintext. The tag is then (polyeval(ciphertext, clamp(r)) + r) mod
> 2^128. Whatever the distribution of polyeval(ciphertext, clamp(r)) mod
> 2^128 may be, the one-time key s is always a fresh output from
> ChaCha20, which is presumed to be indistinguishable from random. As
> such, so is the tag.

Ah, thanks Samuel!

So this thread is a bit of a false alarm...


> I guess the RFC may be referring to the polynomial evaluation portion
> of Poly1305?

Hmm, maybe a charitable reading of RFC 7539 is that the Poly1305 "s"
is required to be unpredictable but not indistinguishable, so even
though ChaCha20 supplies an indistinguishable "s",
indistinguishability of the tag isn't a necessary property of all uses
of Poly1305?

Less charitably:  Maybe section 2.7 in that RFC just doesn't make
sense (see the complaint about ChaCha20 being "not what
protocols...require" for a PRF, because it's able to generate an
"arbitrarily long keystream").

---

This raises a good question about Noise, though:

The Noise spec's statement that "The entire ciphertext must be
indistinguishable from random if the key is secret" is *NOT* just an
explanation of AEAD requirements, it's a new requirement we're adding,
that just happens to fulfilled by our existing Noise AEADs (and maybe
most AEADs?).

Is this requirement a good idea?

PRO:  We named this thing "Noise", and we've generally tried to
encrypt and make the handshake indistinguishable from, well, noise, as
much as possible.  There are potential use-cases where this matters,
e.g. making an "unfingerprintable" protocol for censorship-resistance,
or when trying to add padding so as not to leak message lengths.

CON:  It's an unnecessary requirement for an AEAD scheme.  Somewhere
down the line someone might show up with an AEAD that doesn't fit this
requirement but is otherwise good, and we will then be in the awkward
position of disallowing their AEAD for a superfluous reason that is
irrelevant to their use case.

Thoughts?


Trevor