Subject: Key updates

From: Martin Thomson <[email-masked]>
Date: Wed, 09 Jan 2019 13:06:34 +1100

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

The above PR makes some fairly significant changes to key updates.  Mostly the changes are editorial in nature, but the fix to issues 2214 is non-trivial.

The fix is to add another bit to key phase.  That bit is used to signal whether key updates are permitted.  This is necessary to avoid a corner case where it is possible to complete lose synchronization.  One nice property you get from this is the ability to limit the number of keys you have to maintain to 2.

There's more text on how to manage old keys and a cleanup of the language.  The key update text was very old and poorly structured.

Feedback would be appreciated.

---

From: Ian Swett <[email-masked]>
Date: Wed, 9 Jan 2019 09:49:32 -0500

One question: It appears this allows a peer to permanently disable key
updates by always setting the Key Update Permitted bit to 0.  Do you think
that's a feature or a bug?

I can see implementations deciding key update isn't worth implementing
given the low cost of creating a new connection, so it seems like it could
be a feature to me.

On Tue, Jan 8, 2019 at 9:06 PM Martin Thomson <[email-masked]> wrote:

> The above PR makes some fairly significant changes to key updates.  Mostly
> the changes are editorial in nature, but the fix to issues 2214 is
> non-trivial.
>
> The fix is to add another bit to key phase.  That bit is used to signal
> whether key updates are permitted.  This is necessary to avoid a corner
> case where it is possible to complete lose synchronization.  One nice
> property you get from this is the ability to limit the number of keys you
> have to maintain to 2.
>
> There's more text on how to manage old keys and a cleanup of the
> language.  The key update text was very old and poorly structured.
>

---

From: Christian Huitema <[email-masked]>
Date: Wed, 9 Jan 2019 07:12:27 -0800

I am not really supporting this proposed change. I understand that if peers engage in very rapid key updates they can get out of synch, but this is a pathological behavior. Adding another bit in the header is not required, and introduces another failure mode when reneging on the enabled bit.

We could use plenty of bits like that: ECN echo comes to mind. We don't. We use frames. From that point of view, using ACK as a check is more in line with the QUIC design. "Don't roll the key if you have not received at least one ACK for the current phase" seems much simpler. Also, it uses an honest signal, by opposition to a random bit, and that doesn't create an other class of misbehavior.

If that doesn't convince you, then please add a specification on how to react to reneging the enable bit, and also how to react to peers ignoring it.

-- Christian Huitema 

> On Jan 9, 2019, at 6:49 AM, Ian Swett <ianswett=[email-masked]> wrote:
> 
> One question: It appears this allows a peer to permanently disable key updates by always setting the Key Update Permitted bit to 0.  Do you think that's a feature or a bug?
> 
> I can see implementations deciding key update isn't worth implementing given the low cost of creating a new connection, so it seems like it could be a feature to me.
>

---

From: Ryan Hamilton <[email-masked]>
Date: Wed, 9 Jan 2019 10:57:52 -0800

On Wed, Jan 9, 2019 at 7:12 AM Christian Huitema <[email-masked]>
wrote:

> I am not really supporting this proposed change. I understand that if
> peers engage in very rapid key updates they can get out of synch, but this
> is a pathological behavior. Adding another bit in the header is not
> required, and introduces another failure mode when reneging on the enabled
> bit.
>
> We could use plenty of bits like that: ECN echo comes to mind. We don't.
> We use frames. From that point of view, using ACK as a check is more in
> line with the QUIC design. "Don't roll the key if you have not received at
> least one ACK for the current phase" seems much simpler. Also, it uses an
> honest signal, by opposition to a random bit, and that doesn't create an
> other class of misbehavior.
>

I like this advice. It seems simple and obviously correct.

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Wed, 9 Jan 2019 16:53:45 -0500

Agree

On 9 January 2019 at 19.58.20, Ryan Hamilton (
rch=[email-masked]) wrote:

---

From: Martin Thomson <[email-masked]>
Date: Thu, 10 Jan 2019 09:13:21 +1100

On Thu, Jan 10, 2019, at 02:12, Christian Huitema wrote:
> line with the QUIC design. "Don't roll the key if you have not received 
> at least one ACK for the current phase" seems much simpler. Also, it 
> uses an honest signal, by opposition to a random bit, and that doesn't 
> create an other class of misbehavior.

If you look at the history of the PR, I initially proposed using ACK in exactly this way.  The feedback I got was that this was difficult for people to implement, because it more tightly couples two parts of the processing pipeline than was previously necessary.  That is, if you consider packet protection as a discrete stage in processing, getting information to and from the ACK frame processing might be difficult, depending on implementation structure.

We've been very careful to avoid having protocol behaviour that triggers on acknowledgment.  I don't think that we have any that escape the loss recovery and CC algorithms.  As an architectural principle, I think that is worth preserving.

> If that doesn't convince you, then please add a specification on how to 
> react to reneging the enable bit, and also how to react to peers 
> ignoring it.

That I have done.  Of course, as Ian points out, if the bit is never set, there isn't really any recourse, and that might be valuable enough to be considered a feature.

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Wed, 9 Jan 2019 17:31:12 -0500

I’m just worried about Ians comment about one endpoint being able to stall
key updates.

I can see the separation of processing argument, but you could reformulate
it slightly to not use ACK’s:

A key update is only possible after successfully decoding one packet for
the current locally originated key phase.
Or would that still have a race condition?

Kind Regards,
Mikkel Fahnøe Jørgensen

On 9 January 2019 at 23.13.34, Martin Thomson ([email-masked]) wrote:

> create an other class of misbehavior.

If you look at the history of the PR, I initially proposed using ACK in
exactly this way. The feedback I got was that this was difficult for people
to implement, because it more tightly couples two parts of the processing
pipeline than was previously necessary. That is, if you consider packet
protection as a discrete stage in processing, getting information to and
from the ACK frame processing might be difficult, depending on
implementation structure.

We've been very careful to avoid having protocol behaviour that triggers on
acknowledgment. I don't think that we have any that escape the loss
recovery and CC algorithms. As an architectural principle, I think that is
worth preserving.

> react to reneging the enable bit, and also how to react to peers

That I have done. Of course, as Ian points out, if the bit is never set,
there isn't really any recourse, and that might be valuable enough to be
considered a feature.

---

From: Ryan Hamilton <[email-masked]>
Date: Wed, 9 Jan 2019 15:02:07 -0800

On Wed, Jan 9, 2019 at 2:13 PM Martin Thomson <[email-masked]> wrote:

> exactly this way.  The feedback I got was that this was difficult for
> people to implement, because it more tightly couples two parts of the
> processing pipeline than was previously necessary.  That is, if you
> consider packet protection as a discrete stage in processing, getting
> information to and from the ACK frame processing might be difficult,
> depending on implementation structure.
>
> We've been very careful to avoid having protocol behaviour that triggers
> on acknowledgment.  I don't think that we have any that escape the loss

I'm not sure this principle is that important, but if it is, we could
introduce a new frame for this purpose. KEY_PHASE_RECEIVED, or some such.

---

From: Martin Thomson <[email-masked]>
Date: Thu, 10 Jan 2019 10:16:48 +1100

> introduce a new frame for this purpose. KEY_PHASE_RECEIVED, or some such.

I think it is.  I know that some implementations provide hooks for acknowledgments, and that wouldn't be prohibited, but it's different if those hooks become mandatory.

A new frame is certainly possible, but it could eliminate what might be a useful feature (disabling key updates).  We'd also need to consider what to do about this message around the end of the handshake.  One thing Kazuho wants to do is block key updates until 0-RTT keys are discarded, effectively treating the 0-RTT to 1-RTT transition as a key update.

---

From: Christian Huitema <[email-masked]>
Date: Wed, 9 Jan 2019 16:49:22 -0800

> On Jan 9, 2019, at 3:16 PM, Martin Thomson <[email-masked]> wrote:
> 

You do not have separation today. You only validate the phase bit if it comes from a new packet. The requirement is to only rotate the key if at least one of the current phase packets has been acknowledged. That's a high level sender side decision, typically not something you would delegate to a line card.

> A new frame is certainly possible, but it could eliminate what might be a useful feature (disabling key updates).  We'd also need to consider what to do about this message around the end of the han…

Another issue is that not setting the enabling bit at time T does not mean it will not be set later. So that's not a good way to indicate lack of support for key update. If you want that the proper tool is a transport parameter.

-- Christian Huitema

---

From: Kazuho Oku <[email-masked]>
Date: Thu, 10 Jan 2019 09:50:13 +0900

2019年1月10日(木) 8:02 Ryan Hamilton <rch=[email-masked]>:
> I'm not sure this principle is that important, but if it is, we could introduce a new frame for this purpose. KEY_PHASE_RECEIVED, or some such.

While that's possible, using a frame makes the design complicated,
because a frame is not tied to a particular generation of a traffic
key. An endpoint is allowed to retransmit a frame of lost packet as it
is. That means that you cannot use the generation of the packet that
carried the frame to infer for which key generation the
KEY_PHASE_RECEIVED frame permits an update. Therefore, the design of
such a frame needs to carry the generation of the traffic key as a
number, possibly as a varint field. And the receiver would also be
required to validate that the value is no more than current generation
+ 1.

Compared to that, having the key phase bit and the update permitted
bit next to each other is much simpler.

--
Kazuho Oku

---

From: Martin Thomson <[email-masked]>
Date: Thu, 10 Jan 2019 11:55:26 +1100

On Thu, Jan 10, 2019, at 11:50, Kazuho Oku wrote:
> key.

I'd forgotten that.  Thanks Kazuho.  We could probably fix that by maintaining a counter (or epoch, to use DTLS terminology) that increments with each key update and send that in the frame if we were committed to using frames.  That starts to look like a MAX_KEY_PHASE or MAX_KEY_EPOCH frame.

---

From: Kazuho Oku <[email-masked]>
Date: Thu, 10 Jan 2019 10:36:37 +0900

> You do not have separation today. You only validate the phase bit if it comes from a new packet. The requirement is to only rotate the key if at least one of the current phase packets has been ackn…

The problem of using ACK as a signal is that it could provide a false
illusion that a sender is permitted to update the traffic key whenever
it sees an ACK for a new generation. If the sender falsely assumes
that, it would emit packets that cannot be decrypted by the receiver
that tries to retain minimum number of keys (i.e. 2).

My preference goes to having a design that guarantees the
communication to succeed without requiring the receiver to retain a
greater number of keys than necessary.

> Another issue is that not setting the enabling bit at time T does not mean it will not be set later. So that's not a good way to indicate lack of support for key update. If you want that the proper…

I am not sure if I agree that using a transport parameter is better.

Typically, it is not until the sender actually goes over the threshold
(e.g., send 1G packets) that it knows that the peer needs to support
key updates. Assuming that is the case, there is no difference between
communicating the information during the handshake and when key update
becomes necessary.

-- 
Kazuho Oku

---

From: Victor Vasiliev <[email-masked]>
Date: Thu, 10 Jan 2019 20:18:42 -0500

> recovery and CC algorithms.  As an architectural principle, I think that is

I'm not sure I believe this is a useful principle (if you track
acknowledgements for stream data, tracking anything else is easier).  That
said, you can always make a custom ack frame.

How about something like this:

   1. Peer A sends I_WOULD_LIKE_TO_ADVANCE_THE_KEY_PHASE frame with the
   number of next phase.
   2. Peer B replies with YES_PLEASE_DO_ADVANCE_THE_KEY_PHASE frame as soon
   as it receives Peer A's request.
   3. Peer A can advance the key phase as soon as it gets permission from
   Peer A.

Note that since here you ask for permission and list the phase explicitly,
there is less potential for things changing to fast or peers being confused.

---

From: Christian Huitema <[email-masked]>
Date: Fri, 11 Jan 2019 10:26:43 -0800

On 1/9/2019 5:36 PM, Kazuho Oku wrote:
> ...

I think we all agree that after draft 17, any change to packet format
should clear a very high bar. The PR proposes to add a bit in the header
bit, and is just one such change. I understand it is just one bit, but
then I have some experience when asked to change just one bit in code
that is almost ready to ship. And I would rather not do it, because I do
not believe the change is necessary. I read the thread, and I can count
three issues. I am not convinced that either of those clears the bar.

The first issue is that if peers rotate the key too often, and
especially if they rotate the key often and simultaneously, they could
end up breaking the connection. Well, don't do that.

The second issue is that if a peer rotates keys too quickly, it forces
the other peer to maintain multiple encryption contexts. Key rotation
requires maintaining at least two contexts: old and current, or current
and new. The old context can be disposed of as soon as packets are not
expected from the peer, which is currently defined as 3 RTO. If a
rotation occurs with these 3 RTO, the node may need to keep 3 contexts:
old, current and new. Again, the solution is simple: don't do that. We
could add text to that effect, such as "at least 6 RTO between key
rotations". Or we could simply state that if a peer engages in rotation
N+1, it is effectively discarding all packets still in transit from
rotation N-1, effectively limiting the number of keys to be maintained to 2.

The third issue is not really a protocol issue, but rather a new
functionality. Can nodes limit how often their peers engage in key
rotation? Or, pushed to the max, can an implementation just not support
key rotation at all. My take is that this kind of feature negotiation is
better handled with transport parameters than by adding bits in the
header. I am also very concerned that if an application supports key
rotation there should be an easy way to test it.

-- Christian Huitema

---

From: Kazuho Oku <[email-masked]>
Date: Sat, 12 Jan 2019 13:55:27 +0900

2019年1月12日(土) 3:26 Christian Huitema <[email-masked]>:
> should clear a very high bar.

My understanding is that it is not only the packet format. Any change
to the protocol needs to clear the high bar. The flip side is that we
are free to choose the most appropriate way _if_ we agree that there
is a reason to change.

In this particular case, the new information we have is that the key
update mechanism that we currently have has an issue that the keys
might become out-of-sync.

I think we should fix the issue, and assuming that the WG agrees to
fix the issue, my preferred way of fixing the issue is to introduce
the Key Update Permitted bit, because it is simple and hard to
mis-implement on both the sender and the receiver side, as well as
having the other benefits that we have discussed. Using the key phase
bit "and ACK" to see if the sender can issue another update is
complicated.

> The PR proposes to add a bit in the header

-- 
Kazuho Oku

---

From: Jana Iyengar <[email-masked]>
Date: Thu, 17 Jan 2019 18:06:19 -0800

It seems to me that the issues, while real, are corner cases, since they
require (very) frequent key rotation. As such, I'm tempted to avoid these
corner cases rather than provide protocol behaviors to allow them.

Are there good reasons why key rotation might happen very frequently?

---

From: Kazuho Oku <[email-masked]>
Date: Fri, 18 Jan 2019 12:31:20 +0900

2019年1月18日(金) 11:06 Jana Iyengar <[email-masked]>:
>
> It seems to me that the issues, while real, are corner cases, since they require (very) frequent key rotation. As such, I'm tempted to avoid these corner cases rather than provide protocol behaviors to allow them.
>

I think that is a good question.

I might be concerned about an endpoint that tries to update the key
whenever it tries to use a new network. An endpoint running on a
mobile device (that has a Wifi hardware with support for encryption
offload) might try to install a new key every time the Wifi network
comes up.

Under such a design, when a Wifi network comes up (triggering a key
update) and then immediately becomes unreachable, then if another Wifi
network becomes reachable, the endpoint might try to install different
key twice, if that is permitted by the state of the QUIC connection.

-- 
Kazuho Oku

---

From: Christian Huitema <[email-masked]>
Date: Thu, 17 Jan 2019 18:33:27 -1000

> key twice, if that is permitted by the state of the QUIC connection.

Fine. So maybe we should just say, "don't do that". There is no
functional requirement to change the key when the network changes. If
the endpoints are doing migration, it seems like a really bad idea to
try rotate the keys at the same time.

The other plausible corner case is a very high speed connection, over
which so many packets are sent so quickly that using the same key might
be risky. Section 5.5 of RFC 8446 states that the 64 bit Record Sequence
Number would wrap before that becomes a problem with ChaCha20/Poly1305,
but that after sending more than  2^24.5 full-size records (about 24
million) the safety margin of AES-GCM would drop to 2^-57. QUIC is never
sending full size records, but the most conservative reading of this
paragraph is that keys should be rotated after sending at most 2^24
packets when using AES-GCM. On a 10 Gbps link, that would last 30
seconds, and that's too long to create risks of getting out of sync. It
could only be an issue if the peers were running on a terabit link with
a long RTT. Well, if they do that, the obvious fix is to use
ChaCha20/Poly1305 instead of AES GCM.

-- Christian Huitema

---

From: Kazuho Oku <[email-masked]>
Date: Fri, 18 Jan 2019 14:38:54 +0900

2019年1月18日(金) 13:33 Christian Huitema <[email-masked]>:
> Fine. So maybe we should just say, "don't do that". There is no functional requirement to change the key when the network changes. If the endpoints are doing migration, it seems like a really bad idea to try rotate the keys at the same time.
>
> The other plausible corner case is a very high speed connection, over which so many packets are sent so quickly that using the same key might be risky. Section 5.5 of RFC 8446 states that the 64 bit Record Sequence Number would wrap before that becomes a problem with ChaCha20/Poly1305, but that after sending more than  2^24.5 full-size records (about 24 million) the safety margin of AES-GCM would drop to 2^-57. QUIC is never sending full size records, but the most conservative reading of this paragraph is that keys should be rotated after sending at most 2^24 packets when using AES-GCM. On a 10 Gbps link, that would last 30 seconds, and that's too long to create risks of getting out of sync. It could only be an issue if the peers were running on a terabit link with a long RTT. Well, if they do that, the obvious fix is to use ChaCha20/Poly1305 instead of AES GCM.

Yeah. Practically speaking, I'd assume that you'd need to spend
multiple round-trips to send 2^24 packets due to the size of the
congestion window.

It might also be worth pointing out that an endpoint cannot send more
than 2^pn_bits packets before seeing an acknowledgement from the peer.
My understanding is that most if not all of the QUIC stacks will use a
16-bit packet number, and that means that updating the key less
frequently than every 2^16 packets is guaranteed to be safe.

The issue with the current text is that it incorrectly suggests that
the peer updating the key is a signal that it is ready to accept
another key update. If we are going to fix the issue without changing
the wire format, I think we need to state the overarching rule (that
an endpoint MUST NOT initiate a Key Update unless it knows that the
peer has received a packet protected by the current key) as well as
how to determine that.

For example, something like:
* A sender MUST NOT initiate a Key Update unless it is certain that
the peer has accepted a packet that was encrypted by the current key.
* One way of testing the condition is to examine the ACK frames sent
by the peer; a packet encrypted using the current key being
acknowledged by the peer can be used as the signal.
* The other way is to not instantiate a key update until the previous
update until emitting at least 2^pn_bits packets.
* A sender SHOULD NOT initiate a Key Update earlier than 3-PTO after
the previous switch of application traffic key.

-- 
Kazuho Oku

---

From: Christian Huitema <[email-masked]>
Date: Thu, 17 Jan 2019 22:18:32 -1000

> frequently than every 2^16 packets is guaranteed to be safe.

I would rather not make any assumption like that. It is fairly simple to
use variable length PN encoding. If you have a 19Gbps connection with
even moderate latency, you will need more than 16 bits.

> peer has received a packet protected by the current key) as well as

Yes. Tightening the text makes sense.

> the peer has accepted a packet that was encrypted by the current key.
Yes.
> acknowledged by the peer can be used as the signal.
Yes.
> the previous switch of application traffic key.

I would rather have something simpler than these two clauses. Something
like:

* another way is to not initiate a key update earlier than 3-PTO after
the first packet with the new application traffic key was sent.

-- Christian Huitema

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Fri, 18 Jan 2019 00:29:11 -0800

On 18 January 2019 at 09.19.17, Christian Huitema ([email-masked])
wrote:

How about just requiring an acknowledgment received for at least one packet
with a given key phase before allowing a new key update.

And just a single key phase bit.

Yes, it requires some coordination between crypto layer and ACK processor,
but can anyone seriously argue that would be difficult, especially compared
to all the other complexity, including timer estimates. The information
only transferred asynchronously, so the coordination is quite loose.

---

From: Kazuho Oku <[email-masked]>
Date: Fri, 18 Jan 2019 20:21:21 +0900

> the first packet with the new application traffic key was sent.

I'm not sure if just having the 3-PTO rule is a good way, because it
is possible to have an interval more than 3-PTO between packet
emissions when network change is involved, an event that might
coincide with key updates.

Consider the following example: a client receives a key update,
responds to it with it's key update as it loses the connectivity to
the mobile network. Because the network condition was bad, the
responding packet never reaches the network (and the server). After a
small amount of time (but longer than 3-PTO), the client reconnects to
Wifi, and sends a new packet. Because it offloads encryption to
hardware, it tries to use a new encryption key whenever possible. In
this example, 3-PTO rule does not prevent the client doing another key
update.

I share the view with Martin that we have so far avoided using ACK as
way of signaling a change of state of an endpoint. Assuming that we
need to retain the design pattern, we need to describe a method other
than that uses an ACK. The reason I suggested using of number of
packets (being greater than 2^pn_bits) is because it can be used as
such a signal, at least for certain endpoints. If we are unhappy with
that, we need to look for a different method, however as I have
stated, I do not think a time-based approach works.

PS. OTOH, I think having a 3-PTO rule is good for forbidding
too-frequent updates that lead to loss of packets (because the
receiver might have a limit on the number of decryption keys being
active).

-- 
Kazuho Oku