Subject: [quicwg/base-drafts] Timing side-channel on key updates (#2792)

From: Marten Seemann <[email-masked]>
Date: Fri, 14 Jun 2019 00:18:35 -0700

When receiving a packet with an unexpected key phase, an implementation should compute the new keys:
> A receiving endpoint detects an update when the KEY_PHASE bit does not match what it is expecting. It creates a new secret [...] and the corresponding read key and IV using the KDF function provided by TLS.

This creates a timing side-channel, since an attacker can modify the KEY_PHASE bit, thereby making a peer compute the next key generation. The packet will be discarded, since the header is protected by the AEAD, but the fact that the key is computed on receipt of that packet is a side-channel that might be used to recover the header protection key.

The way to avoid this side-channel is to pre-compute the N+1 key when rolling over keys from key phase N-1 to N. An implementation would then use the N+1 keys when receiving a packet with an unexpected KEY_PHASE, in exactly the same way it would do decryption on a packet sent at key phase N.

This however contradicts the text that claims that an implementation may choose to only keep two read keys at any given moment:
> Endpoints MAY limit the number of keys they retain to two sets for removing packet protection and one set for protecting packets. Older keys can be discarded.

Directly after a key update, an implementation would have to store (at least) 3 key generations: N-1 for a duration of 3 PTO, in order to be able to decrypt delayed / reordered packets, N, as well as the precomputed N+1 to avoid the timing side-channel described above.

I don't think that storing 3 keys is a problem (I think @kazuho disagrees, I'll let him explain his reasoning himself), but the spec shouldn't pretend that it's possible to create an implementation that both isn't vulnerable to the timing side-channel and at the same time gracefully handles moderate amounts of reordering around 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/issues/2792

---

From: Kazuho Oku <[email-masked]>
Date: Fri, 14 Jun 2019 01:39:56 -0700

I think you are correct in pointing out that there is a timing side-channel, and that we need to fix the issue.

OTOH, I disagree that requiring all endpoints to be capable of retaining 3 keys is not a good way of fixing the issue due to the following reasons.

Firstly, I do not think we can justify why an endpoint needs to be capable of retaining that much keys, even though Key Update is expected to happen very rarely. The purpose of Key Update is to replace a key after extensive use, we would never be using a key that becomes weak just after couple of PTOs.

Considering that, using 2 keys should be sufficient; 3 keys is likely a sign of a needlessly complex design.

Let's compare the proposal of the 3-key design with a 2-key design (that allows the receiver to delay the installation of the next key for 3 PTO after since Key Update, which is #2788).

In the 3-key design, the next key is installed when a Key Update happens. The old key is disposed 3 PTO after a Key Update, and the slot becomes NULL.

In the 2-key design, installation of the next key and the disposal of the old key happens at the same moment (i.e. 3 PTO after a Key Update). An endpoint would always retain 2 keys once the handshake is confirmed.

To me it seems that the latter is simpler. As stated above, there is no need for doing Key Update every 3 PTO, and therefore, assuming that we need to make a change due to the attack vector, I think we should simply allow endpoints delay the installation of the next key rather than changing the increasing the minimum state that an endpoint needs to be capable of maintaining.

-- 
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/issues/2792#issuecomment-502023289

---

From: Marten Seemann <[email-masked]>
Date: Fri, 14 Jun 2019 02:07:06 -0700

I agree, there's not really a need to do key updates that frequently. However, I like the fact that we're currently defining a clear rule: An endpoint is allowed to update to N+1 as soon as it has received an acknowledgement for a packet sent at key phase N.

> In the 2-key design, installation of the next key and the disposal of the old key happens at the same moment (i.e. 3 PTO after a Key Update). An endpoint would always retain 2 keys once the handshake is confirmed. There is no need for retaining a mapping between packet numbers and key phases. The oddity of the key phase bit directly maps to the decryption key.

You should still keep track of the packet number at which the key update happened, in order to check that the peer is not reusing the old key to encrypt packets after it already switched to new keys. Strictly speaking, this is not required for a working implementation, but it's a really easy check to catch a misbehaving peer (or detect an active attack).

> In the 3-key design, the next key is installed when a Key Update happens. The old key is disposed 3 PTO after a Key Update, and the slot becomes NULL.

As I've mentioned in the discussion in #2788, the reason I'm skeptical about delaying key updates by 3 PTO (and effectively dropping all packets with a higher key phase until this period is over) is that we're replacing a very clear definition by an approximate rule: the PTO is calculated locally, and depending on the network conditions, the two endpoints might have different opinions about the exact value of the PTO. An endpoint that wants to ensure that no packets are dropped due to the unavailability of keys would have no choice but to wait >> 3 PTO. While this should be well within the safety limits of the cipher suites we're using, not having a clear criterion seems to be a sign of suboptimal protocol design.

-- 
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/issues/2792#issuecomment-502032498

---

From: MikkelFJ <[email-masked]>
Date: Fri, 14 Jun 2019 03:13:02 -0700

> I agree, there's not really a need to do key updates that frequently. However, I like the fact that we're currently defining a clear rule: An endpoint is allowed to update to N+1 as soon as it has…

Perhaps we should state that an endpoint should precompute the key early but not update keys too frequently to prevent timing attacks and overhead.

> An endpoint that wants to ensure that no packets are dropped due to the unavailability of keys would have no choice but to wait >> 3 PTO. 

That is not necessarily a bad thing, but it is unfortunate that there is no clear definition. We could also say the idle timeout period.

As long as we compute keys using SHA256 it might not be a concern, but computing keys too frequently could exhaust safety parameters on other potentially faster algorithms.

-- 
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/issues/2792#issuecomment-502053786

---

From: ianswett <[email-masked]>
Date: Fri, 14 Jun 2019 06:18:51 -0700

To clarify, the key phase bit is inside header protection, so the attacker in question is the peer?

-- 
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/issues/2792#issuecomment-502106032

---

From: Marten Seemann <[email-masked]>
Date: Fri, 14 Jun 2019 06:27:22 -0700

@ianswett: No, this is an on-path attack. Header protection is not authenticated, so an attacker can just flip bits in the header. Decrypting the packet will fail then, since the header is part of the authenticated data used in the AEAD.
We have a timing side-channel as soon as we treat packets differently based on values in the unprotected header, before authenticating the packet. This is analogous to the [timing side channel using packet number](https://quicwg.org/base-drafts/draft-ietf-quic-tls.html#rfc.section.9.4).

-- 
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/issues/2792#issuecomment-502108828

---

From: ianswett <[email-masked]>
Date: Fri, 14 Jun 2019 06:31:58 -0700

Thanks for the extra explanation, I'm not sure that's a very good side-channel, but I agree it is one.

-- 
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/issues/2792#issuecomment-502110270

---

From: Nick Banks <[email-masked]>
Date: Fri, 14 Jun 2019 07:18:31 -0700

Does anyone have any ideas what kind of actual attack could take advantage of this? The attacker can only cause you to install your keys early once per key phase change. Assuming you hardly every change key phase, what then? I agree it's a way the unauthenticated attacker can change your state, but I don't think it's a big enough problem we need to worry about fixing.

-- 
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/issues/2792#issuecomment-502126987

---

From: Marten Seemann <[email-masked]>
Date: Fri, 14 Jun 2019 07:29:41 -0700

> Does anyone have any ideas what kind of actual attack could take advantage of this?

That's a good question. I agree that this attack vector doesn't look very promising at first sight, but then again I'm always surprised what cryptanalysts can extract from a single bit.

> The attacker can only cause you to install your keys early once per key phase change.

That depends. If you create the new keys, try decrypt the packet, and then discard the keys (if decryption fails), the attacker has an unbounded number of tries. Obviously, this would also be a DoS vector, since computing new keys is more than order of magnitude more expensive than an AEAD operation (at least in my implementation). If you cache the new keys once they are computed, then the attacker indeed only has a single shot per key phase. However, then you might as precompute the new keys when installing the current key phase.
The problem with that is that the spec currently suggests that you only ever need to keep state for 2 key generations at any given moment. This is incompatible with caching the keys for the next key phase, as I described above.

-- 
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/issues/2792#issuecomment-502131227

---

From: Kazuho Oku <[email-masked]>
Date: Fri, 14 Jun 2019 07:53:27 -0700

@marten-seemann 
> I agree, there's not really a need to do key updates that frequently. However, I like the fact that we're currently defining a clear rule: An endpoint is allowed to update to N+1 as soon as it has…

But the current spec. also recommends to wait for 3 PTO before initiating the next Key Update. That would not change, and as we agree, nothing in practice requires us to do Key Updates every 3 PTO.

> You should still keep track of the packet number at which the key update happened, in order to check that the peer is not reusing the old key to encrypt packets after it already switched to new key…

I agree that an endpoint might still want to track the packet number at which key update happened. But even in such case, the simplicity of the 2-key design still exists, in sense that you'd only use it for detecting a suspicious peer. It's much straightforward and easier to test, because the rare case (of actually using 3 keys at the same time) never happens.

To clarify, I am not saying that 3-key design is incorrect. My argument is that lack of clear signal is a non-issue (because there is no need to do a Key Update every 3 PTO or more frequently), and that therefore that argument cannot be used for prohibiting people to choose the 2-key design (which is simpler).

-- 
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/issues/2792#issuecomment-502140161

---

From: Mike Bishop <[email-masked]>
Date: Fri, 14 Jun 2019 08:35:16 -0700

Isn't the middle ground here to pre-compute the N+1 key when the N-1 key is dropped, with the drop happening at the first of:
  - 3xPTO after the N key was first used
  - First arrival of a packet which purports to be N+1

The attacker's ability at that point would be to cause any delayed N-1 packets to be dropped, but if we're presuming the ability to bit-flip, they can cause those packets to be invalid and dropped anyway.

-- 
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/issues/2792#issuecomment-502156288

---

From: Kazuho Oku <[email-masked]>
Date: Sun, 16 Jun 2019 23:24:19 -0700

@MikeBishop That certainly reduces the information being potentially exposed to the attacker every one bit per key update.

But no less than that for example when an attacker injects two packets slightly more frequent than every 3 PTO, with the only difference between the two packets being the value of the KEY_PHASE bit. In such an attack scenario, the attacker can tell which of the two packets caused the calculation of the updated key for every key update.

Admittedly, the leak is tiny; but I am not sure if it is tiny enough that we can ignore.

-- 
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/issues/2792#issuecomment-502550441