Subject: [TLS] Data volume limits

From: Eric Rescorla <[email-masked]>
Date: Tue, 15 Dec 2015 13:14:30 -0800

Watson kindly prepared some text that described the limits on what's safe
for AES-GCM and restricting all algorithms with TLS 1.3 to that lower
limit (2^{36} bytes), even though ChaCha doesn't have the same
restriction.

I wanted to get people's opinions on whether that's actually what we want
or whether we should (as is my instinct) allow people to use ChaCha
for longer periods.

-Ekr

---

From: Eric Rescorla <[email-masked]>
Date: Tue, 15 Dec 2015 13:15:33 -0800

For context, see:
https://github.com/tlswg/tls13-spec/pull/372

---

From: Watson Ladd <[email-masked]>
Date: Tue, 15 Dec 2015 16:17:34 -0500

I don't think that's what I intended: I think the limit should be
ciphersuite specific. Unfortunately that requires more work.

On Tue, Dec 15, 2015 at 4:15 PM, Eric Rescorla <[email-masked]> wrote:
> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls
>

-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.

---

From: Eric Rescorla <[email-masked]>
Date: Tue, 15 Dec 2015 13:18:43 -0800

> ciphersuite specific. Unfortunately that requires more work.

That makes sense. Do you think you'll be able to provide that in the not
too distant future? I can just leave this on ice till then...

-Ekr

---

From: Dave Garrett <[email-masked]>
Date: Tue, 15 Dec 2015 16:25:46 -0500

Personally, I think a hard requirement to rekey every 64GiB is reasonable enough to just use it for every cipher. I don't think cipher-specific requirements are worth the effort/complexity. Something like a MUST for AES-GCM and a SHOULD for ChaCha seems fine, though, if really desired.

Dave

---

From: Benjamin Beurdouche <[email-masked]>
Date: Tue, 15 Dec 2015 22:27:09 +0100

> On 15 Dec 2015, at 22:17, Watson Ladd <[email-masked]> wrote:
> 

IMHO, if we differentiate the limit depending on the ciphersuite, it will be more complex to handle and cause problems at some point.
I would rather have a single value in the spec that is safe for all allowed ciphersuites, rekey more frequently and leave people take their own risks by setting higher limits if they do not negotiate AES-GCM (for example).

B.

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Tue, 15 Dec 2015 22:01:52 +0000

Might I enquire about the cryptographical reason behind such a limit?

Is this the limit on the size of a single record?  GCM does have a limit approximately there on the size of a single plaintext it can encrypt.  For TLS, it encrypts a record as a single plaintext, and so this would apply to extremely huge records.

Or is this a limit on the total amount of traffic that can go through a connection over multiple records?  If this is the issue, what is the security concern that you would have if that limit is exceeded?

Thank you.

From: TLS [mailto:[email-masked]] On Behalf Of Eric Rescorla
Sent: Tuesday, December 15, 2015 4:15 PM
To: [email-masked]
Subject: [TLS] Data volume limits

-Ekr

---

From: Eric Rescorla <[email-masked]>
Date: Tue, 15 Dec 2015 14:08:02 -0800

On Tue, Dec 15, 2015 at 2:01 PM, Scott Fluhrer (sfluhrer) <
[email-masked]> wrote:

> Is this the limit on the size of a single record?  GCM does have a limit
> approximately there on the size of a single plaintext it can encrypt.  For
> TLS, it encrypts a record as a single plaintext, and so this would apply to
> extremely huge records.
>
>
>
> Or is this a limit on the total amount of traffic that can go through a
> connection over multiple records?  If this is the issue, what is the
> security concern that you would have if that limit is exceeded?
>

Watson provided these, so perhaps he can elaborate.

It would be good to have a value we all agree on.

Thanks,
-Ekr

>
> Thank you.
>
>
>
> *From:* TLS [mailto:[email-masked]] *On Behalf Of *Eric Rescorla
> *Sent:* Tuesday, December 15, 2015 4:15 PM
> *To:* [email-masked]
> *Subject:* [TLS] Data volume limits
>
>
>

---

From: Russ Housley <[email-masked]>
Date: Tue, 15 Dec 2015 17:18:35 -0500

> or whether we should (as is my instinct) allow people to use ChaCha

Perhaps the algorithm registration can provide the limit, allowing implementations use the full period for each algorithm.

Russ

---

From: Watson Ladd <[email-masked]>
Date: Tue, 15 Dec 2015 17:28:04 -0500

> Perhaps the algorithm registration can provide the limit, allowing implementations use the full period for each algorithm.

That makes sense, but people might ignore these values in the
registry, and the entries might not be reviewed as well as they should
be compared to if they are in the relevant RFCs.

---

From: Hanno Böck <[email-masked]>
Date: Tue, 15 Dec 2015 23:36:39 +0100

On Tue, 15 Dec 2015 13:14:30 -0800
Eric Rescorla <[email-masked]> wrote:

> Watson kindly prepared some text that described the limits on what's
> safe for AES-GCM and restricting all algorithms with TLS 1.3 to that
> lower limit (2^{36} bytes), even though ChaCha doesn't have the same
> restriction.
> 
> I wanted to get people's opinions on whether that's actually what we
> want or whether we should (as is my instinct) allow people to use
> ChaCha for longer periods.

Let me state the opinion that unlikely will get adopted: Isn't that a
good reason to reconsider whether GCM is a good mode in the first place?

How about: Let's use chacha20, let's not set any limits because we don't
have to, let's deprecate algorithms that can't keep up with that?

(I generally think even TLS 1.3 deprecates a lot of stuff there is
still far too much variation. Let's keep things simpler, let's reduce
the algorithm zoo.)

-- 
Hanno Böck
http://hboeck.de/

mail/jabber: [email-masked]
GPG: BBB51E42

---

From: Watson Ladd <[email-masked]>
Date: Tue, 15 Dec 2015 17:38:23 -0500

> TLS, it encrypts a record as a single plaintext, and so this would apply to

The issue is the bounds in Iwata-Ohashai-Minematsu's paper, which show
a quadratic confidentiality loss after a total volume sent. This is an
exploitable issue.

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Tue, 15 Dec 2015 23:08:17 +0000

> -----Original Message-----
> From: Watson Ladd [mailto:[email-masked]]
> Sent: Tuesday, December 15, 2015 5:38 PM
> To: Scott Fluhrer (sfluhrer)
> Cc: Eric Rescorla; [email-masked]
> Subject: Re: [TLS] Data volume limits
> 
> > Is this the limit on the size of a single record?  GCM does have a
> > limit approximately there on the size of a single plaintext it can
> > encrypt.  For TLS, it encrypts a record as a single plaintext, and so
> > this would apply to extremely huge records.
> 
> The issue is the bounds in Iwata-Ohashai-Minematsu's paper, which show a
> quadratic confidentiality loss after a total volume sent. This is an exploitable
> issue.

Actually, the main result of that paper was that GCM with nonces other than 96 bits were less secure than previous thought (or, rather, that the previous proofs were wrong, and what they can prove is considerably worse; whether their proof is tight is an open question).  They address 96 bit nonces as well, however the results they get are effectively unchanged from the original GCM paper.  I had thought that TLS used 96 bit nonces (constructed from 32 bit salt and a 64 bit counter); were the security guarantees from the original paper too weak?  If not, what has changed?

The quadratic behavior in the security proofs are there for just about any block cipher mode, and is the reason why you want to stay well below the birthday bound.  However, that's as true for (say) CBC mode as it is for GCM

---

From: Watson Ladd <[email-masked]>
Date: Tue, 15 Dec 2015 18:47:57 -0500

On Dec 15, 2015 6:08 PM, "Scott Fluhrer (sfluhrer)" <[email-masked]>
wrote:
> Actually, the main result of that paper was that GCM with nonces other
than 96 bits were less secure than previous thought (or, rather, that the
previous proofs were wrong, and what they can prove is considerably worse;
whether their proof is tight is an open question).  They address 96 bit
nonces as well, however the results they get are effectively unchanged from
the original GCM paper.  I had thought that TLS used 96 bit nonces
(constructed from 32 bit salt and a 64 bit counter); were the security
guarantees from the original paper too weak?  If not, what has changed?
>
> The quadratic behavior in the security proofs are there for just about
any block cipher mode, and is the reason why you want to stay well below
the birthday bound.  However, that's as true for (say) CBC mode as it is
for GCM

That's correct. And when we crunch the numbers assuming 2^60 is negligible
out comes 2^36 bytes. This doesn't hold for ChaCha20.

---

From: Eric Rescorla <[email-masked]>
Date: Tue, 15 Dec 2015 15:48:10 -0800

On Tue, Dec 15, 2015 at 3:08 PM, Scott Fluhrer (sfluhrer) <
[email-masked]> wrote:

> (constructed from 32 bit salt and a 64 bit counter);

TLS 1.3 uses a 96-bit nonce constructed by masking the counter with a random
value.

were the security guarantees from the original paper too weak?  If not,
> what has changed?
>
> The quadratic behavior in the security proofs are there for just about any
> block cipher mode, and is the reason why you want to stay well below the
> birthday bound.

The birthday bound here is 2^{64}, right?

-Ekr

>   However, that's as true for (say) CBC mode as it is for GCM
>
>

---

From: Brian Smith <[email-masked]>
Date: Tue, 15 Dec 2015 14:00:44 -1000

> a quadratic confidentiality loss after a total volume sent. This is an

Please explain in more detail how you got "2^36 bytes" for a nonce size of
96 bits from the Iwata-Ohashai-Minematsu paper [1].

[1] https://eprint.iacr.org/2012/438.pdf

Also, the Niwa-Ohashi-Minematsu-Iwata follow-up paper [2] change things in
any way? In particular, note that it concludes "The new security bounds
improve the security bounds in [11] by a factor of 2^17, and they show that
the security of GCM is actually close to what was originally claimed in
[17,18]."

A factor of 2^17 difference is pretty significant as far as this is
concerned, AFAICT.

[2] https://eprint.iacr.org/2015/214.pdf

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

---

From: Henrick Hellström <[email-masked]>
Date: Wed, 16 Dec 2015 01:08:54 +0100

On 2015-12-16 00:48, Eric Rescorla wrote:
>
>
> On Tue, Dec 15, 2015 at 3:08 PM, Scott Fluhrer (sfluhrer)
> <[email-masked] <mailto:[email-masked]>> wrote:
>     The quadratic behavior in the security proofs are there for just
>     about any block cipher mode, and is the reason why you want to stay
>     well below the birthday bound.
>
>

Actually, no.

Using the sequence number as part of the effective nonce, means that it 
won't collide. There is no relevant bound for collisions in the nonces 
or in the CTR state, because they simply won't happen (unless there is 
an implementation flaw). There won't be any potentially exploitable 
collisions.

However, theoretically, the GHASH state might collide with a 2^{64} 
birthday bound. This possibility doesn't seem entirely relevant, though.

---

From: Watson Ladd <[email-masked]>
Date: Tue, 15 Dec 2015 19:31:04 -0500

> Using the sequence number as part of the effective nonce, means that it
won't collide. There is no relevant bound for collisions in the nonces or
in the CTR state, because they simply won't happen (unless there is an
implementation flaw). There won't be any potentially exploitable collisions.

You don't understand the issue. The issue is PRP not colliding, whereas PRF
can.

---

From: Andrey Jivsov <[email-masked]>
Date: Tue, 15 Dec 2015 16:39:45 -0800

On 12/15/2015 04:08 PM, Henrick Hellström wrote:
 > Using the sequence number as part of the effective nonce, means that 
it won't collide. There is no relevant bound for collisions in the 
nonces or in the CTR state, because they simply won't happen (unless 
there is an implementation flaw). There won't be any potentially 
exploitable collisions.

Here is one attack that exploits such a collision 
https://www.ietf.org/mail-archive/web/openpgp/current/msg08345.html

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Wed, 16 Dec 2015 00:46:46 +0000

> From: TLS [mailto:[email-masked]] On Behalf Of Henrick Hellström
> Sent: Tuesday, December 15, 2015 7:09 PM
> To: [email-masked]
> won't collide. There is no relevant bound for collisions in the nonces or in the
> CTR state, because they simply won't happen (unless there is an
> However, theoretically, the GHASH state might collide with a 2^{64} birthday
> bound. This possibility doesn't seem entirely relevant, though.

That is a good point, and deserves to be examined more.

With CBC mode, there's a probability that two different ciphertext blocks will happen to be identical; when that unlikely event happens, the attacker can determine the bitwise difference between the corresponding plaintext blocks (and thereby leak a small amount of plaintext)

This doesn't happen with GCM.  Instead, the distinguisher is of this form: the attacker with a potential plaintext can compute the internal CTR values for GCM; if he sees a duplicate value, he can deduce that that potential plaintext wasn't the real one (because the internal CTR values never repeat).

Assuming that they cannot distinguish AES with a random key from a random permutation, that's the only thing they can learn.

That is, when they prove that there is no distinguisher with better than 2^{-64} advantage, what they are referring to (in practice) is that the attacker could eliminate a tiny fraction (1 out of 2^{64}) of the possible plaintexts; they gain no more information than that.

---

From: Henrick Hellström <[email-masked]>
Date: Wed, 16 Dec 2015 01:59:32 +0100

On 2015-12-16 01:31, Watson Ladd wrote:
> You don't understand the issue. The issue is PRP not colliding, whereas
> PRF can.

Oh, but I concur. This means that if you observe two same valued cipher 
text blocks, you know that the corresponding key stream blocks can't be 
identical, and deduce that the corresponding plain text blocks have to 
be different. Such observations consequently leak information about the 
plain text, in the rare and unlikely event they actually occur.

However, calling it an exploitable weakness is a bit of a stretch. 
AES-CBC is likely to loose confidentiality slightly faster, for typical 
plain texts.

---

From: Martin Thomson <[email-masked]>
Date: Wed, 16 Dec 2015 13:40:41 +1100

> or whether we should (as is my instinct) allow people to use ChaCha

Whatever the actual limits are, I think that implementatios should be
encouraged to rekey more strongly.

If 2^36 is the number, then I can see that being reached in some
applications.  That means that we need the rekey feature to exist.  If
we are going to have that feature, then we need to make sure that it
works.  And suggesting a stupidly high limit (e.g., ChaCha being
greater than 2^96) leaves people thinking that they can skip
implementation and testing of the rekey facility; or it just goes
unused.  If it's not in use, then we'll have a good chance of creating
a protocol feature we can't rely on if it really is needed.

In light of that, the actual limits don't matter that much to me.  As
David McGrew suggested, set a limit at 2^32 and avoid having to think
too hard about how close to the failure point you might be.

---

From: Brian Smith <[email-masked]>
Date: Tue, 15 Dec 2015 17:01:33 -1000

> encouraged to rekey more strongly.

Why?

> And suggesting a stupidly high limit (e.g., ChaCha being

I think this is exactly why the limit matters. If we are not in danger of
reaching the limit, then we don't need the rekeying mechanism and it should
be removed. The rekeying mechanism adds considerable complexity and that
complexity needs to be justified.

Alternatively, we'd need a new justification for the rekeying mechanism.
The new justification would affect the design of the rekeying mechanism.
For example, if the purpose of the rekeying mechanism is to get similar
effects to, say, the Axolotl ratchet, then we should ensure that the
rekeying mechanism actually has similar properties to Axolotl.

> too hard about how close to the failure point you might be.

First, let's figure out why TLS 1.3 needs a rekeying mechanism, if it does.
Then we can figure out how frequently we should suggest rekeying occur
based on sound reasoning.

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

---

From: Martin Thomson <[email-masked]>
Date: Wed, 16 Dec 2015 14:24:21 +1100

> Martin Thomson <[email-masked]> wrote:

If there were a stupidly high limit, then I would argue for no
rekeying facility.

But the numbers Watson ran suggested that GCM starts to look shaky at
2^36.  That's too low for some applications.

For the rest of the argument I suggest you reread my last mail.

---

From: Eric Rescorla <[email-masked]>
Date: Tue, 15 Dec 2015 19:28:53 -0800

On Tue, Dec 15, 2015 at 4:59 PM, Henrick Hellström <[email-masked]>
wrote:

> identical,

That assumes that the plaintext is identical, no? That may be true in some
limited
cases, but isn't generally true

-Ekr

and deduce that the corresponding plain text blocks have to be different.
> Such observations consequently leak information about the plain text, in
> the rare and unlikely event they actually occur.
>
> However, calling it an exploitable weakness is a bit of a stretch. AES-CBC
> is likely to loose confidentiality slightly faster, for typical plain texts.
>
>

---

From: Watson Ladd <[email-masked]>
Date: Tue, 15 Dec 2015 22:36:01 -0500

On Tue, Dec 15, 2015 at 7:59 PM, Henrick Hellström <[email-masked]> wrote:
> Oh, but I concur. This means that if you observe two same valued cipher text
> blocks, you know that the corresponding key stream blocks can't be
> identical, and deduce that the corresponding plain text blocks have to be
> different. Such observations consequently leak information about the plain
> text, in the rare and unlikely event they actually occur.
>

The problem is that once you stack enough of those negligible
probabilities together, you end up with something big. Push up to
2^{63} bytes, and the collision probability is 1/4 or 1/2 (I didn't
recompute it just now). And while the definition seems to involve only
a minor loss of security, that's the definition people use for
security.

Using 2^{-64} as a success probability ensures that attackers who can
exploit multiple connections are still defended against. Could we do
better with 2^{-32}? Sure. But at this point we're saying you can
transport over 16 Gbyte of data before rekeying: I think that's enough
for almost all purposes.

---

From: Stephen Farrell <[email-masked]>
Date: Wed, 16 Dec 2015 03:42:47 +0000

Hi Watson,

On 16/12/15 03:36, Watson Ladd wrote:
> recompute it just now). 

The collision probability of... what? (For that to be 0.50
my gut tells me it's something that's really not at all
likely to be worrisome, but I know I'm not expert here hence
me asking:-)

Thanks,
S.

---

From: Dave Garrett <[email-masked]>
Date: Tue, 15 Dec 2015 22:57:01 -0500

> too hard about how close to the failure point you might be.

+1

In fact, if we're OK with setting this rather low threshold, then we could even get rid of the rekey signal entirely and just have an automatic rekey after every 4GiB for all ciphers. That'd be one less complexity to deal with. Rekeys would be routine.

Dave

---

From: Martin Thomson <[email-masked]>
Date: Wed, 16 Dec 2015 14:59:35 +1100

> In fact, if we're OK with setting this rather low threshold, then we could even get rid of the rekey signal entirely and just have an automatic rekey after every 4GiB for all ciphers. That'd be one…

I don't like automatic rekey (though I almost like the per-record
rekeying that I think was semi-facetiously suggested by someone).  An
explicit rekey allows for two things:
 - testing
 - reducing the limit if we find that the cipher is more busted than
we originally thought (with respect to key overuse)

---

From: Bill Frantz <[email-masked]>
Date: Tue, 15 Dec 2015 20:01:58 -0800

So we have to trade off the risks of too much data vs. the risks 
of a complex rekey protocol vs. the risks having the big data 
applications build new connections every 2**36 or so bytes.

If we don't have rekeying, then the big data applications are 
the only ones at risk. If we do, it may be a wedge which can 
compromise all users.

Cheers - Bill

-------------------------------------------------------------------------
Bill Frantz        | Re: Hardware Management Modes: | Periwinkle
(408)356-8506      | If there's a mode, there's a   | 16345 
Englewood Ave
www.pwpconsult.com | failure mode. - Jerry Leichter | Los Gatos, 
CA 95032

---

From: Eric Rescorla <[email-masked]>
Date: Tue, 15 Dec 2015 20:01:41 -0800

On Tue, Dec 15, 2015 at 7:59 PM, Martin Thomson <[email-masked]>
wrote:

> > In fact, if we're OK with setting this rather low threshold, then we
> could even get rid of the rekey signal entirely and just have an automatic
> rekey after every 4GiB for all ciphers. That'd be one less complexity to
> deal with. Rekeys would be routine.
>

Also, allows each side to have their own opinion.

Not a fan of automatic rekey.

-Ekr

---

From: Dave Garrett <[email-masked]>
Date: Tue, 15 Dec 2015 23:08:08 -0500

> Also, allows each side to have their own opinion.

We could just make the threshold a configurable parameter, with default/maximum at 2^32 bytes. Each endpoint could just provide its threshold in a new extension. Both get to specify what they want and it could be lowered arbitrarily for testing or panic fix.

Dave

---

From: Martin Thomson <[email-masked]>
Date: Wed, 16 Dec 2015 15:11:36 +1100

> We could just make the threshold a configurable parameter, with default/maximum at 2^32 bytes. Each endpoint could just provide its threshold in a new extension. Both get to specify what they want…

That sounds more complex than the current option.

---

From: Dave Garrett <[email-masked]>
Date: Tue, 15 Dec 2015 23:19:13 -0500

> That sounds more complex than the current option.

It's the difference between one signal in the handshake followed by predictable rekeying and an arbitrary number of signals at arbitrary points after the handshake.

Dave

---

From: Andrey Jivsov <[email-masked]>
Date: Tue, 15 Dec 2015 22:39:10 -0800

On 12/15/2015 03:47 PM, Watson Ladd wrote:
>
>
> On Dec 15, 2015 6:08 PM, "Scott Fluhrer (sfluhrer)" 
> > > From: Watson Ladd [mailto:[email-masked] 
> <mailto:[email-masked]>]
> > > Cc: Eric Rescorla; [email-masked] <mailto:[email-masked]>
> > Actually, the main result of that paper was that GCM with nonces 
> other than 96 bits were less secure than previous thought (or, rather, 
> that the previous proofs were wrong, and what they can prove is 
> considerably worse; whether their proof is tight is an open 
> question).  They address 96 bit nonces as well, however the results 
> they get are effectively unchanged from the original GCM paper.  I had 
> thought that TLS used 96 bit nonces (constructed from 32 bit salt and 
> a 64 bit counter); were the security guarantees from the original 
> paper too weak?  If not, what has changed?
> >
> well below the birthday bound.  However, that's as true for (say) CBC 
> mode as it is for GCM
>
> That's correct. And when we crunch the numbers assuming 2^60 is 
> negligible out comes 2^36 bytes. This doesn't hold for ChaCha20.
>

If 2^36 above is about confidentiality, I am getting q<2^34, assuming 
probability of a collision lower than p=2^-60.

2^34*(2^34-1) <  (2^(128-60))/0.316 (that's the formula with 'e', not 
C(q,2)).

q=2^34 blocks is 2^38 bytes (256 GiB). Close enough, although p=2^-60 
could have been higher for higher total bytes before rekey.

---

From: Simon Josefsson <[email-masked]>
Date: Wed, 16 Dec 2015 09:44:18 +0100

> limit (2^{36} bytes), even though ChaCha doesn't have the same

Can we see a brief writeup explaining the 2^36 number?

I don't like re-keying.  It is usually a sign that your primitives are
too weak and you are attempting to hide that fact.  To me, it is similar
to discard the first X byte of RC4 output.

If AES-GCM cannot provide confidentiality beyond 64GB (which would
surprise me somewhat), I believe we ought to be careful about
recommending it.

Of course, the devil is in the details: if the risk is that the secret
key is leaked, that's fatal; if the risk is that the attacker can tell
whether two particular plaintext 128 byte blocks are the same or not in
the entire file, that can be a risk we can live with (similar to the
discard X bytes of RC4 fix).

I believe 64GB is within the range that people download in a web browser
these days.  More data intensive longer-running protocols often transfer
significantly more.

/Simon

---

From: Eric Rescorla <[email-masked]>
Date: Wed, 16 Dec 2015 03:17:56 -0800

> Can we see a brief writeup explaining the 2^36 number?

I believe Watson provided one a while back at:
https://www.ietf.org/mail-archive/web/tls/current/msg18240.html

> to discard the first X byte of RC4 output.

To be clear: I would prefer not to rekey either, but the consensus at IETF
Yokohama
was that we were close enough to the limit that we probably had to. Would be
happy to learn that we didn't.

-Ekr

---

From: Henrick Hellström <[email-masked]>
Date: Wed, 16 Dec 2015 13:07:30 +0100

> https://www.ietf.org/mail-archive/web/tls/current/msg18240.html

One rather obvious problem with trying to equate probability of loss of 
confidentiality with the advantage for an IND-KPA adversary, is that the 
IND-models don't account for the length of the plain text.

The real life problem is that you lose a lot more information a lot 
faster, by revealing the amount and frequency of the data transfer, than 
through the KPA distinguisher for CTR mode.

And, furthermore, the IND-KPA distinguisher is a fairly well understood 
abstract artifact of CTR mode. It is not obviously relevant to compare 
it to distinguishers for primitives such as RC4, which typically 
indicate that there might be even worse problems.

---

From: Watson Ladd <[email-masked]>
Date: Wed, 16 Dec 2015 07:11:10 -0500

On Wed, Dec 16, 2015 at 6:17 AM, Eric Rescorla <[email-masked]> wrote:
>> > safe

If you come up with a number for how many bytes we would send
maximally, I can see what the probability of a distinguisher would be.
There are a bunch of places I was sloppy. Personally I think 2^36
bytes over one connection is quite a lot, but it appears that people
are still worried about about this edge case.

Rekeying isn't that complicated conceptually, or from the standpoint
of how to integrate it in. Reauthentication is a lot worse.

---

From: Watson Ladd <[email-masked]>
Date: Wed, 16 Dec 2015 07:13:21 -0500

On Wed, Dec 16, 2015 at 7:07 AM, Henrick Hellström <[email-masked]> wrote:
> The real life problem is that you lose a lot more information a lot faster,
> by revealing the amount and frequency of the data transfer, than through the
> KPA distinguisher for CTR mode.
>
> abstract artifact of CTR mode. It is not obviously relevant to compare it to
> distinguishers for primitives such as RC4, which typically indicate that
> there might be even worse problems.

Sure it is. An attacker can distinguish RC4 from random with a very
high probability (I didn't work it out, but it's an exercise in Bayes
theorem and your favorite biases). I agree this doesn't cover side
channel information related to plaintext length and timing, but there
is a padding facility intended to help with that.

---

From: "Dang, Quynh" <[email-masked]>
Date: Wed, 16 Dec 2015 12:21:51 +0000

Hi Eric,

I explained the issue before and some other people recently explained it again on this thread. AES has 128-bit block. Therefore, when there are 2^64  or more ciphertext blocks, there are likely collisions among the ciphertext blocks (the collision probability increases rapidly when the number of ciphertext blocks increases above 2^64 ( 2^n/2 in generic term) ).

However, the only information the attacker can gain from ANY pair of collided ciphertext blocks is that their corresponding plaintext blocks are probably different ones because the chance for them to be the same is 1/2^128 (1/2^n in generic term) and this is NOT better than a random guess. So, you don't lose anything actually.

As a pseudorandom function, AES completely fails under any mode when the number of ciphertext blocks gets above 2^64.  When the counter is effectively only 64 bits (instead of 96 bits as in TLS 1.3), the data complexity should be below 2^32 blocks because the same input block and the same key can be repeated 2^32 times to find a collision in the ciphertext blocks.  If you want a negligible collision probability, the number of data blocks should be way below 2^32 in this situation.

However, the confidentiality of the plaintext blocks is not lost at all as long as the counter number does not repeat.

Quynh.

________________________________
From: TLS <[email-masked]> on behalf of Eric Rescorla <[email-masked]>
Sent: Wednesday, December 16, 2015 6:17 AM
To: Simon Josefsson
Cc: [email-masked]
Subject: Re: [TLS] Data volume limits

On Wed, Dec 16, 2015 at 12:44 AM, Simon Josefsson <[email-masked]<mailto:[email-masked]>> wrote:

To be clear: I would prefer not to rekey either, but the consensus at IETF Yokohama
was that we were close enough to the limit that we probably had to. Would be
happy to learn that we didn't.

-Ekr

/Simon

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Wed, 16 Dec 2015 15:44:20 +0000

OK, let me try an extremely naïve approach.

Say, an adversary observes a ton of TLS traffic between A and B. Using approach that Watson and others outlined, he can now tell that this is not a truly random stream but a bunch of encrypted data. My question is, from practical real-world point of view - so what? (Of course, beyond the ability to publish a real paper that IND-* has been compromised :)

If there are practical consequences, like loss of confidentiality – I’m dying to hear the outline of a practical attack.
--
Regards,
Uri Blumenthal

From: TLS <[email-masked]<mailto:[email-masked]>> on behalf of "Dang, Quynh" <[email-masked]<mailto:[email-masked]>>
Date: Wednesday, December 16, 2015 at 07:21
To: Eric Rescorla <[email-masked]<mailto:[email-masked]>>, "[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>
Subject: Re: [TLS] Data volume limits

Hi Eric,

Quynh.

________________________________
From: TLS <[email-masked]<mailto:[email-masked]>> on behalf of Eric Rescorla <[email-masked]<mailto:[email-masked]>>
Sent: Wednesday, December 16, 2015 6:17 AM
To: Simon Josefsson
Cc: [email-masked]<mailto:[email-masked]>
Subject: Re: [TLS] Data volume limits

-Ekr

/Simon

---

From: Watson Ladd <[email-masked]>
Date: Wed, 16 Dec 2015 10:50:13 -0500

On Wed, Dec 16, 2015 at 10:44 AM, Blumenthal, Uri - 0553 - MITLL
<[email-masked]> wrote:
> Say, an adversary observes a ton of TLS traffic between A and B. Using
> approach that Watson and others outlined, he can now tell that this is not a
> truly random stream but a bunch of encrypted data. My question is, from
> practical real-world point of view - so what? (Of course, beyond the ability
> to publish a real paper that IND-* has been compromised :)
>
> If there are practical consequences, like loss of confidentiality – I’m
> dying to hear the outline of a practical attack.

The problem is that people design systems assuming something like
indistinguishability. And so when you violate that assumption, all
bets are off.

What is the actual problem with either implementing rekeying, or
limiting data to something like 128 GByte per connection?
> --
> Regards,
> Uri Blumenthal
>
> From: TLS <[email-masked]> on behalf of "Dang, Quynh"
> <[email-masked]>
> To: Eric Rescorla <[email-masked]>, "[email-masked]" <[email-masked]>
>
> I explained the issue before and some other people recently explained it
> again on this thread. AES has 128-bit block. Therefore, when there are 2^64
> or more ciphertext blocks, there are likely collisions among the ciphertext
> blocks (the collision probability increases rapidly when the number of
> ciphertext blocks increases above 2^64 ( 2^n/2 in generic term) ).
>
>
> However, the only information the attacker can gain from ANY pair of
> collided ciphertext blocks is that their corresponding plaintext blocks are
> probably different ones because the chance for them to be the same is
> 1/2^128 (1/2^n in generic term) and this is NOT better than a random guess.
> So, you don't lose anything actually.
>
>
> As a pseudorandom function, AES completely fails under any mode when the
> number of ciphertext blocks gets above 2^64.  When the counter is
> effectively only 64 bits (instead of 96 bits as in TLS 1.3), the data
> complexity should be below 2^32 blocks because the same input block and the
> same key can be repeated 2^32 times to find a collision in the ciphertext
> blocks.  If you want a negligible collision probability, the number of data
> blocks should be way below 2^32 in this situation.
>
>
> However, the confidentiality of the plaintext blocks is not lost at all as
> long as the counter number does not repeat.
>
>
> Quynh.
>
>
>
>
>

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Wed, 16 Dec 2015 17:09:34 +0000

>indistinguishability. And so when you violate that assumption, all

I don’t buy this. AFAIK, TLS has not been designed based on that
assumption. And I’m not making any bets. :)

>limiting data to something like 128 GByte per connection?

As far as I’m concerned - none (no problem). And if there’s a way to
enforce rekeying sooner than that (limiting data-under-one-key to a MUCH
smaller amount) - I’d be in favor of that too. I just don’t accept the
above justification for it - and want to be shown how loss of IND property
in TLS context leads to a practical attack.

---

From: Watson Ladd <[email-masked]>
Date: Wed, 16 Dec 2015 12:16:41 -0500

> assumption. And I’m not making any bets. :)

What security properties does TLS provide? In the past TLS users have
made assumptions that TLS provides security properties it does not.
The solution to this problem is to provide the security properties
that people expect, and they expect IND.

> in TLS context leads to a practical attack.

The practical attack is the loss of IND property. That's the attack.
This is not a weakness in the proven bounds, but a mode limitation.
Since you've agreed we can rekey more frequently

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Wed, 16 Dec 2015 18:14:00 +0000

On 12/16/15, 12:16 , "Watson Ladd" <[email-masked]> wrote:

>What security properties does TLS provide?

When the vast majority of TLS users employ it (TLS), they expect (a) that
TLS would ensure the authenticity of their remote peer, (b) that TLS would
protect their data exchange from being eavesdropped on and/or modified,
and (c) that these hold even when the “enemy” (whoever he might be)
controls the entire communications path between them and their peers.

You can translate the above into more formal definition. :-)

>In the past TLS users have made assumptions that TLS provides security
>properties it does not.

Very true.

>that people expect, and they expect IND.

Not necessarily so.

As far as I’m concerned, IND-* is a good property to have, but not a
“sacred cow”. 

>The practical attack is the loss of IND property. That's the attack.

And how does it translate into a loss of one or more of the above
properties? That’s what people want to hear. If you tell them that an
observer would be able to mathematically distinguish between truly random
data and their encrypted TLS stream (but only after 2^n blocks passed by,
and that’s their risk and exposure) - they’re likely to laugh you out of
the room.

>Since you've agreed we can rekey more frequently

Yes I agree that we can, and probably should. Probably regardless of the
mode used, to keep things simple(r).

---

From: Watson Ladd <[email-masked]>
Date: Wed, 16 Dec 2015 13:19:43 -0500

> As far as I’m concerned, IND-* is a good property to have, but not a

Do you have an alternative definition you can put in and crank and get
the limit out? That's the level of definition at which this sort of
analysis has to be done, not blathering about "confidentiality" and
specific attacks. The reason I used IND-* is that's what the analyses
that have been performed used, because it is defined well enough to do
this.

---

From: Brian Smith <[email-masked]>
Date: Wed, 16 Dec 2015 09:57:43 -1000

> https://www.ietf.org/mail-archive/web/tls/current/msg18240.html

So, if [2] is correct, then we can take Watson's 2^36 and multiply it by
2^17 to get 2^53 bytes as the limit? It seems so, since [2] claims that
they've improved the bounds by 2^17. Note that 3 out of 4 of the authors of
[2] are the same authors as [1], which is the paper that defined the
formula that the 2^36 number was calculated from.

Earlier (in another thread), we agreed that an implementation would not
send 2^48 or more records. A limit of 2^53 bytes would allow for 2^39
maximally-sized (16KB) records, which is not far off from the 2^48
theoretical maximum that the record sequence number allows. More
importantly, 2^53 == 10^15 == 1 petabyte == 1,000,000 gigabytes; I think we
can live with an upper limit of byte sent that is even much smaller than
that.

Therefore, I think we shouldn't add the rekeying mechanism as it is
unnecessary and it adds too much complexity. Also, the above limits apply
to AES-GCM but not ChaCha20-Poly1305. So, at the very least, we should
avoid the rekeying complexity for ChaCha20-Poly1305 and other AEADs that
don't need it. And, implementations that don't intend to send these giant
quantities of data, even with AES-GCM, shouldn't be required, implicitly or
explicitly, to implement the rekeying.

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

---

From: Watson Ladd <[email-masked]>
Date: Wed, 16 Dec 2015 15:00:53 -0500

On Wed, Dec 16, 2015 at 2:57 PM, Brian Smith <[email-masked]> wrote:
> [2] are the same authors as [1], which is the paper that defined the formula
> that the 2^36 number was calculated from.

You need to actually read the papers and understand which formulas are
modified. If you did you would see the improvement is in AES-GCM with
funny nonce sizes, not the confidentiality issue.

>
> Earlier (in another thread), we agreed that an implementation would not send
> 2^48 or more records. A limit of 2^53 bytes would allow for 2^39
> unnecessary and it adds too much complexity. Also, the above limits apply to
> AES-GCM but not ChaCha20-Poly1305. So, at the very least, we should avoid
> the rekeying complexity for ChaCha20-Poly1305 and other AEADs that don't
> need it. And, implementations that don't intend to send these giant

---

From: Brian Smith <[email-masked]>
Date: Wed, 16 Dec 2015 12:26:17 -1000

Watson Ladd <[email-masked]> wrote:

> Brian Smith <[email-masked]> wrote:
> formula

Great. Thank you for pointing out my mistake. First, I'll correct my
mistake in understanding [2]. Then, I'll verify your derivation how we can
get the "2^36 bytes" figure. Lastly, I'll ask whether the initial premise
under which we derived that number is meaningful. In particular, many
people seem to be using a limit of 2^-18 for the attackers
distinguishability advantage to allow (over) 2^48 bytes to be sent, but the
2^36 limit we derived comes from using the number 2^-60 instead. But, is
2^-60 really the right number to use? It seems like we can likely tolerate
a much higher probability of distinguishability. However, it isn't clear
what probability of distinguishability is sufficient. In other words, there
is a tension between the strictness in demanding proof of IND-* security
vs. the simplicity of the protocol (rekeying or now) for AES-GCM. I believe
it is worth asking more cryptographers for help in determining this limit.

First, my mistake in understanding [2]: The improvements to [2] are for
Theorem 1 in [1], which is about AES-GCM in general, for all nonce lengths.
However, [1] also defined Corollary 3 that tightens the bound for the case
where the nonce length is 96 bits, which completely avoids the term with
factor 2^22. So, the 2^17 improvement in [2] for Theorem 1 is not relevant
because we're using Corollary 3, which is already even tighter. Sorry for
wasting people's time with that.

Second, let's go back to how we got 2^36. We used Corollary 3 from [1],
which has this formula:

        0.5(σ + q + 1)^2 / 2^n

We rename σ to s:

        0.5(s + q + 1)^2 / 2^n

substitute n == 128:

        0.5(s + q + 1)^2 / 2^128

and simplify:

        (s + q + 1)^2 / 2^127

we get the formula in Watson's email [3]. In that email, Watson then
claimed that we want to keep this quantity under 2^-60:

        (s + q + 1)^2 / 2^127 < 2^-60.

Simplified:

        (s + q + 1)^2 < 2^67.

Further simplified:

        s + q + 1 < 2^33.5.

So, Watson's point in [3], as I understand it, is that even if we ignore q,
s must be less than 2^32. 2^32 blocks * 2^4 bytes per block = 2^36 bytes in
order to have a proof of IND-* security for AES-GCM, So we'd need to send
2^36 or fewer bytes to have proven IND-* security.

Lastly, let's reconsider Watson's claim in [3] that 1/2^60 is the correct
bound. In [0], the authors wrote: "To provide a concrete example, these
results show that, if AES is indistinguishable from a random permutation,
and fewer than 2^48 packets are protected, then the attacker’s advantage is
no more than 2^−18." This implies that David thought that 2^-18 was a
sufficient bound.

Note that even the conclusion of [1] says that its bounds for the 96-bit
nonce case is tighter than the bounds from the original proof [0]. So, it
seems strange to use [1] to refute the above claim from [0], when in fact
[1] strengthens [0] for the case of 96-nonces, which is what TLS uses.

[0] https://eprint.iacr.org/2004/193.pdf

> > [2] https://eprint.iacr.org/2015/214.pdf

[3] https://www.ietf.org/mail-archive/web/tls/current/msg18240.html

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

---

From: Watson Ladd <[email-masked]>
Date: Wed, 16 Dec 2015 17:33:28 -0500

formula

We've already decided to add a far more complicated support for new
authentication. Reykeyinh is not that complicated.

claimed that we want to keep this quantity under 2^-60:
> So, Watson's point in [3], as I understand it, is that even if we ignore
q, s must be less than 2^32. 2^32 blocks * 2^4 bytes per block = 2^36 bytes
in order to have a proof of IND-* security for AES-GCM, So we'd need to
send 2^36 or fewer bytes to have proven IND-* security.

There are likely to be over 2^40 tls connections globally.

The claim may be true. But I'm saying 2^-18 is insufficient.

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Thu, 17 Dec 2015 09:19:21 +0100

On Wed, 2015-12-16 at 09:57 -1000, Brian Smith wrote:

> unnecessary and it adds too much complexity. 

Any arbitrary limit for a TLS connection is almost guaranteed to cause
problems in the future. We cannot predict whether 2^x should be
sufficient for everyone, and I'm pretty sure this will prove to be a
terrible mistake. TLS is already being used for VPNs and transferring
larger amounts of data in long lived connections is a reality even
today. The rekey today happens using the reauthentication mechanism,
which has very complex semantics. Converting these to a simpler and
predictable rekey mechanism would be an improvement.

regards,
Nikos

---

From: Yoav Nir <[email-masked]>
Date: Thu, 17 Dec 2015 13:07:25 +0200

> On 17 Dec 2015, at 10:19 AM, Nikos Mavrogiannopoulos <[email-masked]> wrote:
> 

Agreed. The alternative to having a rekey mechanism is to push the complexity to the application protocol, requiring it to be able to use more than one connection to transfer all the data, which may require some sort of session layer to maintain state between connections.

So unless we can guarantee or require that every algorithm we are going to use is good for some ridiculous amount of data (2^64 bytes may be enough), we need rekeying.

Yoav

---

From: "Dang, Quynh" <[email-masked]>
Date: Fri, 18 Dec 2015 15:49:36 +0000

The collision probability of ciphertext blocks also depends on the size of the plaintext (record size  in a TLS implementation) in each call of the GCM encryption function.  Let's call each plaintext  to be 2^x 128-bit blocks.

TLS 1.3 uses 96-bit IV. 

If someone wants the collision probability below 1/2^y such as 1/2^24 or 1/2^32 (2^32 = 4,294,967,296 and 2^24 = 16,777,216 ), the total number of plaintext blocks under a given key must be 2^((96 + x - y)/2) or lower.  

So, 2^((96 + x - y)/2) 128-bit blocks are the limit to achieve  IND-* with GCM. 

If someone does not need IND-* property, the above restriction is not needed.

Quynh. 

________________________________________
From: TLS <[email-masked]> on behalf of Yoav Nir <[email-masked]>
Sent: Thursday, December 17, 2015 6:07 AM
To: Nikos Mavrogiannopoulos
Cc: [email-masked]; Simon Josefsson
Subject: Re: [TLS] Data volume limits

Yoav

---

From: Hubert Kario <[email-masked]>
Date: Mon, 21 Dec 2015 13:41:35 +0100

> the only ones at risk. If we do, it may be a wedge which can

if the rekey doesn't allow the application to change authentication 
tokens (as it now stands), then rekey is much more secure than 
renegotiation was in TLS <= 1.2

so if we include rekeying in TLS, I'd suggest to set its limit to 
something fairly low for dig data transfers, that is gigabytes, not 
terabytes, otherwise we'll be introducing code that is simply not tested 
for interoperability

(with AES-NI you can easily transfer gigabytes in just few minutes)
-- 
Regards,
Hubert Kario
Senior Quality Engineer, QE BaseOS Security team
Web: www.cz.redhat.com
Red Hat Czech s.r.o., Purkyňova 99/71, 612 45, Brno, Czech Republic

---

From: Eric Rescorla <[email-masked]>
Date: Mon, 28 Dec 2015 14:54:35 -0500

Scott, Henrick,

Are you persuaded by Watson's analysis?

Thanks,
-Ekr

---

From: Florian Weimer <[email-masked]>
Date: Mon, 28 Dec 2015 21:08:10 +0100

> renegotiation was in TLS <= 1.2

You still have the added complexity that during rekey, you need to
temporarily switch from mere sending or receiving to at least
half-duplex interaction.

Florian

---

From: Eric Rescorla <[email-masked]>
Date: Mon, 28 Dec 2015 15:11:13 -0500

> temporarily switch from mere sending or receiving to at least

That's not intended. Indeed, you need to be able to handle the old key
in order to send/receive the KeyUpdate. Can you elaborate on your concern?

-Ekr

---

From: Florian Weimer <[email-masked]>
Date: Mon, 28 Dec 2015 21:33:00 +0100

> in order to send/receive the KeyUpdate. Can you elaborate on your concern?

Ah, so you want to keep the current mechanism and not inject fresh
randomness?  Isn't this fairly risky?

Florian

---

From: Eric Rescorla <[email-masked]>
Date: Mon, 28 Dec 2015 15:36:36 -0500

> randomness?  Isn't this fairly risky?

Can you explain the risk you are concerned about in more detail?

-Ekr

---

From: "Dang, Quynh" <[email-masked]>
Date: Tue, 29 Dec 2015 12:00:49 +0000

Hi all,

Rekeying too often unnecessarily does not increase any cryptographic security. In addition, it could create other cryptographic issues for the system. The first issue is key collision risk when AES-128 is used and the second issue could be multi-target (multi-key) risk theoretically. 

Therefore, I would suggest not to rekey (as currently specified) too often unnecessarily. 

I think providing a data limit guidance sub-section under the Security Consideration section is one good option to be considered. Users just follow the guidance to set their own data limit(s). 

Quynh. 

________________________________________
From: TLS <[email-masked]> on behalf of Dang, Quynh <[email-masked]>
Sent: Friday, December 18, 2015 10:49 AM
To: [email-masked]
Subject: Re: [TLS] Data volume limits

TLS 1.3 uses 96-bit IV.

Quynh.

Yoav

---

From: Aaron Zauner <[email-masked]>
Date: Fri, 1 Jan 2016 07:35:41 +0100

Hi,

> surprise me somewhat), I believe we ought to be careful about

I unequivocally concur here.

This might be a good time to point again to my existing AES-OCB
draft that hasn't really seen a lot of discussion nor love lately.
It expired but I've recently updated the draft (not yet uploaded
to IETF as I'm waiting for implementer feedback from two particular
sources). The update has something to do with how GCM is implemented
in some stacks though, see:
https://github.com/azet/draft-zauner-tls-aes-ocb/commit/26c2fff7808fc88bf47e5d097f2ff5ca23201029

Aaron

---

From: Aaron Zauner <[email-masked]>
Date: Fri, 1 Jan 2016 08:04:11 +0100

> https://github.com/azet/draft-zauner-tls-aes-ocb/commit/26c2fff7808fc88bf47e5d097f2ff5ca23201029

Having said that, it's probably also a good idea for me to mention
that the OCB designers point out that:
```
[...]

Birthday-bound attacks (as well as good cryptographic hygine)
motivate rekeying well in advance of birthday-bound concerns. In RFC
7253 we say that a given a key should be used to encrypt at most 248
blocks (about 280 terabytes).
``` -- http://web.cs.ucdavis.edu/~rogaway/ocb/ocb-faq.htm#ferguson

Aaron

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 1 Jan 2016 09:23:31 +0200

> ``` -- http://web.cs.ucdavis.edu/~rogaway/ocb/ocb-faq.htm#ferguson

On topic of existing recomendations, SECSH recommends rekeying after
2^32 blocks (64GB) with 128-bit block ciphers like AES[1].

This is obviously a lot more conservative than the above quoted
recommendation.

Also, it occurs to me that if key update makes sense to even
include depends on the decided threshold. If it is 64GB, then it
makes sense to include. If it is 256TB, then probably not (pseudo-
wrapping TLS sequence numbers is probably not a good usecase,
as data volumes would need to be enormous for that to become an
issue).

[1] It also has recommendation to rekey before 2^32 packets, but
that comes from SSH sequence numbers being 32-bit. TLS sequence
numbers are 64-bit.

-Ilari