Subject: [TLS] AES-GCM and ChaCha-Poly1305: how many bytes are safe?

From: Watson Ladd <[email-masked]>
Date: Mon, 2 Nov 2015 09:27:52 -0500

Dear all,

All modes have a limit on how much data can be encrypted before bad
things start to happen, i.e. IND-$ becoming false, or authenticity
becoming false. In this email I will discuss what those limits are for
AES-GCM and ChaCha20-Poly1305, assuming the usual assumptions about
the ciphers: that is PRP for AES and PRF for ChaCha20. These limits
are due to Iwata et. al. and Bernstein. All I have done in this email
is evaluate them carefully.

We start by noting that TLS encrypts messages of at most 2^14 bytes,
and so at most 2^16 16-byte blocks. This is a ridiculous overestimate,
but it doesn't need to be tightened, as I will explain later.

Bernstein proves general results on Carter-Wegman authenticators,
found in http://cr.yp.to/papers.html#securitywcs. For these results a
sender of 2^60 messages can tolerate 2^60 forgery attempts while the
probability of forgery is at most 1.002/2^52. I think that's
sufficient. These apply to AES-GCM. For ChaCha20-Poly1305 there is a
different result where the number of messages does not appear, but
only the length: this result gives a much stronger 1/2^87. This is due
to generating a different authentication key for every nonce.

ChaCha20 is a PRF. As a result we can go beyond the birthday bound,
and send use all 2^96 messages.

AES is a PRP. Therefore there is a quadratic security loss, and the
result from Iwata-Ohashai-Minematsu states the probability of success
is upper bounded by (s+q+1)^2/2^127, where s is the total number of
blocks encrypted and q the number of queries made by the attacker. The
sum must therefore be below 2^32 to have the same level of security as
the authenticator, and so we are limited to a total amount of
encryption with a given key of 2^32 blocks, or 2^36 bytes. We could be
slightly more aggressive, but cannot hit anywhere close to 2^64.

Please double-check the above analysis, in particular the assumptions
about how ChaCha20-Poly1305 actually works.  I haven't dug up other
recommendations to see if I got in the right ballpark.

Sincerely,
Watson

---

From: Brian Smith <[email-masked]>
Date: Mon, 2 Nov 2015 09:59:31 -1000

Watson Ladd <[email-masked]> wrote:

> For these results a
> probability of forgery is at most 1.002/2^52.

TLS only allows one forgery attempt per connection (thus per key). That is,
as soon as a TLS implementation fails to verify a record's authentication
tag, it must shut down the connection. Thus, it would be more useful to
state the analysis as "Observing X signed records over Y bytes increases
the odds of the attacker forging the next record to Z."

Cheers,
Brian
-- 
https://briansmith.org/

---

From: Yoav Nir <[email-masked]>
Date: Tue, 3 Nov 2015 07:25:07 +0900

> On 3 Nov 2015, at 4:59 AM, Brian Smith <[email-masked]> wrote:
> 
> Watson Ladd <[email-masked] <mailto:[email-masked]>> wrote:
> For these results a
> TLS only allows one forgery attempt per connection (thus per key). That is, as soon as a TLS implementation fails to verify a record's authentication tag, it must shut down the connection. Thus, it would be more useful to state the analysis as "Observing X signed records over Y bytes increases the odds of the attacker forging the next record to Z.”

That is true for TLS, but not for DTLS, so I guess we have to state it both ways.

Yoav