Subject: [quicwg/base-drafts] Rework Key Update (#2237)

From: Martin Thomson <[email-masked]>
Date: Thu, 20 Dec 2018 17:26:51 -0800

This section was pretty old and it had at least one bug, along with a
bunch of editorial lack of clarity.

Substantively, this does two things:

1. It specifies what label to use for the KDF when updating.  The
agreement at one time was that we would use a quic-specific label, but
that never really got captured properly.  This proposes "quic ku".

2. It specifies that acknowledgments of packets with a given key phase
are necessary before another update can be triggered.  As noted in
 #2214, simultaneous updates can result in a deadlock if updates happen
too quickly.  This has the nice effect of allowing update compliance to
be more rigorously tested.

Closes #2214.
You can view, comment on, or merge this pull request online at:

  https://github.com/quicwg/base-drafts/pull/2237

-- Commit Summary --

  * Rework Key Update

-- File Changes --

    M draft-ietf-quic-tls.md (92)

-- Patch Links --

https://github.com/quicwg/base-drafts/pull/2237.patch
https://github.com/quicwg/base-drafts/pull/2237.diff

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/2237

---

From: ekr <[email-masked]>
Date: Thu, 20 Dec 2018 17:36:08 -0800

Hmm... I thought we had agreed that we were never going to use acknowledgements as side effects and that's why we rejected the DTLS-style KeyUpdate. I had assumed that instead you were waiting for the other side to change its phase.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/2237#issuecomment-449206362

---

From: Marten Seemann <[email-masked]>
Date: Thu, 20 Dec 2018 18:32:18 -0800

marten-seemann commented on this pull request.

I agree with @ekr. At least in my implementation, the coupling between acknowledgements and key management would create *a lot* of additional complexity.
I proposed a different solution in https://github.com/quicwg/base-drafts/issues/2214#issuecomment-449219993.

> +
+Endpoints maintain separate read and write secrets for packet protection.  An
+endpoint initiates a key update by updating its packet protection write secret
+and using that to protect new packets.  The endpoint creates a new write secret
+from the existing write secret as performed in Section 7.2 of {{!TLS13}}.  This
+uses the KDF function provided by TLS with a label of "quic ku".  The
+corresponding key and IV are created from that secret as defined in
+{{protection-keys}}.  The header protection key is not updated.
+
+The endpoint uses the key and IV to protect all subsequent packets, and inverts
+the value of the KEY_PHASE bit to signal the change of keys.
+
+An endpoint MUST NOT initiate more than one key update at a time.  A new key
+cannot be used until the endpoint has received an acknowledgment for a packet it
+sends with the new keys.  An endpoint that receives a packet protected with old
+keys that includes an acknowledgement for a packet protected with newer keys MAY

I don't understand this error condition. Are you implying that key updates effectively create separate packet number spaces, and ACKs are only valid for the space that they're sent with?
I know that there was a lot of discussion about which packets to include in an ACK frame, but as a high-level strategy it should be allowed to include all packets received within the last one to two RTTs. This would lead to ACK frames that span multiple key phases.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/2237#pullrequestreview-187252610

---

From: Martin Thomson <[email-masked]>
Date: Thu, 20 Dec 2018 20:12:54 -0800

We can switch to a two-bit epoch if you like.  That addresses the problem.  This is the easiest change to specify, but if implementing a two-bit epoch is easier, we have the bits available, it's totally possible.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/2237#issuecomment-449240409

---

From: Marten Seemann <[email-masked]>
Date: Thu, 20 Dec 2018 20:23:41 -0800

The thing I like about a two-bit epoch is that it's easy to implement frequent key updates. My hope is that implementation will rotate keys a lot more frequently than the theoretically safe levels - otherwise key rotation will remain an obscure function of the protocol that's only used on 0.01% of the connections, and we all know what that means for interop.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/2237#issuecomment-449243183

---

From: Martin Thomson <[email-masked]>
Date: Thu, 20 Dec 2018 20:43:18 -0800

The number of bits we use to signal key update doesn't have any effect on how often it will be used.  The reason I like it is that it avoids a problem we didn't realize we had until now.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/2237#issuecomment-449246934

---

From: Marten Seemann <[email-masked]>
Date: Thu, 20 Dec 2018 20:46:41 -0800

I think it does, since the issue I described depends on all packets of a certain key phase being lost. If you only do key updates for example every 1 million packets, the probability of that would be negligible.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/2237#issuecomment-449247648

---

From: Martin Thomson <[email-masked]>
Date: Thu, 20 Dec 2018 20:53:36 -0800

What is important is how often people want to update.  And even without this bug, I doubt that it is going to be that often.  That said, we'll probably eventually want to grease it.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/2237#issuecomment-449249377

---

From: Kazuho Oku <[email-masked]>
Date: Thu, 20 Dec 2018 21:25:48 -0800

If we are to use another bit, could we use that for indicating the newest KEY_PHASE bit that the peer used for sending?

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/2237#issuecomment-449258272

---

From: Marten Seemann <[email-masked]>
Date: Thu, 20 Dec 2018 21:30:03 -0800

@kazuho That would make key updates on both sides completely independent from each other, wouldn't it? i.e. I wouldn't have to update my (send) keys when the peer updates its keys.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/2237#issuecomment-449259360

---

From: Kazuho Oku <[email-masked]>
Date: Thu, 20 Dec 2018 21:33:42 -0800

@marten-seemann IIUC, current design does not enforce that. It's just that the text tells you that an endpoint should update when the peer does. That can be the same.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/2237#issuecomment-449260246

---

From: Martin Thomson <[email-masked]>
Date: Fri, 21 Dec 2018 05:34:17 +0000 (UTC)

@kazuho, As a practical matter, spending the two bits on epoch gives us more flexibility.  You could, if you wanted, have multiple updates in flight with two bits (up to 3 updates then).  If you echo a bit, you do fix the bug, but get less out of it.

@marten-seemann, you could, but then you lose the ability to force the other side to update.  That's a requirement we discovered in TLS.  Say that I know that AES-128-GCM is weak and needs updating every 1 million packets, as opposed to the 200 million or so that we currently understand to be the limit.  I can use the current scheme to cause you to update even if you don't know that.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/2237#issuecomment-449260311

---

From: Kazuho Oku <[email-masked]>
Date: Thu, 20 Dec 2018 21:38:34 -0800

@martinthomson 
> As a practical matter, spending the two bits on epoch gives us more flexibility. You could, if you wanted, have multiple updates in flight with two bits (up to 3 updates then). If you echo a bit, you do fix the bug, but get less out of it.

I agree. OTOH, assuming that we wouldn't be updating the keys too often, I would prefer the least complex approach on solving the issue (when spending enough amount of bits). And to me it seems that having an explicit signal that indicates that the peer has received the key update might be the simplest.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/2237#issuecomment-449260836

---

From: Martin Thomson <[email-masked]>
Date: Thu, 20 Dec 2018 21:40:42 -0800

I think that checking send and receive epoch for equality is simple enough.  It's just that N and N+2 would appear to be the same, and two bits fixes that.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/2237#issuecomment-449261117

---

From: Martin Thomson <[email-masked]>
Date: Thu, 20 Dec 2018 21:54:12 -0800

@martinthomson pushed 1 commit.

b4ddb7f6a837e0771307519ae6604facf2dba5b4  Switch to a two-bit key phase

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/2237/files/867af94790a3e2cb696dadca9352d7bff537e37a..b4ddb7f6a837e0771307519ae6604facf2dba5b4

---

From: Martin Thomson <[email-masked]>
Date: Thu, 20 Dec 2018 21:56:55 -0800

martinthomson commented on this pull request.

No, the point of this is that you requested a key update and the peer didn't comply.  This is how we ensure that endpoints update when requested.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/2237#discussion_r243493730

---

From: Martin Thomson <[email-masked]>
Date: Thu, 20 Dec 2018 21:57:28 -0800

4d3f65aacb02e09cb9b4e0ca2f4d5b9c6adeb373  unplural

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/2237/files/b4ddb7f6a837e0771307519ae6604facf2dba5b4..4d3f65aacb02e09cb9b4e0ca2f4d5b9c6adeb373

---

From: Marten Seemann <[email-masked]>
Date: Thu, 20 Dec 2018 22:41:04 -0800

> @@ -1098,50 +1098,23 @@ anticipation of receiving a ClientHello.
 # Key Update
 
 Once the 1-RTT keys are established and the short header is in use, it is
-possible to update the keys. The KEY_PHASE bit in the short header is used to
-indicate whether key updates have occurred. The KEY_PHASE bit is initially set
-to 0 and then inverted with each key update.
+possible to update the keys used to protect packets. The Key Phase bits in the
+short header are used to indicate whether key updates have occurred. The
+Key Phase is initially set to 0 and then incremented with each key update.

Incremented % 4

-The KEY_PHASE bit allows a recipient to detect a change in keying material
-without necessarily needing to receive the first packet that triggered the
-change.  An endpoint that notices a changed KEY_PHASE bit can update keys and
-decrypt the packet that contains the changed bit.
+The Key Phase allows a recipient to detect a change in keying material
+without needing to receive the first packet that triggered the change.  An
+endpoint that notices a changed Key Phase bit can update keys and decrypt the

If we want to be able to force the peer to update its keys, shouldn’t this be a MUST?

> +An endpoint MUST NOT initiate more than one key update at a time.  A new key
+cannot be used until the endpoint has received an indication that its peer is
+using the same key phase.
+
+An endpoint that receives a packet protected with old keys that includes an
+acknowledgement for a packet protected with newer keys MAY treat that as a
+connection error of type PROTOCOL_VIOLATION.
+
+
+## Responding to a Key Update
+
+A receiving endpoint detects an update when the Key Phase is one greater than
+what it is expecting.  The endpoint creates a new read secret and the
+corresponding read key and IV using the same process as its peer.
+
+A packet with a Key Phase other than the expected or next value MUST be

The previous one is ok as well, as long as it’s sent with a smaller packet number. 

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/2237#pullrequestreview-187285207

---

From: Kazuho Oku <[email-masked]>
Date: Fri, 21 Dec 2018 15:17:35 -0800

@martinthomson 
> I think that checking send and receive epoch for equality is simple enough. It's just that N and N+2 would appear to be the same, and two bits fixes that.

Yeah IMO it's a bit unfortunate that an endpoint might need to update the receiving key twice at once, but I agree it works.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/2237#issuecomment-449521464

---

From: Marten Seemann <[email-masked]>
Date: Fri, 21 Dec 2018 18:17:11 -0800

It’s not really updating its key twice at once. The situation where you receive a packet encrypted with N+2 only occurs if both peers already did the simultaneous key update, which means the current key will be N+1 already. 

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/2237#issuecomment-449538062

---

From: Kazuho Oku <[email-masked]>
Date: Fri, 21 Dec 2018 18:36:26 -0800

My point is that a receiver needs to assume that it would be receiving either N, N+1, N+2, instead of just assuming that it would receive one of the two consecutive keys.

Doesn't that make the state machine complicated?

We have the following provisions:
* "An endpoint SHOULD retain old read keys for a period of no more than three times the Probe Timeout (PTO, see {{QUIC-RECOVERY}})."
* "Packets with higher packet numbers always use the updated keys and MUST NOT be decrypted with old keys."

The proposed change of allowing N+2 encourages an endpoint to maintain the states for three generations of the keys to implement this behavior, instead of just keeping information for two generations.

My preference goes to a design that discourages (or disables) frequent key updates, so that keeping states for two generations is guaranteed to be sufficient.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/2237#issuecomment-449539202

---

From: Kazuho Oku <[email-masked]>
Date: Fri, 21 Dec 2018 19:49:58 -0800

(following my previous comment) As an example, a design like below ensures that keeping states for two generation of keys is fine and also encourages the endpoint to drop the older generation key at the correct moment.

* We use one bit for send key phase, and another bit for receive key phase.
* When the sender updates the send key, it's flips the send key phase bit.
* When the receiver _retires_ the old receive key, it flips the receive key phase bit.
* Sender's send key phase bit becoming equal to the peer's receive key phase bit allows the sender to make another key update; until that happens, a sender is not allowed to do a key update.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/2237#issuecomment-449542641

---

From: Martin Thomson <[email-masked]>
Date: Sun, 23 Dec 2018 23:01:26 -0800

A "May Update" bit.  I can see people setting that to a value that prevents key update, but it does have the benefit of signaling when updates are possible in a way that keeps a cap on the number of active keys.  Taking into account all other considerations, I think that is better.  No time to act on that today, but we'll get to it.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/2237#issuecomment-449694662

---

From: Marten Seemann <[email-masked]>
Date: Wed, 26 Dec 2018 08:43:46 -0800

> A "May Update" bit. I can see people setting that to a value that prevents key update

Why is this better? I'm not sure if keeping 2 keys around is so much better than having short periods of time (3 PTO) where you keep 3 keys.
Since key updates will happen rarely in practice, I think we should design a mechanism that actually forces a key update, not one that allows a lazy implementation to prevent a key update from happening in the first place.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/2237#issuecomment-449991777

---

From: Kazuho Oku <[email-masked]>
Date: Wed, 26 Dec 2018 12:14:46 -0800

@marten-seemann We cannot enforce implementors to code correctly.

The issue with the 2-bit KEY_PHASE design is that the receiver has a code path that is very rarely being executed (retaining 3 keys at once). Some stacks might fail to implement it correctly. Or some stacks might not implement key updates correctly at all. Anyways, we might see interoperability issues in the wild, and the bug would be hard to identify, because it's rare and because it would look like an connection stalling to the end user.

"MAY_UPDATE" bit takes a different approach. We do not have a code path that is rarely taken on the receiver side. Hence less chance of having interoperability issues. A receiver that does not allow the sender to update keys can be detected, and then the sender can close the connection with a specific error code. That is much better than the connection silently breaking.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/2237#issuecomment-450019472

---

From: Martin Thomson <[email-masked]>
Date: Sun, 30 Dec 2018 15:18:18 -0800

At this stage, I'm going to put this on the agenda for discussion in Tokyo.  I think that we have three valid options, though we might have ruled the first out:

1. use acknowledgements to regulate multiple updates
2. use two phase bits, representing a cyclic sequence (0, 1, 2, 3) and allow two updates ahead
3. use one phase bit and a second bit indicating whether key updates are permitted

1 is theoretically possible, but likely to be impractical in many implementations, so we can rule that out.

This PR is currently 2, though I'm biased slightly toward 3 now.  It doesn't have an error condition where the phase is 3 ahead of expected, but the packet number is higher.  More importantly, it reduces the number of active keys after the handshake is complete to at most 2.  The drawback is that you can block key updates.  That said, some people might consider that to be a feature.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/2237#issuecomment-450593563