Subject: [quicwg/base-drafts] Preventing KEY_PHASE bit from being used as a tool to correlate CIDs (#1322)

From: Kazuho Oku <[email-masked]>
Date: Tue, 24 Apr 2018 07:26:25 +0000 (UTC)

Once we decide to either encrypt PN (#1079) or have per-CID PN (#1317), KEY_PHASE bit will be left as a tool for an observer to correlate CIDs in order to determine which of those CIDs belong to a particular QUIC connection.

Let's consider the case where a client, in an attempt to grease the bit, flips the KEY_PHASE bit for every 65,536 packets it sends. That would mean that it is effectively leaking the 17th bit (from LSB) of an unencrypted PN. The leak would be sufficient for an observer to determine which CIDs belonged to the same connection, for connections consisting of CIDs that carry more than 65,356 packets.

Another bad example is a client that greases the bit for some minor portion of the connections (e.g. 1%). Then, an observer will have a better chance of tracking that 1% of connection.

Considering these two attacks, I think that we should require implementations to flip the KEY_PHASE bit at randomly, and that we should flip either 50% or 100% of the connections that we handle.

The questions are:
* do we need to document such requirements?
* are there any other ways for an observer to use the bit?

-- 
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/1322

---

From: Kazuho Oku <[email-masked]>
Date: Tue, 24 Apr 2018 00:28:28 -0700

The other way to address the issue is to remove the KEY_PHASE bit.

For example, we can remove the bit and instead state that the key phase can be changed only when a new CID is used. When an endpoint receives a new CID, it trial decrypts the packet using the current generation key and the next generation key to see if the key phase has shifted.

-- 
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/1322#issuecomment-383831610

---

From: Martin Thomson <[email-masked]>
Date: Thu, 26 Apr 2018 01:34:32 -0700

> Once we decide to either encrypt PN (#1079) or have per-CID PN (#1317), 

Why not both?!?

-- 
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/1322#issuecomment-384559096

---

From: Kazuho Oku <[email-masked]>
Date: Thu, 26 Apr 2018 05:24:24 -0700

I agree that we should do both.

The intent of the text was to state that preventing leak of information from KEY_PHASE bit that could be used to correlate CIDs, makes sense only if we prevent leak from PN in some way.

-- 
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/1322#issuecomment-384621693

---

From: Christian Huitema <[email-masked]>
Date: Mon, 30 Apr 2018 14:03:14 -0700

I like the idea of using migration to a new CID as an alternative to key rollover. Come to think of it, we could transmit the key phase bit as part of the NEW CONNECTION ID frame. Could even make it a key rollover sequence. But that requires allowing different paths to use different key phases. If all paths migrate to new CID at the same time, we still have leakage.

-- 
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/1322#issuecomment-385527956

---

From: Martin Thomson <[email-masked]>
Date: Mon, 30 Apr 2018 16:57:43 -0700

That sounds like budget encryption, which I think we should avoid like the plague.  See https://github.com/quicwg/base-drafts/issues/1317#issuecomment-385562880 for an alternative 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/1322#issuecomment-385563073

---

From: Kazuho Oku <[email-masked]>
Date: Mon, 30 Apr 2018 20:46:59 -0700

>  Come to think of it, we could transmit the key phase bit as part of the NEW CONNECTION ID frame. Could even make it a key rollover sequence. 

The positive side of the current design is that key updates are unilateral. Using NEW_CONNECTION_ID for signalling means that an endpoint will instruct the peer to update the key. I am not sure if doing so is a good thing.

> If all paths migrate to new CID at the same time, we still have leakage.

I agree that that is an issue. One trivial way of avoiding such an issue is to implement the following strategy:

* endpoints should switch to a new path after sending 2<sup>32</sup> packets on that path
* endpoints should start using an updated key for every 2<sup>61</sup> packets that it sends over one QUIC connection

We might want to suggest something like 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/issues/1322#issuecomment-385592665

---

From: Martin Thomson <[email-masked]>
Date: Mon, 30 Apr 2018 22:17:54 -0700

Key updates require reciprocation.  Using a new connection ID would be the same.  So no change there.

One advantage of coupling NEW_CONNECTION_ID to key updates is that it means that there is a single mechanism that supports migration (and multipath) and key update.  You can't support one without also enabling the other.

One thing I've been concerned about with key update is that no one will implement it.  NSS only very recently grew that capability in TLS 1.3; it's a small feature, but one that took ages to implement because there wasn't much incentive to build it.  We still don't have the DTLS variant because it messes with our timers in ways that are hard to reason about.

I agree that simultaneous migration would be a mistake.  Better to drive rollovers based on packet counts as @kazuho suggests.  Though I think that we can probably ignore the 2<sup>62</sup> limit and throw connections away if they ever get to that point.

-- 
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/1322#issuecomment-385601496