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

[Taylor R Campbell <[e-mail]>]

> Date: Sat, 26 Dec 2020 20:59:21 +0100
> From: Loup Vaillant-David <[e-mail]>
> 
> 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.

The probability of each forgery attempt's success _independently_ is
bounded by 8*floor(L/16)/2^106, where L is the maximum message length.

If the adversary makes q forgery attempts, then the probability of
succeeding at _any_ forgery is bounded by q*8*floor(L/16)/2^106.

Note that both the number of forgery attempts _and_ the maximum
message length figure into this bound.

References:
https://cr.yp.to/highspeed/naclcrypto-20090310.pdf#page=30
https://eprint.iacr.org/2014/613.pdf#page=4

> 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.)

ChaCha/Poly1305 and AES-GCM are no different in this respect: for
fixed number of messages and total bytes encrypted, the forgery
probability is proportional to q/L for both of them, with a different
constant factor arising from differences in Poly1305 and GHASH.

Using a message sequence number as the nonce so you can quickly reject
outdated message numbers mitigates the issue for ChaCha/Poly1305, for
the reason you describe.  But that's not as relevant for XChaCha,
which is meant for applications where you may not have a reliable
message sequence number.

They also do scale differently in the number messages and total bytes:
AES-GCM is quadratic where ChaCha/Poly1305 is linear, because AES-GCM
is held back by AES as a PRP.  I attempted to sketch the qualitative
differences in this table in the Daence paper:

https://eprint.iacr.org/2020/067.pdf#page=5
source code: https://github.com/riastradh/daence/blob/master/adv.py

(Daence guarantees the adversary's advantage is below 1/2^32 per key
as long as you process at most 2^52 messages of at most 2^38 bytes
under each key, even if you manage to attain _both_ limits at the same
time for a single key.  I chose this so the usage limits wouldn't have
to be explained by a complicated series of tables and prose like
AES-GCM-SIV's <https://tools.ietf.org/html/rfc8452#page-12>.)

> 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.

No objection to making the XChaCha draft clearer about what the hard
limit is.  I am a big fan of clearly articulated usage limits.