Subject: [quicwg/base-drafts] per-CID PN space? (#1317)

From: Kazuho Oku <[email-masked]>
Date: Sun, 22 Apr 2018 19:45:03 -0700

It seems to me that any PNE scheme without an accompanying checksum is fragile to side-channel attacks [\[1\]](https://github.com/quicwg/base-drafts/pull/1079#issuecomment-383438404), assuming that an receiver might drop a packet that contains a PN that it has already seen without decrypting the payload [\[2\]](https://github.com/quicwg/base-drafts/pull/1079#issuecomment-382459179). However I am not sure if we want to accept the overhead of including the checksum of PN in every packet.

Leak of PN is a privacy issue because we share a single PN space among multiple CIDs.

Considering that, it might be a good idea to consider if we can have different PN space for each CID.

As an example, I think that the making following changes to the drafts would be sufficient to have per-CID PN space.

* maximum value of the Sequence field in the NEW_CONNECTION_ID frame (hereafter referred to as _CID sequence number_) will be set to UINT32_MAX. Note that CID sequence number is never reused.
* CID sequence number of the first CID will be changed from -1 to 0
* every ACK frame will have a CID sequence number field. The field carries the sequence number of the CID to which the acked packets belong
* AEAD nonce will be the concatenation of the CID sequence number and the per-CID packet number, which will be 94-bits long. Per RFC 5116, we can reasonably assume that every AEAD scheme will be capable of handing a nonce of that size.

The pros of the approach are:
* PN leak is no longer a privacy concern. It becomes purely an ossification issue that can be resolved separately.
* RTT can be measured separately for each CID

The primary concern will be that the implementations will be required to record PNs and send ACKs for each CID rather than for the entire connection. If that is a deal-blocker, we can consider retaining the current ACK format by changing the proposed approach so that the concatenation of CID sequence number and the per-CID PN would fit into 62-bits (e.g., 16-bit CID sequence number and 46-bit PN).

On the sender side, we can continue living with just one loss recovery / congestion control device per connection. This is because in QUIC v1 a sender never sends retransmittable frames through under multiple CIDs at the same time.

[1] https://github.com/quicwg/base-drafts/pull/1079#issuecomment-383438404
[2] https://github.com/quicwg/base-drafts/pull/1079#issuecomment-382459179

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

---

From: MikkelFJ <[email-masked]>
Date: Sun, 22 Apr 2018 23:24:37 -0700

This is largely the same as my proposal here:
Segmented Packet Numbers
https://github.com/quicwg/base-drafts/issues/1105

-- 
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/1317#issuecomment-383467507

---

From: Kazuho Oku <[email-masked]>
Date: Mon, 23 Apr 2018 08:11:02 +0000 (UTC)

@mikkelfj Thank you for the link. I had missed that.

It would depend on each person's view, but I hope that this issue will be considered as discussing about a specific issue (i.e. none of the proposed PNE schemes being resistant to side-channel attacks without additional overhead for checksum), along with one way of fixing the 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/1317#issuecomment-383490943

---

From: Antoine Delignat-Lavaud <[email-masked]>
Date: Mon, 23 Apr 2018 05:25:09 -0700

As long as the same cryptographic key can be used on different connection IDs, it is a bad idea to segregate the packet number space for the same reason packet gaps are a bad idea - it unnecessarily increases the risk of AEAD nonce re-use, which (as has been repeated countless times, and illustrated in bad implementations) a catastrophic event that collapses connection integrity.

For any given key, best practice is to use a counter to guarantee unique nonces.

The problem of making packet numbers unlinkble between connection ID can be easily solved while maintaining such a counter. This is done by blinding the PN sent on the network with a random offset derived from the crypto secret and the connection identifier. This ensures that any two blinded PN are indistinguishable on the network but remain a simple counter for the endpoints. The same approach is used in TLS 1.3 to blind the ticket age.

-- 
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/1317#issuecomment-383556564

---

From: Kazuho Oku <[email-masked]>
Date: Mon, 23 Apr 2018 05:41:52 -0700

@ad-l 
> For any given key, best practice is to use a counter to guarantee unique nonces.

That is true. And that is what the PR proposes. It proposes to use the concatenation of two counters that monotonically increase (CID sequence number and per-CID PN).

-- 
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/1317#issuecomment-383561047

---

From: Antoine Delignat-Lavaud <[email-masked]>
Date: Mon, 23 Apr 2018 12:50:07 +0000 (UTC)

@kazuho Sorry, I misunderstood your definition of CID sequence number, your proposal is to include a unique counter tied to the connection ID to the AEAD nonce. This guarantees unique nonce and is indeed OK

-- 
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/1317#issuecomment-383563432

---

From: ianswett <[email-masked]>
Date: Mon, 23 Apr 2018 13:56:51 +0000 (UTC)

Re: "On the sender side, we can continue living with just one loss recovery / congestion control device per connection. This is because in QUIC v1 a sender never sends retransmittable frames through under multiple CIDs at the same time."

PATH_CHALLENGE and PATH_RESPONSE frames generate acknowledgements, and are sent on the non-default path, so extra care has to be taken to not cause the acknowledgement of these packets to cause packets on the current default path to be acknowledged.

Once you have per-CID PN spaces, a way to ack them in a single QUIC frame or packet, and separate loss recovery contexts for each, you've pretty much created multipath.  Except for some text, I don't think there's much left?

-- 
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/1317#issuecomment-383584368

---

From: Kazuho Oku <[email-masked]>
Date: Mon, 23 Apr 2018 07:32:21 -0700

@ianswett 
> PATH_CHALLENGE and PATH_RESPONSE frames generate acknowledgements, and are sent on the non-default path, so extra care has to be taken to not cause the acknowledgement of these packets to cause packets on the current default path to be lost.

Thank you for pointing that out. I had missed that.

OTOH, I think it is still true that the proposed approach does not introduce any additional complexity, considering the fact that such requirement exists regardless of how PN for each path is numbered.

> Once you have per-CID PN spaces, a way to ack them in a single QUIC frame or packet, and separate loss recovery contexts for each, you've pretty much created multipath. Except for some text, I don'…

Yeah. That is the interesting side-effect. But maybe we should not call this a multipath because it's not in the scope of v1. Much like we do not call QUIC something, something that Jana will kill you.

-- 
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/1317#issuecomment-383596665

---

From: janaiyengar <[email-masked]>
Date: Mon, 23 Apr 2018 22:41:47 +0000 (UTC)

@kazuho : Thank you for writing up this issue. This is exactly the alternative design I had thought of in London. As @ianswett notes, if we were to go here, I suspect this bridges most of the gap from where we are to multipath. I agree that while it's not in scope for v1, if this (i) can be implemented simply for the non-multipath case, and (ii) can be extended by implementations to experiment with multipath, then we're headed in the right direction.

Thinking about this some, I think this is plausible. The current approach of using PNE or whatever, as you note, has exactly the same requirements as this mechanism does, in that a single loss recovery context with exceptions can handle both. If extended however, which we don't need to specify in v1, then multipath is achievable.

-- 
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/1317#issuecomment-383745711

---

From: Christian Huitema <[email-masked]>
Date: Mon, 30 Apr 2018 20:57:26 +0000 (UTC)

This is certainly a plausible design, but can you explain how it prevents the key phase bit linkage issue?

The key rollover is required because only so many packets can be sent with the same key. In the proposed design, all paths use the same key. Doesn't it follow that the key needs to roll at the same time on all paths?

-- 
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/1317#issuecomment-385526473

---

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

I've been casually considering whether to couple changing connection ID to key update.  That would mean that we can't remove the sequence number from NEW_CONNECTION_ID, but it would remove the KEY_PHASE bit and accomplish the same ends as this proposes, without having to grapple with separate packet number spaces.  The only problem this introduces is that with multipath you get much less coherent sequences of packet numbers as each path has different latency and loss characteristics, which might lead to ACK frames encoding less efficiently.

-- 
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/1317#issuecomment-385562880

---

From: ianswett <[email-masked]>
Date: Mon, 30 Apr 2018 17:14:15 -0700

I think multipath is likely to cause large gaps in packet number spaces or other reasons why ACK frames would be encoded less efficiently, so if that's the only negative, we should probably do this.

-- 
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/1317#issuecomment-385566008

---

From: Kazuho Oku <[email-masked]>
Date: Mon, 30 Apr 2018 18:06:21 -0700

@huitema 
> This is certainly a plausible design, but can you explain how it prevents the key phase bit linkage issue?

It does not. Having separate PN per CID provides resistance to side channels attacks that try to recover an encrypted PN.

-- 
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/1317#issuecomment-385573851

---

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

@martinthomson 
> I've been casually considering whether to couple changing connection ID to key update. That would mean that we can't remove the sequence number from NEW_CONNECTION_ID, but it would remove the KEY_PHASE bit and accomplish the same ends as this proposes, without having to grapple with separate packet number spaces.

Clarification question: is the proposal suggesting to require key update for every new Connection ID That would mean that the endpoints need to maintain N encryption / decryption contexts where N is the number of paths, whereas the current maximum is 2.

I think that is a trade-off that we need to consider, since IIRC we did not favor having different encryption context per every CID in Melbourne.

An alternative design that does not require per-path encryption context is to let the client _optionally_ update the key as described in https://github.com/quicwg/base-drafts/issues/1322#issuecomment-383831610).

-- 
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/1317#issuecomment-385575555

---

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

Yes, during the period that you are probing one path and using another, there would be two sets of keys in play.  If we went full multipath, then we'd need one key per path.  Keep in mind that a set of keys is pretty small - 44 octets plus overheads - much smaller than the amount of state you need to keep for a migration.

I'm not a big fan of trial decryption, even as constrained as your suggestion would have.

-- 
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/1317#issuecomment-385602263