[CFRG] Security limits of ChachPoly (was: XChacha20 counter size)

[Loup Vaillant-David <[e-mail]>]

> This is also relevant for authenticators based on universal hashes
> like AES-GCM and ChaCha/Poly1305, whose security depends linearly on
> the _maximum_ message length (not just the total amount of data):
> Accept a single 256 GiB message, and the number of messages you can
> safely handle -- even if all the others are tiny -- dramatically
> drops compared to an application limited to 2^14 bytes per message
> like TLS.

I did some digging, and in the case of Poly1305 as used in RFC 8439,
the number of messages is irrelevant. Only their maximum length
matters. Security does *not* drop as you send more messages. You can
send as many messages as you want.

I speculate (but don't know) that it might be because unlike GCM, the
secret multiplier is not reused across messages. (AES GCM could have
done the same, but it would have meant computing 2 additional blocks
per message instead of just one.)

The security bounds given by DJB's Poly1305 paper say that it was
designed this way specifically to preserve security as we send more
messages. Only message length matters. This is shown again in the
current AEAD limits draft:

   v = number of attempts
   p = target adversary attack probability
   l = maximum message length (in blocks)
   u = number of users or keys (multi-key attack)

   v <= (p * 2^103) / (l * u)

The biggest possible messages with a 64-bit counter would be 2^68
blocks (we have 4 Poly1305 blocks per Chacha20 block). So:

   v <= (p * 2^103) / (2^68 * u)
   v <= (p * 2^35) / u

That's the theoretical limit, though.  One does not simply encrypt 2^70
bytes in one block (my laptop barely exceeds 2^32 bytes per second).
More realistic (yet unreasonable) length would be in the Terabyte
range. With 8TiB, we'd have 2^43 bytes, or 2^39 blocks:

   v <= (p * 2^103) / (2^39 * u)
   v <= (p * 2^64) / u

Inadvisable for sure, but not broken either. Stream repetition would be
many orders of magnitude worse. In my opinion, the fact that short
messages are better does not justify breaking all security for long
messages. I'd sooner specify that applications "MUST" crash if the
input message is bigger than some threshold.

Loup.