Subject: [TLS] Data Volume Limits Analysis

From: aluykx <[email-masked]>
Date: Tue, 08 Mar 2016 14:16:04 -0800

Kenny Paterson and I prepared a document providing an overview of how 
much data ChaCha20+Poly1305 and AES-GCM can process with a single key. 
Besides summarizing the results, the document also gives an explanation 
of why the limits are there. The document confirms the analysis done by 
Watson and others in the thread on "Data Volume Limits", but goes into 
more detail.

The document can be found on Kenny's website:
http://www.isg.rhul.ac.uk/~kp/TLS-AEbounds.pdf

Atul Luykx

---

From: Eric Rescorla <[email-masked]>
Date: Sun, 20 Mar 2016 16:40:17 -0700

Atul, Kenny,

Thanks for doing this. My initial impression is that these results are
uncomfortably
close to the line for AES-GCM, especially for the scenario where we have
multiple
keys: there are probably well upward of 2^{32} HTTPS connections a day.

 A few questions:

1. As I understand it, failure in these models is fairly catastrophic,
so I should be reading Table 1 as "chance of total collapse of
confidentiality",
not "chance of being able to read one plaintext" value. Is that correct?

2. Are there available proofs for a non-chosen plaintext context? This seems
to bear on the multiple key question: it seems plausible that an attacker
could
capture a very large number of AES-GCM encrypted connections passively,
but collecting a huge number of AES-GCM connections where it gets to
specify the plaintexts seems more challenging, even with BEAST-style
attacks.

3. Naively, from equation 5, it seems like as \sigma >> q you should be able
to encrypt rather more submaximal (e.g., 1K) records than maximal size
records.

Finally, and this calls for an opinion: do you believe that given these
results
we should include a KeyUpdate feature in TLS 1.3?

Thanks,
-Ekr

On Tue, Mar 8, 2016 at 2:16 PM, aluykx <[email-masked]> wrote:

> Kenny Paterson and I prepared a document providing an overview of how much
> data ChaCha20+Poly1305 and AES-GCM can process with a single key. Besides
> summarizing the results, the document also gives an explanation of why the
> limits are there. The document confirms the analysis done by Watson and
> others in the thread on "Data Volume Limits", but goes into more detail.
>
> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls
>

---

From: aluykx <[email-masked]>
Date: Wed, 23 Mar 2016 09:11:43 +0100

Hey,

> not "chance of being able to read one plaintext" value. Is that 

Actually, confidentiality will not collapse, the limit indicates the 
moment when information starts leaking, which could start off as little 
as one bit of plaintext. The bigger issue is when integrity fails. For 
AES-GCM this could lead to the integrity key being recovered, allowing 
adversaries to forge TLS records (though to do so for chosen plaintext 
messages needs a bit more adversarial capability - essentially, enough 
contiguous known plaintext at the start of a record for some TLS 
sequence number).

> to bear on the multiple key question: it seems plausible that an
> attacker could

As far as we know, there are no non-chosen plaintext proofs, however, 
the bounds do not improve when only considering known-plaintext attacks. 
Also, analysis where the adversary only sees ciphertext is not very 
realistic since in practice one can always deduce something about the 
plaintext.

> to encrypt rather more submaximal (e.g., 1K) records than maximal size

If \sigma >> q, this means you've processed many long records. Switching 
to short records will allow you to process more of them, although the 
amount of data you can process will not change.

> we should include a KeyUpdate feature in TLS 1.3?

Ideally it would be better to include a KeyUpdate feature, but the added 
complexity could risk introducing vulnerabilities worse than what 
happens when the bounds are not respected, since all of these attacks 
require adversaries to monitor large amounts of data. If KeyUpdate is 
simple, then include it, but otherwise it might not be worth the risk.

Kenny and Atul

On 2016-03-21 00:40, Eric Rescorla wrote:
> close to the line for AES-GCM, especially for the scenario where we
> have multiple
> to bear on the multiple key question: it seems plausible that an
> attacker could
> Finally, and this calls for an opinion: do you believe that given
> these results
>> Kenny Paterson and I prepared a document providing an overview of
>> how much data ChaCha20+Poly1305 and AES-GCM can process with a
>> single key. Besides summarizing the results, the document also gives
>> an explanation of why the limits are there. The document confirms
>> the analysis done by Watson and others in the thread on "Data Volume
>> Limits", but goes into more detail.
>>

---

From: Aaron Zauner <[email-masked]>
Date: Wed, 23 Mar 2016 11:46:59 +0100

* aluykx <[email-masked]> [23/03/2016 09:12:02] wrote:
> complexity could risk introducing vulnerabilities worse than what happens
> when the bounds are not respected, since all of these attacks require
> adversaries to monitor large amounts of data. If KeyUpdate is simple, then
> include it, but otherwise it might not be worth the risk.

Thinking about this a bit before I read your reply, I came to the
same conclusion. It could be useful if it's well done and
implementations update securely. But that's hard :)

Aaron