Subject: Re: [TLS] Data volume limits

From: Henrick Wibell Hellström <[email-masked]>
Date: Fri, 1 Jan 2016 13:54:00 +0100

I think it is a good idea to rekey AES-GCM after approximately 2^32 
records, give or take a few magnitudes.

The question for me isn't whether AES-GCM requires frequent rekeying (it 
does), but exactly how much complexity the rekeying mechanism would add, 
to the protocol and to implementations.

On 2015-12-28 20:54, Eric Rescorla wrote:
> Scott, Henrick,
>
> Are you persuaded by Watson's analysis?
>
> Thanks,
> -Ekr
>
>
>
>
> On Mon, Dec 21, 2015 at 7:41 AM, Hubert Kario <[email-masked] 
> <mailto:[email-masked]>> wrote:
>
>     On Tuesday 15 December 2015 20:01:58 Bill Frantz wrote:
>     > 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.
>
>     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 <http://www.cz.redhat.com>
>     Red Hat Czech s.r.o., Purkyňova 99/71, 612 45, Brno, Czech Republic
>     _______________________________________________
>     TLS mailing list
>     [email-masked] <mailto:[email-masked]>
>     https://www.ietf.org/mailman/listinfo/tls
>
>
>
>
> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 1 Jan 2016 16:40:16 +0200

On Fri, Jan 01, 2016 at 01:54:00PM +0100, Henrick Wibell Hellström wrote:
> I think it is a good idea to rekey AES-GCM after approximately 2^32 records,
> give or take a few magnitudes.
> 
> does), but exactly how much complexity the rekeying mechanism would add, to
> the protocol and to implementations.

There have been three basic proposed categories of key update schemes:

1) Ratchet keys through KDF, no new randomness.
2) Ratchet keys through KDF, with new randomness
3) Do new PK key exchange

Also, if one doesn't want applications to have to be aware of rekeying,
one can't introduce new flights ("fully asynchronous key update"). This
would cause _severe_ constraints.

Then there is strictly weaker constraint that one can't introduce "dead
air", where the protocol can't make forward progress without waiting
for response (the previous constraint is sufficient but not necressary
to meet this).

Firstly, 1)

The current scheme is example of 1) without new flights. Basically,
send a message to ratchet sender's keys. There is no symmetry-breaking
between updates, so if k(i) = k(j), then k(i+n) = k(j + n) (such
symmetry-breaking could be introduced by adding key number to KDF
inputs).

Also, I noted that the current scheme seems to break HKDF pairing:
It tries to expand already expanded value (traffic secret). This
violates pairing.

Also, scheme like this could nicely work with DTLS: One could use
epoch numbers to signal rekeying (but one would then take care
not wrap epoch in way that could cause confusion).

Then 2)

Doing 2) without new flights would imply:

- Two traffic keys, one for each direction. The low-level ciper keys
  derive from traffic key of respective direction.
- Sending message to update keys would update only the traffic key
  in sending direction, regenerating low-level cipher keys and resetting
  the RSN in that direction.
- Entropy from peer can't be explicitly be used. The best one could
  do here is to recommend mixing last received ratchet entropy from
  peer into own entropy to produce the random value to send when
  replying (when that happens).

I don't think this is terribly more complicated than 1). But it is
more complicated nevertheless.

I don't see dropping the stronger full asynchronous constraint would
simplify things, due to possibility of "crossed rekey" caused by
finite "speed of light".

Also, this would cause issues with DTLS: One would have to reliably
transmit these rekeying messages, whereas previous DTLS are reliable
only within handshake.

Finally 3)

Now the rekeying necressarily involves two messages. Doing this
fully asynchronously seems just about impossible (updating one half-
key at a time would hit "key caching" problem).

Then it would be whole new logic for performing PK exchange. One
can't reuse handshake because it would introduce thorny issues about
tying to previous handshake and ensuring that state doesn't change
in all sorts of unexpected ways. It also would need to somehow
prevent crossing a key update.

All in all, the complexity looks grealy greater than 1) or 2).

-Ilari

---

From: James Cloos <[email-masked]>
Date: Fri, 01 Jan 2016 14:00:07 -0500

[Msg for followup picked at random from this thread -JimC]

One thing we should remember on this thread is that it does not only
apply to aes and its' 128-bit block size.

Because TLS chose to create a NotQuiteChaCha rather than use ChaCha,
its chacha20poly1305 also has a small data volume limit (2^40 bits;
only twice aesgcm's limit).

So key updates or re-keying will be more universally required.

(Are there any aeads currently spec'ed with both large enough blocks and
large enough nonces safely to avoid key updates?)

-JimC
-- 
James Cloos <[email-masked]>         OpenPGP: 0x997A9F17ED7DAEA6

---

From: Eric Rescorla <[email-masked]>
Date: Fri, 1 Jan 2016 11:24:27 -0800

> only twice aesgcm's limit).

Can you elaborate on this point a bit? I haven't been focusing on ChaCha,
but we're not quite done with ChaCha yet, so if changes are needed, now
would be
the time.

-Ekr

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 1 Jan 2016 21:27:57 +0200

> only twice aesgcm's limit).

Huh? AFAIK, the limiting factor with Chacha20 as specced in TLS is
the RSN space => 2^64 records maximum (which is 256ZB at max record
size, and 352EB just to transmit the record overheads).

Transferring just the 352EB at 1,000 Gbps would take about 100 years.

-Ilari

---

From: James Cloos <[email-masked]>
Date: Fri, 01 Jan 2016 19:42:21 -0500

>>>>> "ER" == Eric Rescorla <[email-masked]> writes:

ER> Can you elaborate on this point a bit? I haven't been focusing on
ER> ChaCha, but we're not quite done with ChaCha yet, so if changes are
ER> needed, now would be the time.

The switch from 64 bit nonce + 64 bit counter to 96 bit nonce + 32 bit
counter means a max of 2**32 * 256 bits before a key update is needed, yes?

-JimC

---

From: Eric Rescorla <[email-masked]>
Date: Fri, 1 Jan 2016 18:03:14 -0800

> counter means a max of 2**32 * 256 bits before a key update is needed, yes?

This doesn't sound right to me.

In TLS, we use a distinct nonce for each record and then a block counter
inside the record. So, it's true that you couldn't encrypt a record that
was more than 2^{32} * 256 bits long, but since TLS records can't be
more than 16KB long anyway, this isn't the critical limitation.

-Ekr

---

From: James Cloos <[email-masked]>
Date: Sat, 02 Jan 2016 11:19:11 -0500

>>>>> "ER" == Eric Rescorla <[email-masked]> writes:

ER> In TLS, we use a distinct nonce for each record and then a block counter
ER> inside the record. So, it's true that you couldn't encrypt a record that
ER> was more than 2^{32} * 256 bits long, but since TLS records can't be
ER> more than 16KB long anyway, this isn't the critical limitation.

That does change things.  I do not recall any posts noting that after I
posted an objection to the change, but I mostly missed everything from
May thru July or so because of the stroke...

Thanks for the correction.

-JimC

---

From: Hubert Kario <[email-masked]>
Date: Mon, 04 Jan 2016 12:59:53 +0100

On Monday 28 December 2015 21:08:10 Florian Weimer wrote:
> On 12/21/2015 01:41 PM, Hubert Kario wrote:
> 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.

this situation already happens in initial handshake so the 
implementation needs to support that

I don't see how rekey adds complexity here...

Web: www.cz.redhat.com

---

From: Florian Weimer <[email-masked]>
Date: Mon, 4 Jan 2016 13:02:57 +0100

> implementation needs to support that

But after and the handshake and without real re-key, sending and
receiving operations exactly match what the application requests.  If
you need to switch directions against the application's wishes, you end
up with an API like OpenJDK's SSLEngine (or a callback variant which is
equivalent in complexity).

Dealing with this during the initial handshake is fine.  But supporting
direction-switching after that is *really* difficult.

Florian

---

From: Hubert Kario <[email-masked]>
Date: Mon, 04 Jan 2016 13:19:44 +0100

On Monday 04 January 2016 13:02:57 Florian Weimer wrote:
> you need to switch directions against the application's wishes, you
> end up with an API like OpenJDK's SSLEngine (or a callback variant
> which is equivalent in complexity).

for renegotiation, yes

but for rekey it doesn't need any input from application so there is no 
need for any callbacks
 
> Dealing with this during the initial handshake is fine.  But
> supporting direction-switching after that is *really* difficult.

yes, this is a bit more problematic, especially for one-sided transfers. 
For example, when one side is just sending a multi-gigabyte transfer as 
a reply to a single command - there may be megabytes transferred before 
the other side reads our request for rekey and then our "CCS" message

I thought you just meant the need to keep two cipher contexts in memory 
at the same time (current and currently negotiated).
-- 
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: Florian Weimer <[email-masked]>
Date: Mon, 4 Jan 2016 13:22:15 +0100

> the other side reads our request for rekey and then our "CCS" message

Yes, this is the issue I meant.  I simply don't see a way to re-inject
new randomness without a round-trip.  (Key update without new randomness
doesn't face this challenge, but then it's mostly cheating.)

Florian

---

From: Benjamin Kaduk <[email-masked]>
Date: Tue, 5 Jan 2016 18:56:03 -0600

> doesn't face this challenge, but then it's mostly cheating.)

EKR asked for an explanation of what risk you want to mitigate by adding
new randomness on the 28th of December, but I don't recall seeing an
explanation.  This belief that key update without new randomness is
undesirable does not really seem to be supported by any concrete
arguments, in the recent history of this thread.

-Ben

---

From: Florian Weimer <[email-masked]>
Date: Thu, 7 Jan 2016 11:45:04 +0100

On 01/06/2016 01:56 AM, Benjamin Kaduk wrote:
> explanation.

I tried, but maybe it's not clear.

Anyway, I don't see the current key update mechanism provides much
value.  I don't think it is desirable to have a full re-key mechanism
with the complexity it involves.

Florian