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

From: MikkelFJ <[email-masked]>
Date: Tue, 01 May 2018 00:10:44 -0700

I support the idea of changing keys only when changing CID, but make it optional until the packet count reaches at most 2^32. CID change can be probalisitic after say 2^31 packets to reduce linkage.

-- 
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-385613697

---

From: Kazuho Oku <[email-masked]>
Date: Tue, 01 May 2018 01:12:36 -0700

@martinthomson 
> 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.

FWIW, picotls doesn't yet have key updates (and I wonder if I would ever implement it). Considering that, I am perfectly fine with dropping key update entirely from QUIC v1, leaving it as an issue to be solved by an extension or v2 issue.

-- 
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-385622096

---

From: MikkelFJ <[email-masked]>
Date: Tue, 01 May 2018 01:33:50 -0700

@kazuho I don't have the numbers fresh in memory, but if you don't do key updates, you limit yourself to a few GB of transfer, or you create a serious security violation because GCM is weak when you send too much data.

Or am I missing something about key updates?

If it isn't already stated, an endpoint should close a conneciton with protocol violation if it does not refresh keys in due time.

-- 
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-385625212

---

From: MikkelFJ <[email-masked]>
Date: Tue, 01 May 2018 01:39:00 -0700

http://www.isg.rhul.ac.uk/~kp/TLS-AEbounds.pdf

-- 
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-385625956

---

From: Kazuho Oku <[email-masked]>
Date: Tue, 01 May 2018 23:35:46 -0700

@mikkelfj Thank you for the link. I have actually been looking for it. And rereading it, I agree that we need to have some form of key update in QUIC (or change PN to a 32-bit value, considering that AES-GCM is the default cipher).

-- 
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-385878429

---

From: Kazuho Oku <[email-masked]>
Date: Thu, 03 May 2018 06:11:48 -0700

Now that #1079 has been merged, and assuming that we would not have per-CID PN, let me propose another simple solution: never update PN protection key throughout the connection, and define the generation of payload protection key as _PN mod 2<sup>32</sup>_.

Since the sample used for PNE is 128 bits long, I would assume (or hope) that we can encrypt 2<sup>62</sup> packet numbers using a single key. In other words, there is no need to update the PN protection key. Then, we can use the value of the decrypted PN to determine the key generation of the payload protection key.

-- 
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-386290369

---

From: Christian Huitema <[email-masked]>
Date: Thu, 03 May 2018 07:00:14 -0700

I like that proposal. It makes key rotation straightforward, and it foes solve the phase bit leakage issue.

-- 
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-386305451

---

From: MikkelFJ <[email-masked]>
Date: Thu, 03 May 2018 09:13:58 -0700

That could work. There is an on path attack where large packet numbers are skipped to expend resources on frequent rekeying, so perhaps som text to guard against this - notably in relation to optimistic ACK packet skipping. I was considering switching between CID's instead of skipping packets - but that is no good if the ACK doesn't care about the path and PN's have one linear space.

-- 
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-386350581

---

From: Marten Seemann <[email-masked]>
Date: Thu, 03 May 2018 16:28:48 -0700

That’s an interesting proposal.
I see a problem that the key rotation is exercised very infrequently. 2^32 packets allow the transfer of roughly 5 TB of data, so only a tiny fraction of QUIC connections will use it at all. And code that doesn’t get used is prone to bugs.

-- 
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-386466700

---

From: janaiyengar <[email-masked]>
Date: Thu, 03 May 2018 17:51:29 -0700

@kazuho: I still believe that per-CID PN is the best way to get to multipath. Even if we don't do it yet, I expect that we will get there eventually. I wouldn't want to make the assumption that we use a single PN space yet.

I like the idea of tying key updates to new CIDs, but there's a gotcha. Both endpoints might decide to do zero-length CIDs, and you then lose any ability to do a key update.

Why not do both? That is, KEY_PHASE bit used as normal, but CID resets the key phase. In other words, CID represents the high-order bits of the key phase, and the KEY_PHASE bit represents the lowest order bit. Does this make sense?

-- 
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-386479321

---

From: Kazuho Oku <[email-masked]>
Date: Thu, 03 May 2018 17:54:57 -0700

@mikkelfj 
> There is an on path attack where large packet numbers are skipped to expend resources on frequent rekeying, so perhaps som text to guard against this - notably in relation to optimistic ACK packet skipping.

I am not sure if that is a realistic attack considering the fact that attacker would be required to spend same amount of CPU cost, and that an attacker cannot trigger key update once every 2 RTT (note: a sender cannot send PN that is greater than the largest acknowledged value + 2<sup>31</sup>).

-- 
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-386479836

---

From: Kazuho Oku <[email-masked]>
Date: Thu, 03 May 2018 18:00:50 -0700

@marten-seemann 
> I see a problem that the key rotation is exercised very infrequently. 2^32 packets allow the transfer of roughly 5 TB of data, so only a tiny fraction of QUIC connections will use it at all. And co…

I share the concern, and I think that we can grease the feature. One way would be to occasionally start with a PN near 2<sup>32</sup>. The other way would be to for some portion of connections inject huge gaps during the early stages of the connection so that the PN would soon become above 2<sup>32</sup>.

-- 
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-386480587

---

From: Marten Seemann <[email-masked]>
Date: Thu, 03 May 2018 18:09:43 -0700

Is there any limit on how many key updates can safely be done? If not, another option would be to lower the threshold to e.g. 2^16 (this would correspond to roughly 80MB of data transferred). This would ensure that a significant fraction of QUIC connections would 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/issues/1322#issuecomment-386481756

---

From: Kazuho Oku <[email-masked]>
Date: Thu, 03 May 2018 18:19:18 -0700

@janaiyengar 
> I like the idea of tying key updates to new CIDs, but there's a gotcha. Both endpoints might decide to do zero-length CIDs, and you then lose any ability to do a key update.

Agreed.

> Why not do both?

I think that I at least agree with you that my proposal of eliminating the KEY_PHASE bit by using PN mod 2<sup>32</sup> as the generation number is orthogonal to the discussion of #1317.

> That is, KEY_PHASE bit used as normal, but CID resets the key phase. In other words, CID represents the high-order bits of the key phase, and the KEY_PHASE bit represents the lowest order bit. Does this make sense?

That should be possible, but it might be better to derive the first generation of the encryption key using HKDF that takes CID as the input, then update the key for every 2<sup>32</sup> PN. This is because we cannot skip key generations in the current derivation formula, which is: `client_pp_secret<N+1> =
  QHKDF-Expand(client_pp_secret<N>, "client 1rtt", Hash.length)`.

-- 
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-386482993

---

From: Kazuho Oku <[email-masked]>
Date: Thu, 03 May 2018 18:23:05 -0700

@marten-seemann 
> Is there any limit on how many key updates can safely be done? If not, another option would be to lower the threshold to e.g. 2^16 (this would correspond to roughly 80MB of data transferred). This…

I would prefer setting the threshold to something greater than the largest delta that can be represented by the PN field of a QUIC packet. That property ensures you that having 2 generations of encryption keys is enough, regardless of how the client injects gaps. That is why I proposed 2<sup>32</sup>.

-- 
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-386483533

---

From: Marten Seemann <[email-masked]>
Date: Thu, 03 May 2018 18:42:21 -0700

I don’t know if many implementations would actually implement a key update that only allows ales place after 5 TB of transferred data. In most cases, it would probably be easier to shut down the connection and reconnect.
I also don’t see how we could possibly integration test and interop test this, without manually modifying the constant every time we run a test (which kind of defeats the purpose of such a test 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/1322#issuecomment-386486052

---

From: Kazuho Oku <[email-masked]>
Date: Thu, 03 May 2018 18:46:12 -0700

@marten-seemann Maybe you missed https://github.com/quicwg/base-drafts/issues/1322#issuecomment-386480587? I think you can enforce the use in some ways.

-- 
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-386486489

---

From: Martin Thomson <[email-masked]>
Date: Thu, 03 May 2018 18:47:50 -0700

I don't think that PN mod 2<sup>32</sup> works without trial decryption.

Let's say that we have an 8 bit encoding and we are approaching the crossover point.  When the crossover happens, the recipient uses the old PN key and gets a random 8 bit value, which might be a valid value less than the crossover point.  That packet will fail to be decrypted.

I also agree with @marten-seemann that we should favour designs that are based on explicit signals rather than simple counts.  2<sup>32</sup> is large enough that some implementations might not encounter the rollover point.  I have experience with fixed rollovers in NSS and testing them is ugly.  On the other hand, sending KeyUpdate is easy.  I don't think that a randomized packet number is the right fix for that.

Finally, though I suspect @janaiyengar is right with respect to per-CID spaces, but the decision to roll keys based on a change in connection ID can be made without going that far.  All we need to do is decide to keep the sequencing of connection IDs.  We also need to recognize that two sets of keys might be maintained for some time during migration; that would be somewhat longer than the text currently suggests because of probing, but it's not that much.

-- 
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-386486688

---

From: Kazuho Oku <[email-masked]>
Date: Thu, 03 May 2018 18:59:32 -0700

> Let's say that we have an 8 bit encoding and we are approaching the crossover point. When the crossover happens, the recipient uses the old PN key and gets a random 8 bit value, which might be a va…

@martinthomson Maybe you missed the point that I proposed keeping the PN key stable across the entire connection? https://github.com/quicwg/base-drafts/issues/1322#issuecomment-386290369

-- 
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-386487938

---

From: Martin Thomson <[email-masked]>
Date: Thu, 03 May 2018 19:02:39 -0700

No, I saw that - and it's a necessary precondition for this.  Nonetheless, the problem remains.

-- 
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-386488262

---

From: Kazuho Oku <[email-masked]>
Date: Fri, 04 May 2018 02:05:02 +0000 (UTC)

Then, would you mind clarifying what you mean by “old PN key”?

-- 
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-386488507

---

From: Martin Thomson <[email-masked]>
Date: Thu, 03 May 2018 19:09:44 -0700

Oh, I'm being daft.  I still think that the other reasons are enough.

-- 
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-386488951

---

From: Kazuho Oku <[email-masked]>
Date: Thu, 03 May 2018 19:09:50 -0700

PS. assuming that we can use one PN key across the entries connection, the other solution would be to steal one bit from the varint encoding of the PN (in clear) and use that as the KEY_PHASE bit. The bit will then become unobservable.

-- 
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-386488960

---

From: Martin Thomson <[email-masked]>
Date: Thu, 03 May 2018 20:00:46 -0700

Yes, I have considered that option.  I still prefer coupling connection ID change to key migration.  It has the benefit of consolidating mechanisms for migration and key update, which means that the mechanism is more likely to see use.

-- 
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-386494973

---

From: Kazuho Oku <[email-masked]>
Date: Thu, 03 May 2018 21:51:06 -0700

>  I still prefer coupling connection ID change to key migration. It has the benefit of consolidating mechanisms for migration and key update, which means that the mechanism is more likely to see use.

I can see the benefit. OTOH, there is a downside. As @janaiyengar has pointed out, a server with a zero-length CID cannot let the Connection ID change.

-- 
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-386505276

---

From: Kazuho Oku <[email-masked]>
Date: Thu, 03 May 2018 21:53:10 -0700

FWIW, in https://github.com/quicwg/base-drafts/issues/989#issuecomment-386504853 I have proposed encrypting certain bits (including the KEY_PHASE bit) of the first octet in-place. The pros / cons of the approach is discussed on the comment there.

-- 
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-386505455

---

From: MikkelFJ <[email-masked]>
Date: Thu, 03 May 2018 22:06:41 -0700

Skipping packet numbers to induce key rotation seems like (danish proverb) crossing the creek to fetch water since PNE just gained a linear number space.

-- 
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-386506636

---

From: MikkelFJ <[email-masked]>
Date: Fri, 04 May 2018 01:28:41 -0700

@marten-seemann 
>Is there any limit on how many key updates can safely be done? If not, another option would be to lower the threshold to e.g. 2^16 (this would correspond to roughly 80MB of data transferred). This w…

Yes, sort of. If there is a 1/N chance of a successfull attack on a key, and you have M keys, the chance is improved to M/N. As I understand this ties more to AES than to GCM and since AES is much harder than GCM, this is not an immediate concern, but too many keys is not a good idea.

See 
1.3 Security Degradation for Multiple 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/issues/1322#issuecomment-386536349

---

From: Kazuho Oku <[email-masked]>
Date: Fri, 04 May 2018 18:11:38 +0000 (UTC)

> I can see the benefit. OTOH, there is a downside. As @janaiyengar has pointed out, a server with a zero-length CID cannot let the Connection ID change.

@martinthomson I think I missed one important aspect in my comment here.

The issue with only allowing key update on CID change would mean that an endpoint (both the client and the server) cannot update the key if the peer advertises a zero-length CID.

I'd assume that most clients will be advertising zero-length CIDs. That would mean that for most connections a server would not be able to trigger a key update, unless we allow key updates to happen without migrating the connection.

-- 
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-386688583

---

From: MikkelFJ <[email-masked]>
Date: Fri, 04 May 2018 19:41:09 +0000 (UTC)

Unless keyphase is a degenerate CID. If so, CID's are not zero length, they are at least one 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#issuecomment-386711891

---

From: Martin Thomson <[email-masked]>
Date: Mon, 07 May 2018 00:45:35 +0000 (UTC)

I think that all of this is too complicated.  Here's a simple solution for this issue:

NEW_CONNECTION_ID can carry an extra hard-to-guess bit that masks the KEY_PHASE bit so that it can't be used to correlate flows.

We also recommend that endpoints that don't use connection IDs can randomly do a key update when they migrate to a new path to break linkability.  That creates uncertainty about which half of the population they are correlated with.

-- 
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-386929936

---

From: Kazuho Oku <[email-masked]>
Date: Mon, 07 May 2018 01:30:35 +0000 (UTC)

> NEW_CONNECTION_ID can carry an extra hard-to-guess bit that masks the KEY_PHASE bit so that it can't be used to correlate flows.

I am not sure if that is a good solution. While it is true that we can scramble the initial value, I do not think that it prevents the leak, because an observer can use the fact of the bit belonging to multiple CID's being flipped at the same time as the correlator.

Considering that, I think that we need to encrypt the information in some way. So far, we have seen three proposals:
* a. tie key phase to CID
* b. tie key phase to PN (which it now encrypted)
* c. encrypt key phase using PN key

As discussed, _a_ does not work well when the peer advertises a zero-length CID (which would be the typical behavior for clients). I personally prefer 
_b_ due to the fact that it does not waste a bit on the wire, however I can understand people looking for a more flexible way of flipping the bit, which is _c_.

-- 
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-386933856

---

From: Martin Thomson <[email-masked]>
Date: Mon, 07 May 2018 01:52:00 +0000 (UTC)

Oh, I see, you are also trying to solve the problem for multipath at the same time.  I agree that what I suggested doesn't work for that.

I think that your *b* and *c* are shades of the same design.  Both require that the PN protection key is fixed (or maybe dependent on connection ID).  I'm OK with *c*, but the reduced ability to force an update in *b* is still a concern.  Why not just encrypt phase along with the 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/issues/1322#issuecomment-386936058

---

From: Kazuho Oku <[email-masked]>
Date: Mon, 07 May 2018 02:05:51 +0000 (UTC)

> Oh, I see, you are also trying to solve the problem for multipath at the same time. I agree that what I suggested doesn't work for that.

Yes. That' correct. And we have a restricted form of multipath in v1 (i.e. path probing).

> I think that your _b_ and _c_ are shades of the same design. Both require that the PN protection key is fixed (or maybe dependent on connection ID). I'm OK with _c_, but the reduced ability to force an update in _b_ is still a concern. Why not just encrypt phase along with the packet number?

I am fine with _c_. The trade-offs between _b_ and _c_ (i.e. spending one-bit vs. ease of updating the key) seem minor to me.

-- 
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-386937799

---

From: Brian Trammell <[email-masked]>
Date: Mon, 07 May 2018 06:42:05 +0000 (UTC)

Aside from the architectural correctness of this proposal -- the path really doesn't need to see KEY_PHASE, so we shouldn't expose it -- this discussion does seem to take as given that protecting the KEY_PHASE bit will have actual benefits in preventing linkability, which seems to be to be a very dubious assertion.

Very simple timing analysis in most cases will be **so much more useful** in achieving CID linkability than any of the edge cases we're optimizing away now that I'm afraid any additional benefit here is lost in the underflow -- I've filed details on this on ops-drafts as https://github.com/quicwg/ops-drafts/issues/31

Again, this seems like a perfectly reasonable thing to do for the sake of cleanliness and correctness, but I wouldn't want us to do this with any hope that it is actually useful against linkability.

-- 
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-386972402