Subject: Key updates

From: Martin Thomson <[email-masked]>
Date: Mon, 6 Aug 2018 15:55:39 +1000

One of the open items out of the design team work was the interaction
between TLS and key updates.  As you might know, TLS key updates are
synchronous, which works well in TCP, but less well in QUIC, where you
need at least two active keys for reception around a key change.

As it is, I think that there are two serious options:

1. Use KEY_PHASE to signal a change.  This requires that both
endpoints are loosely synchronized, which disadvantages asymmetric
data exchanges.

2. Use a prepare-commit style.  DTLS does this by having each peer
send a KeyUpdate message, then requiring that to be acknowledged
before they can switch to the new epoch. QUIC could do the same. The
change is still signaled in the key phase bit, but only after this
signaling exchange.

The weakness of the first option is that packets marked with a change
of key phase trigger trial decryption.  And it requires synchronized
changes, where if one endpoint moves to epoch N (epoch == encryption
level with fewer characters to type), then the other has to follow
before either can move to epoch N+1.  The second has more moving
parts, but avoids both of these problems.

I tend to think that the second is a better design on balance, if only
to dispense with the trial decryption, which we've managed to avoid in
every other case thus far.  The complication might also present some
opportunities, which I will explain below, but that's a secondary
concern.

If we want to use this signaling method, we need to decide who drives
key updating, TLS or QUIC:

TLS: The DTLS design might work in QUIC, but with the KeyUpdate
message hidden in an opaque CRYPTO frame, it could be a little tricky
to manage properly.  If we let TLS drive the key update, then it will
send a KeyUpdate message in a CRYPTO frame and inform QUIC of the
change in sending keys.  From here, QUIC can keep using old keys until
all CRYPTO frames from that epoch are acknowledged.  The receiver will
inform QUIC of new receive keys when it receives KeyUpdate, which can
be installed.

QUIC: Here we define a new frame type (KEY_UPDATE, say) that QUIC
sends when it wants to update keys.  When this is acknowledged, new
keys can be installed and used for sending.  A new API is needed to
TLS to support cranking the key schedule forward.  Invoking that API
would lead to TLS signaling the availability of new keys.  The receive
side isn't any different from the TLS option.  If this was to have
parity with TLS, this would probably need to be two frame types so
that a unilateral update could be distinguished from an update that
includes a request for a mutual update.

In both cases, QUIC will install new receive keys, but retain old
receive keys so that it can deal with reordering.  A few round trips,
an RTO, 2MSL, or whatever we decide for the handshake is probably
fine.  Sending keys can be discarded immediately.

The advantage of having TLS drive is that it uses the same machinery
we have for the handshake.  And there is no disparity between what TLS
and QUIC understand to be current: when TLS wants to send something (a
NewSessionTicket message for example), then it asks for an epoch that
matches what QUIC is using.

The disadvantage of using TLS is that there are more moving parts
involved.  It fits the rules we have for the handshake neatly: for
instance, the CRYPTO frame would be retransmitted using the strict
encryption-level rules, reusing that code from the handshake.  But
those rules aren't really necessary given that the rules for a
KEY_UPDATE easily have the same effect.

My inclination here is to have TLS drive this.  The additional
complexity seems to be manageable in the sense that it uses mechanisms
that should already exist for the handshake.  I also don't think that
a new API for this feature is a good way to ensure that it is used.

Those who are implementing, I know that key updates are often a long
way down the list of priorities, but has anyone spent time considering
the options here?  (I personally implemented key updates for TLS, but
I still haven't managed to find time to do it for DTLS, which might
say something...)

--
Addendum: Optional Key Phase ?

One of the nice things about either prepare-commit design is that it
opens a new option for how we use bits in headers.  If there is a
concern about spending a bit on every packet for the key phase (a
whole bit!), we could design an encoding that only included the key
phase if a longer packet number encoding was in use.

The idea would be that you could use the longer packet number encoding
while you have a key update outstanding, so that the key phase was
available for the entirety of the changeover.  Once packets with the
new epoch were acknowledged, you could switch back to a shorter
encoding that didn't include a key phase.  The receiver would switch
to expecting the new epoch after receiving the first packet in the new
epoch.

That's a saving that might allow endpoints to use the shortest packet
number encoding in more cases.  Of course, the header design is
already complex enough, so maybe we don't actually *want* more options
to consider there :)

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Mon, 6 Aug 2018 02:22:26 -0700

On the last part: using a longer packet number - that would create an
observable signal similar to an unencrypted key-phase bit because many
packets would tend to have similar sizes, then suddenly spike a few bytes
in length.

Key phase could also be tied to connection id, and perhaps some
consideration should be given to a possible multi-path design before opting
for the more complex solution.

As I understand it, the commit option still requires synchronised key
updates in both directions. How about one-sided key updates?

On 6 August 2018 at 07.56.18, Martin Thomson ([email-masked])
wrote:

---

From: Martin Thomson <[email-masked]>
Date: Mon, 6 Aug 2018 19:31:16 +1000

> packets would tend to have similar sizes, then suddenly spike a few bytes

The size of a packet number is hidden. Given that most packets are full
sized, the only effect on those would be less available space for payload.
ACK packets would increase in size by a couple of octets, which could be
masked easily and cheaply if necessary.

> for the more complex solution.

This is definitely an option I have considered. If you have a workable
design, I would be interested. I couldn't reconcile the desired rates of
updates. Connection IDs are needed in spikes, where the rate for key
updates is more measured.

> updates in both directions. How about one-sided key updates?

The option I describe doesn't require that both sides update at the same
time, not do endpoints need to update in lock-step (they can require
reciprocal updates, but that is discretionary).

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Mon, 6 Aug 2018 02:39:23 -0700

I’d challenge that, especially in the cases where it matters most: long
running mobility applications. For example a car management system that
uploads battery and other operational statistics, geofencing applications,
or chat applications used by train commuters.

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Mon, 6 Aug 2018 02:44:52 -0700

I believe the current consensus is to have an ordered set of connections
ID’s. If that were not the case, or if there were two sets, then some
connection ID’s could be associated with a key update. If running out of
key update ID’s, a new such ID would be requested. This is somewhat similar
to the commit based option.

---

From: Martin Thomson <[email-masked]>
Date: Mon, 6 Aug 2018 19:52:24 +1000

On Mon, Aug 6, 2018 at 7:44 PM Mikkel Fahnøe Jørgensen
<[email-masked]> wrote:
>
>> This is definitely an option I have considered. If you have a workable design, I would be interested. I couldn't reconcile the desired rates of updates. Connection IDs are needed in spikes, where the rate for key updates is more measured.
>
> I believe the current consensus is to have an ordered set of connections ID’s. If that were not the case, or if there were two sets, then some connection ID’s could be associated with a key update. If running out of key update ID’s, a new such ID would be requested. This is somewhat similar to the commit based option.

The current direction seems to be toward a bag of connection IDs,
without ordering.  I considered attaching an epoch to
NEW_CONNECTION_ID and having updates coupled to key changes, which
could work if you were willing to couple changes in that way.  The
problem there is twofold:  the provider of connection IDs is in
entirely control over when updates happen (you can't ever update
yourself unilaterally), and not all connections have a connection ID
in the relevant direction.  The former is annoying and probably
manageable, the latter is a real deal breaker.

>> ACK packets would increase in size by a couple of octets, which could be masked easily and cheaply if necessary.
>
> I’d challenge that, especially in the cases where it matters most: long running mobility applications. For example a car management system that uploads battery and other operational statistics, geofencing applications, or chat applications used by train commuters.

Are you suggesting that these applications have fixed size payloads
such that the change to a longer packet number would be noticeable.
That's might be true, but sending a TLS KeyUpdate message or
KEY_UPDATE frame would also change the size of packets in a fairly
obvious fashion if that were the case (many of these applications have
a predictable send rate) as well.  If there is an occasional increase
in rate, both in terms of number of packets and size, then yes, that
could reveal that a key update happened.  If that happens across a
change of path, then yes, there is a linkability exposure.  Given how
packet rates are low on these applications, it might be that key
updates could be disabled for those applications if this is a concern.
As it is, this is far better than a cleartext KEY_PHASE bit, which is
a great correlator.

---

From: Ian Swett <[email-masked]>
Date: Mon, 6 Aug 2018 08:43:09 -0400

> I still haven't managed to find time to do it for DTLS, which might

I think we seriously considered the option of "Close the connection and
0RTT a new one".

As a related point, I've seen a few use cases for QUIC where it was useful
to have different keys for different connection IDs for a longish period of
time.  The first is pairing multicast + unicast, but I think there was
another.  That makes me attracted to the idea of punting on this for QUIC
v1 and tackling this at the same time as multipath?

---

From: Mirja Kühlewind <[email-masked]>
Date: Mon, 6 Aug 2018 15:06:52 +0200

> Am 06.08.2018 um 14:43 schrieb Ian Swett <ianswett=[email-masked]>:
> 
> I think we seriously considered the option of "Close the connection and 0RTT a new one".
> 
> As a related point, I've seen a few use cases for QUIC where it was useful to have different keys for different connection IDs for a longish period of time.  The first is pairing multicast + unicast, but I think there was another.  That makes me attracted to the idea of punting on this for QUIC v1 and tackling this at the same time as multipath?

+1

However, this brings us back to Martin’s other question: does it make sense to have a couple of reserved bits to make it easy to add a bit for the next version with minimal changes to the protocol machinery/wire image?

---

From: Nick Banks <[email-masked]>
Date: Mon, 6 Aug 2018 14:26:29 +0000

On the topic of who drives key updates, my preference would be toward QUIC. I prefer QUIC to have as little dependence on the TLS state object post handshake as possible. Preferably, I'd like to  be able to throw away the entire TLS state object some short time after the handshake. Obviously this would only be possible if no further NST will be shared, but I believe there are several cases where this will be true. This would allow a more memory efficient design, especially on the server side.

As far as punting this to the next version, I also think that might be a good idea. I further agree with Mirja's suggestion that we should still give some consideration now, so as to make the move to the next version easier; if we go this route.

- Nick

---

From: Martin Thomson <[email-masked]>
Date: Tue, 7 Aug 2018 10:36:23 +1000

> I think we seriously considered the option of "Close the connection and 0RTT a new one".

Yes, and the TLS working group did too.  This is what we got.

I implemented a limit to the number of records we send in TLS and
haven't heard a complaint (even though we have non-trivial numbers of
DES connections, where the limit is fairly low).  Which suggests that
this might be an OK strategy... for the web.

However, I also know that people were using h2 for things like
connections between gateways and origin servers and were very annoyed
at the 2^31 cap on the number of streams, which caused them all sorts
of performance problems during changeovers.  2^31 streams happens well
after you need to rekey GCM.  I don't think that we can reasonably
punt on this.

My writeup was long, but I think that the fix is simple.  As much as
Nick might like to destroy TLS state (the essential parts of which
aren't a real burden, being comprised of two 32 octet secrets and an
epoch counter), I don't believe that we can just kick this particular
can down the road, tempting as it might seem.

I do want to explore the notion of binding key changes to connection
ID.  It has some nice properties.  I can't make it work without making
things more complicated than what I proposed though.

---

From: Martin Thomson <[email-masked]>
Date: Tue, 7 Aug 2018 10:39:23 +1000

> However, this brings us back to Martin’s other question: does it make sense to have a couple of reserved bits to make it easy to add a bit for the next version with minimal changes to the protocol…

I think that was Dirkjan who asked that question.

The driving principle behind defining invariants was to avoid having
to come back to this question repeatedly.  We have a version
negotiation mechanism that allows us to change an awful lot between
different protocol version.  We don't need to reserve a few bits
because most of them are already reserved.

---

From: Kazuho Oku <[email-masked]>
Date: Tue, 7 Aug 2018 13:55:44 +0900

2018-08-06 14:55 GMT+09:00 Martin Thomson <[email-masked]>:
> of key phase trigger trial decryption.

I think that I might prefer option 1.

I do not think that the current mechanism requires trial decryption.
IIUC, the endpoints are not allowed to start sending packets at epoch
N+1 until they see peers acknowledging packets that were sent in epoch
N. That means that an endpoint only needs to have at most 2 keys (for
epoch N+1 and N). The epoch (either N or N+1) can be recovered from
the KEY_PHASE bit and there is no need for trial decryption.

Am I missing something?

The issue that might exist with option 2 is that it does not work well
with our model of using QUIC to transport TLS handshake messages.

In the model, the TLS stack never waits for ACK. Handling of
retransmits in the responsibility of QUIC. This is fine for
"handshake", because the moment when a new encryption key becomes
usable is indicated by a TLS message.

However, for key update, the TLS stack needs to wait for the peer to
acknowledge the receipt of the KeyUpdate message before it can start
using it. At least that is what is defined in the DTLS draft. Section
8 of the draft states, quote: "In order to facilitate epoch
reconstruction Section 4.2.2 implementations MUST NOT send with the
new keys or send a new KeyUpdate until the previous KeyUpdate has been
acknowledged (this avoids having too many epochs in active use)."

I am not sure if adding a way to signal the receipt of ACK for a
particular TLS message from QUIC to TLS stack is worth the cost. We do
not have that kind of mechanism. I am scared that such mechanism could
become very complex, considering the fact that the QUIC stack can
split TLS handshake in any way that it would like.

Or are you suggesting a mechanism other than what is defined in DTLS?

> And it requires synchronized

-- 
Kazuho Oku

---

From: Kazuho Oku <[email-masked]>
Date: Tue, 7 Aug 2018 13:58:52 +0900

2018-08-06 18:31 GMT+09:00 Martin Thomson <[email-masked]>:
>> packets would tend to have similar sizes, then suddenly spike a few bytes in
>> length.
>
>
> updates. Connection IDs are needed in spikes, where the rate for key updates
> is more measured.

The other issue with tying key phase to connection ID is that such
design would not allow key update to happen when a zero-length
connection ID is used.

We allow the use of zero-length connection IDs, and I'd assume that it
would be fairly popular for the client-side. I think that we would
prefer such endpoints to have the ability to update the keys as well.

-- 
Kazuho Oku

---

From: Martin Thomson <[email-masked]>
Date: Tue, 7 Aug 2018 15:15:24 +1000

> the KEY_PHASE bit and there is no need for trial decryption.

There is a problem right now with concurrent updates.  If both peers
bump at the same time, then N-1 packets could still be in flight.  A
little reordering will cause them to be interpreted as N+1 instead
(because they arrive after packets at N and we only have one bit of
signal).

So if you want to avoid loss spikes around rekeying, you have to do a
little trial decryption at that point.

Also, the way you ratchet forward is to observe a bit flip, at which
point you decrypt with N+1.  If that works, then you do something.
It's not quite trial decryption in the sense that you only try one
key, but - having implemented it - it's a little annoying to get
right.

> Or are you suggesting a mechanism other than what is defined in DTLS?

It's pretty close that in DTLS.  Here's what I imagined would work:

You let TLS send its KeyUpdate, which gets bundled into a CRYPTO
frame.  TLS moves to the new epoch, and advertises the availability of
new keys.  However, you continue to send in the old epoch until you
have flushed all pending CRYPTO data from the old epoch (i.e., the
CRYPTO frame has all been acknowledged).  All other processing stays
the same: CRYPTO frames are always sent using the same keys, even on
retransmission, new TLS messages would be sent in the new epoch, and
ACK frames would need to send using the epoch of the packets they
acknowledge.

The reason we don't have problems with the handshake is that we *know*
that the peer has keys for the new epoch.  Otherwise we would have to
do the same thing.  There, following these rules would mean sending in
the clear, which isn't smart.  Here, it's just a key update.

---

From: Kazuho Oku <[email-masked]>
Date: Tue, 7 Aug 2018 15:10:42 +0900

2018-08-07 14:15 GMT+09:00 Martin Thomson <[email-masked]>:
> bump at the same time, then N-1 packets could still be in flight.

I think that we might be having different models in our minds.

My view is that, in principle, an endpoint unilaterally updates its
epoch that it uses for "sending" packets. An endpoint MUST NOT update
the send epoch before it sees an acknowledgement for a packet that was
sent encrypting using the current epoch.

To implement reciprocal key update, we will also state that, if the
send epoch used by the peer becomes greater than the value used by an
endpoint, then the endpoint SHOULD increment it's send epoch as well.

If we define the rules this way, I would assume that there is not
chance of key getting updated twice even in case both the peers decide
to update at the same moment.

To put it another way, the issue with the reciprocal (D)TLS-style key
update is that it is defined as a "request" rather than a state change
with idempotency. The rules above is designed as an idempotent state
change from N to N+1 that can be implemented by either peer without
the fear of double update that will lead to potential loss (unless the
endpoints retains more than two keys).

> A
> CRYPTO frame has all been acknowledged).

Thank you for the explanation.

I think that the described algorithm will work fine, but I am not sure
if I like the fact that it requires the QUIC stack to remember the new
encryption key and the fact that a KeyUpdate message has been sent in
a CRYPTO frame at certain offset, and switch to the new key when all
the data up to that offset is acknowledged.

In my view, the design is breaking the layer between the contents
CRYPTO and the QUIC stack (QUIC stack needs to know what is carried in
CRYPTO), and is also requiring the QUIC stack to handle the CRYPTO
frames other than a conveyer of stream of data (by requiring to do
specific action at specific offsets).

> All other processing stays

-- 
Kazuho Oku

---

From: Martin Thomson <[email-masked]>
Date: Tue, 7 Aug 2018 16:37:09 +1000

> endpoints retains more than two keys).

There is nothing inherently wrong with the current design, but I
recently realized that there is a corner case that is awkward at best
without trial decryption, even if you follow those rules.

A sends N+1
B sends N followed by N+1 around the same time.
0.5 RTT later both receive a packet at N+1, so both update (not
naturally noticing that the response was a little faster than it
should have been).
A receives the packet from B at N, reordered a little (maybe the N+1
was a small packet at the tail of a burst).
A thinks that this is N+2 and discards it.

Now, this isn't a correctness issue.  But it's annoying.  It drives
the congestion controller down more than is ideal and adds a bit of
extra latency for anything depending on the contents of that packet
(or those packets if there is more than one).

You fix this by running trial decryption for N and N+2 for a short
time, or you move to the prepare-commit style of update.

> the data up to that offset is acknowledged.

The QUIC stack doesn't have to remember anything other than that is
received new TLS data at epoch N and a key change after that.  The
rules for transmitting CRYPTO frames at the same encryption level
ensure that everything works correctly.  Now it has new send keys, but
the only new rule it needs would be that until all crypto frames for N
are acknowledged, you can't starting sending on N+1.  I tend to think
of this as not being a new rule, but instead that there are
exceptional rules for this during the handshake.

The rules for receiving are different: you install N+1 for reading
immediately (discarding N-1 if that is still around).  You can discard
N+1 on a timer (that can start immediately, I think, based on what I
worked out for key expiration timers, which I am about to put up as a
PR).

---

From: Kazuho Oku <[email-masked]>
Date: Tue, 7 Aug 2018 16:01:32 +0900

> naturally noticing that the response was a little faster than it

My point is that the issue within the current design is that we
require the endpoint to update if the peer initiates an update.

I am suggesting to change that to "an endpoint updates its epoch if
the peer starts using an epoch that is higher than it uses."

Taking the example,

A sends N+1
B sends N followed by N+1 around the same time
0.5 RTT later both receive a packet at N+1, and they will stay using
N+1, because each of them initiated an update and because the epoch
that one uses is not smaller than the value used by the peer

-- 
Kazuho Oku

---

From: Martin Thomson <[email-masked]>
Date: Tue, 7 Aug 2018 17:10:41 +1000

> that one uses is not smaller than the value used by the peer

I see, thanks for clarifying.  I don't think that this is a great idea
because it means that reordered packets will be dropped.  Reordering
is common enough for at least some implementations to want to retain N
for some time after this changeover.

---

From: Kazuho Oku <[email-masked]>
Date: Tue, 7 Aug 2018 16:39:38 +0900

> for some time after this changeover.

Reordered packets will not be dropped, assuming that an endpoint will
not issue more than one key update within a short amount of time (a
guarantee that is provided by the described design), that each
endpoint will retain at most 2 keys for decryption. Nor there will be
trial decryption.

Generally speaking, I think that the designs can be evaluated in two aspects.

1. if retaining at most 2 keys is fine

Retaining at most 2 keys will be fine if there is a guarantee that
multiple updates within a small amount of time does not happen. That
is guaranteed by the design I described above. It is not guaranteed by
the current design, nor by the (D)TLS-based design.

2. if installation of a new key (or a retirement of an old key) is an
explicit signal

I agree that it is nice to have an explicit signal that instructs the
peer to switch the decryption keys, from epochs=(N-1,N) to (N,N+1).
OTOH, I might prefer requiring an endpoint to switch from (N-1,N) to
(N,N+1) at the earliest moment. This is because then, you could start
using the new key after quiescence.

Considering the two, the (D)TLS-based approach does not have the first
property, even setting the discussion about the complexity aside.

I am fine with having an explicit signal for key installation, though
I think that timer is fine based on my assumption (stated above) that
we would prefer having older generation of keys being retired at the
earliest moment.

-- 
Kazuho Oku

---

From: Dmitri Tikhonov <[email-masked]>
Date: Tue, 7 Aug 2018 08:23:29 -0400

> endpoint will retain at most 2 keys for decryption. Nor there will be

This is my understanding as well.  The key phase bit is simply an
index into an array of keys of size 2 that each side uses as a ring
buffer.  A new key overwrites the old key and the current key becomes
the old key.

  - Dmitri.

---

From: Spencer Dawkins at IETF <[email-masked]>
Date: Wed, 8 Aug 2018 15:21:09 -0500

FWIW ...

On Mon, Aug 6, 2018 at 7:39 PM Martin Thomson <[email-masked]>
wrote:

> > However, this brings us back to Martin’s other question: does it make
> sense to have a couple of reserved bits to make it easy to add a bit for
> the next version with minimal changes to the protocol machinery/wire image?
>

That was certainly my understanding when the working group adopted the
invariants draft and added a milestone for it.

Spencer

---

From: Mirja Kühlewind <[email-masked]>
Date: Fri, 10 Aug 2018 12:27:02 +0200

I was more thinking about things we know we want to do in future 
versions and where it would make implementation easier if we already 
design the current version with these changes in mind.

I think that something that is independent of the invariants.