Subject: Go Back to Single Packet Number Space

From: Nick Banks <[email-masked]>
Date: Wed, 25 Jul 2018 19:29:41 +0000

Hello Folks,

I have opened a GitHub Issue (#1579<https://github.com/quicwg/base-drafts/issues/1579>) and Pull Request (#1591<https://github.com/quicwg/base-drafts/pull/1591>) for this topic, but it seems progressed has stalled, so I figured I should take it to the list.

While implementing draft-13, I came across a number of pain points related to using multiple packet number spaces. A lot of the issues result in duplicated state (and associated memory) for all the packet number spaces. But more importantly, the multiple packet number spaces bring in a lot more complexity of logic, compared to the previous single packet number space design. There is a lot more detail in the GitHub issue, and I'd ask that folks take a look at it (and the PR) and provide any feedback they might have. I feel that my Issue adequately describes the problem and my PR provides good (if not better, IMO) solutions to the problems that were fixed previously with multiple packet number spaces. I believe having a single packet number space will drastically simplify implementations in the end.

Finally, as QUIC V1 (2?) is coming to a close (hopefully) I feel like we should resolve this issue soon. I don't want this issue to slip out into the next version.

Thanks,
- Nick

---

From: Martin Thomson <[email-masked]>
Date: Thu, 26 Jul 2018 11:41:48 +1000

The feedback I've heard is that the simplification is subjective.
Others have said that a single space would complicate their
implementation considerably more.  You might want to say more about
that.

The loss of acknowledgements during the Initial phase has the
unfortunate effect of forcing implementations to rely on implicit
acknowledgment.  This doesn't seem like a problem now, but we're close
to the quantum computer cryptographic apocalypse (put that on a
sandwich board and yell it on street corners folks!) and this sort of
reduction in capability could serious impair our ability to ship a key
exchange that doesn't have problems.

Now, this latter thing is not an unfixable problem if you cared about
it, but it depends on what your real problem is.
On Thu, Jul 26, 2018 at 5:29 AM Nick Banks
<nibanks=[email-masked]> wrote:
>
> Hello Folks,
>
>
>
> I have opened a GitHub Issue (#1579) and Pull Request (#1591) for this topic, but it seems progressed has stalled, so I figured I should take it to the list.
>
>
>
> While implementing draft-13, I came across a number of pain points related to using multiple packet number spaces. A lot of the issues result in duplicated state (and associated memory) for all the packet number spaces. But more importantly, the multiple packet number spaces bring in a lot more complexity of logic, compared to the previous single packet number space design. There is a lot more detail in the GitHub issue, and I’d ask that folks take a look at it (and the PR) and provide any feedback they might have. I feel that my Issue adequately describes the problem and my PR provides good (if not better, IMO) solutions to the problems that were fixed previously with multiple packet number spaces. I believe having a single packet number space will drastically simplify implementations in the end.
>
>
>
> Finally, as QUIC V1 (2?) is coming to a close (hopefully) I feel like we should resolve this issue soon. I don’t want this issue to slip out into the next version.
>
>
>
> Thanks,
>
> - Nick

---

From: Nick Banks <[email-masked]>
Date: Thu, 26 Jul 2018 02:36:03 +0000

A lot more has already been discussed related to this on the issue, but I can expand on some of it here.

The design for managing sent packets and handling ACK frames for them for the two designs looks as follows:

Single Packet Space

  *   A single list of sent packet metadata objects, and other loss detection/recovery state (largest packet number, last sent time, RTO timer…).
  *   Each metadata object has 2 bits for tracking encryption level used to send the packet.
  *   On receipt of an ACK frame, encryption level and frame are passed to the ACK processing logic. This logic traverses the list of sent packets and just verifies that the received encryption level >= to the original level.

Multiple Packet Spaces

  *   Three lists of sent packet metadata objects and their associated loss detection/recovery state.
  *   On receipt of an ACK frame, encryption level and frame are passed to the ACK processing logic. The encryption level indicates when sent packet list to search.

The logic complexity of processing the ACK is pretty much the same, but the multiple packet spaces has a lot more state tracking. Additionally, how packet loss works across packet levels is not well explained. With single packet space, there is no extra complexity for cross-packet space loss recovery.

On the side of the acknowledger, there is a lot more complexity. Again, keeping three times the state to track which packets numbers are outstanding in which encryption level is a burden. The most painful part (at least for my code) is when it times to generate all the necessary packets given the current state. Taking those three sets of packet number to acknowledge and generate all the correctly formatted packets in the appropriate encryption levels in quite involved. My logic for deciding what type of packet to frame next and what can/should be put in it still has bugs after working on it for a few weeks. With a single packet number space, you only keep 1 set of packet numbers to acknowledge, and the highest encryption level for a packet number that needs to be acknowledged. Then, you send a single packet, with a single ACK frame at that highest encryption level (or higher), and you are done.

Bottom line, multiple packet numbers require 3 times the state and require a lot of additional logic to manage, both on the send and receive side. IMO, this is a lot of complexity that is not needed, and is overkill for what usually is just 1 or 2 RTT of the entire connection.

- Nick

-----Original Message-----
From: Martin Thomson <[email-masked]>
Sent: Wednesday, July 25, 2018 6:42 PM
To: Nick Banks <[email-masked]>
Cc: QUIC WG <[email-masked]>
Subject: Re: Go Back to Single Packet Number Space

Others have said that a single space would complicate their implementation considerably more.  You might want to say more about that.

The loss of acknowledgements during the Initial phase has the unfortunate effect of forcing implementations to rely on implicit acknowledgment.  This doesn't seem like a problem now, but we're close to the quantum computer cryptographic apocalypse (put that on a sandwich board and yell it on street corners folks!) and this sort of reduction in capability could serious impair our ability to ship a key exchange that doesn't have problems.

Now, this latter thing is not an unfixable problem if you cared about it, but it depends on what your real problem is.

On Thu, Jul 26, 2018 at 5:29 AM Nick Banks <nibanks=[email-masked]<mailto:nibanks=[email-masked]>> wrote:

---

From: Dmitri Tikhonov <[email-masked]>
Date: Wed, 25 Jul 2018 23:01:36 -0400

On Thu, Jul 26, 2018 at 11:41:48AM +1000, Martin Thomson wrote:
> implementation considerably more.

EKR is one of the "others" [1] -- are there other implementers who
prefer the triple packet space?

  - Dmitri.

1. https://github.com/quicwg/base-drafts/issues/1579#issuecomment-405720217

---

From: Tommy Pauly <[email-masked]>
Date: Wed, 25 Jul 2018 21:26:49 -0700

As another implementer, I also prefer having the split packet spaces. The point isn't necessarily that it's good to have the triple spaces, but rather that it's nice to have the packet number spaces correspond tightly with the packet types and protection. The logic for handling a space can be treated more uniformly in that way, although it does involve potentially more memory to store the state.

Thanks,
Tommy

> On Jul 25, 2018, at 8:01 PM, Dmitri Tikhonov <[email-masked]> wrote:
>

---

From: Nick Banks <[email-masked]>
Date: Thu, 26 Jul 2018 04:37:05 +0000

Since there are four encryption levels, the fact that there are only three packet spaces only makes things more confusing IMO. If your argument is that matching them together makes things easier, then I’d think there should be four packet spaces. I think having all this duplication and separation just adds unnecessary complexity.

Sent from my Windows 10 device

[HxS - 15254 - 16.0.10325.20083]

________________________________
From: [email-masked] <[email-masked]> on behalf of Tommy Pauly <[email-masked]>
Sent: Wednesday, July 25, 2018 9:26:49 PM
To: Dmitri Tikhonov
Cc: Martin Thomson; Nick Banks; QUIC WG
Subject: Re: Go Back to Single Packet Number Space

Thanks,
Tommy

> 1. https://na01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fquicwg%2Fbase-drafts%2Fissues%2F1579%23issuecomment-405720217&amp;data=02%7C01%7Cnibanks%40microsoft.com%7C86b0eb2ea03c48a3fc7808d5f2b00684%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C1%7C636681760204180396&amp;sdata=fstGdvwnKKfApVKVQZFuJYdWAZkXCafUsEH0t1YtH8U%3D&amp;reserved=0
>

---

From: Praveen Balasubramanian <[email-masked]>
Date: Thu, 26 Jul 2018 05:14:50 +0000

I agree that multiple PN spaces are confusing and seem unnecessary. Loss recovery would be much simplified by having a single PN space. Its also easier to reason about the state of loss recovery and for debugging and diagnostics. The lower memory overhead is also a factor. We should aim for a simple design unless there is a strong reason not to. Single PN space was how the design was before draft 13 so I don't understand why there would be complications for implementation. Please note that you can trivially change the sender to have a single PN space by just using consecutive PN for the 3 spaces! And the receiver ACK tracking logic would be simplified as well.

From: QUIC <[email-masked]> On Behalf Of Nick Banks
Sent: Wednesday, July 25, 2018 9:37 PM
To: Tommy Pauly <[email-masked]>; Dmitri Tikhonov <[email-masked]>; [email-masked]
Cc: Martin Thomson <[email-masked]>
Subject: RE: Go Back to Single Packet Number Space

Since there are four encryption levels, the fact that there are only three packet spaces only makes things more confusing IMO.. If your argument is that matching them together makes things easier, then I'd think there should be four packet spaces. I think having all this duplication and separation just adds unnecessary complexity.

From: [email-masked]<mailto:[email-masked]> <[email-masked]<mailto:[email-masked]>> on behalf of Tommy Pauly <[email-masked]<mailto:[email-masked]>>

Thanks,
Tommy

> On Jul 25, 2018, at 8:01 PM, Dmitri Tikhonov <[email-masked]<mailto:[email-masked]>> wrote:
>
> 1. https://na01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fquicwg%2Fbase-drafts%2Fissues%2F1579%23issuecomment-405720217&amp;data=02%7C01%7Cnibanks%40microsoft.com%7C86b0eb2ea03c48a3fc7808d5f2b00684%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C1%7C636681760204180396&amp;sdata=fstGdvwnKKfApVKVQZFuJYdWAZkXCafUsEH0t1YtH8U%3D&amp;reserved=0<https://na01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fquicwg%2Fbase-drafts%2Fissues%2F1579%23issuecomment-405720217&data=02%7C01%7Cpravb%40microsoft.com%7C7a6598c7f2734f21a24508d5f2b1798b%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C636681766425990424&sdata=FKfn6LZV%2Fn9fbyja6Ug6hUQZdzvdVpnvqZdgmu3hChk%3D&reserved=0>
>

---

From: "Eggert, Lars" <[email-masked]>
Date: Thu, 26 Jul 2018 06:42:27 +0000

For my implementation, I prefer the single space. My data structures are very similar to what Nick described.

-- 
Sent from a mobile device; please excuse typos.
+49 151 120 55791

> On Jul 26, 2018, at 05:02, Dmitri Tikhonov <[email-masked]> wrote:
>

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Wed, 25 Jul 2018 23:56:50 -0700

I am not currently working on handshake so I don’t have detailed insights
but I see the following concerns:
As Nick writes:

   - Each metadata object has 2 bits for tracking encryption level used to
   send the packet.

This is a problem it you create a highly optimised data structure for the
general receive case. You double or triple the state you need in bitmaps
etc. - yes the counter argument is that you need more state for
retransmission, but these indices use critical cache buffers and
retransmission is rare and can be on disk or main memory.

By having separate packet number spaces you can afford a slower less
optimized logic isolated to the handshake and simplify the logic in the
main case.

So a single number space may be simpler for simpler implementation but more
complex for an advanced implementation.

A counter argument:

The initial handshake requires more state with multiple spaces. This means
that handshake must be done a  specially allocated control block otherwise
the main connections control block will be larger than necessary. This
could be a trade-off between indirection and minimum space required for
long living silent connections.

I believe the extra initial space is not actually a problem because you can
hand-over a read connection to the main connection logic. The additional
memory required during the connection can be a concern, but it isn’t likely
a problem because:  If you are a constrained device you only deal with one
connction at a time and refuse concurrent handshakes. If you are a massive
server, you can easily handle the overhead of 100K concurrent connections
each tracking 4 packet numbers for the duration of a handshake - as long as
the overhead does not spill into the long-term connection.

And finally, keeping the handshake logic out of the main connection makes
it much simpler to experiment with alternative handshakes, for example a
simple pre-shared static key for exchanging traffic keys.

Therefore, I prefer keeping the handshake logic separate from the main
connection as much as possible.

Kind Regards,
Mikkel Fahnøe Jørgensen

On 26 July 2018 at 08.42.52, Eggert, Lars ([email-masked]) wrote:

   - Each metadata object has 2 bits for tracking encryption level used to
   send the packet.

---

From: Kazuho Oku <[email-masked]>
Date: Thu, 26 Jul 2018 17:33:32 +0900

I prefer having split packet number spaces, because in addition to
what Martin says, I feel uneasy about allowing a receiver to
acknowledge a packet "in a greater than or equal encryption level."

My understanding is that this the key of the proposal. Use of a
unified packet number space makes sense only when an endpoint can send
an acknowledgement for all packets that it has received in one
encryption level.

This does sound like a nice hack, but I wonder if it might be too
fragile to changes in TLS that might happen in the future.

At the moment, there is one issue, which might be subtle.

Consider the case where the client is sending it's 2nd flight that
consists of a Handshake packet containing ClientFinished (and
optionally Certificate, CertificateVerify), and a 1-RTT packet
containing application data. At this point, the client knows the 1-RTT
write key, and because the server typically sends NST at the same time
it sends ServerFinished using 0.5 RTT data, the client will be
required to send ACK as part of the 1-RTT packet.

This means that if the Handshake packet gets lost, the server will not
be able to process the ACK even if the packet that contained the ACK
reaches the server, because 1-RTT read key on the server-side is yet
to be activated.

I am not sure how important this issue is.

It might cause excessive retransmits from the server than what we
would see in the separate packet number space approach. The fact that
the server will be sending RTO packets while the user selects his /
her certificate using the client-side UI makes me giggle, but it might
not be a big deal.

However, the existence of such issues make me wonder that the proposal
is relying too much on the details of TLS 1.3. And I am not sure if
the issue explained here is the only problem.

Considering the fact that having split packet number space is just
about having an ACK queue for 3 levels, I would prefer retaining
current design rather than implementing a "hack" that could have
corner cases.

-- 
Kazuho Oku

---

From: Patrick McManus <[email-masked]>
Date: Thu, 26 Jul 2018 08:15:27 -0400

> an acknowledgement for all packets that it has received in one
This sums up my feelings as well - I really like the explicitness of the
separate spaces.

---

From: Nick Banks <[email-masked]>
Date: Thu, 26 Jul 2018 14:04:50 +0000

First, I think we should limit the discussion to what actually is in V1. Things like post quantum crypto and possible future TLS changes are interesting to reason about, but should have no immediate bearing on the design right now. If things change in the future that might cause additional issues, we should handle them in a future version.

Second, on the topic of only acknowledging packets at a greater than or equal encryption level being even harder or less efficient to implement, while I whole-heartedly disagree, I was thinking about this, and feel we could actually go one step further. Already I have proposed disallowing ACKs in Initial packets and allowing 0-RTT packets to be acknowledged in Handshake packets. We could instead just say no ACKs in Initial packets, but all other packets can acknowledge any other packet. No encryption level requirements at all. The obvious possible point of contention with this, is that it would allow Handshake packets to acknowledge 1-RTT packets. While it is a ‘lower’ encryption level (I don’t really know what that means) both Handshake and 1-RTT keys are keys only the endpoints know. I don’t see any harm in temporarily (as long as you accept Handshake packets) allowing Handshake packets to acknowledge 1-RTT packets. With this design, an implementation that needs to acknowledge something can then do whatever it likes, so long as it doesn’t use an Initial packets.

Next, for not explicitly sending ACK frames in Initial packets, I personally don’t see the explicit event of TLS changing read encryption keys from initial to handshake as an implicit signal. To me, it seems very reasonable to call that out as the explicit signal to treat your initial packet(s?) as acknowledged.

- Nick

From: Patrick McManus <[email-masked]>
Sent: Thursday, July 26, 2018 5:15 AM
To: Kazuho Oku <[email-masked]>
Cc: Martin Thomson <[email-masked]>; Nick Banks <[email-masked]>; QUIC WG <[email-masked]>
Subject: Re: Go Back to Single Packet Number Space

On Thu, Jul 26, 2018 at 4:33 AM, Kazuho Oku <[email-masked]<mailto:[email-masked]>> wrote:
I prefer having split packet number spaces, because in addition to
what Martin says, I feel uneasy about allowing a receiver to
acknowledge a packet "in a greater than or equal encryption level."

This sums up my feelings as well - I really like the explicitness of the separate spaces.

---

From: Eric Rescorla <[email-masked]>
Date: Thu, 26 Jul 2018 08:44:07 -0700

On Thu, Jul 26, 2018 at 7:04 AM, Nick Banks <
nibanks=[email-masked]> wrote:

> First, I think we should limit the discussion to what actually is in V1.
> Things like post quantum crypto and possible future TLS changes are
> interesting to reason about, but should have no immediate bearing on the
> design right now. If things change in the future that might cause
> additional issues, we should handle them in a future version.
>
>
>
> Second, on the topic of only acknowledging packets at a greater than or
> equal encryption level being even harder or less efficient to implement,
> while I whole-heartedly disagree, I was thinking about this, and feel we
> could actually go one step further. Already I have proposed disallowing
> ACKs in Initial packets and allowing 0-RTT packets to be acknowledged in
> Handshake packets. We could instead just say no ACKs in Initial packets,
> but all other packets can acknowledge any other packet.
>

This seems like a lot of special casing.

No encryption level requirements at all. The obvious possible point of
> contention with this, is that it would allow Handshake packets to
> acknowledge 1-RTT packets. While it is a ‘lower’ encryption level (I don’t
> really know what that means) both Handshake and 1-RTT keys are keys only
> the endpoints know. I don’t see any harm in temporarily (as long as you
> accept Handshake packets) allowing Handshake packets to acknowledge 1-RTT
> packets. With this design, an implementation that needs to acknowledge
> something can then do whatever it likes, so long as it doesn’t use an
> Initial packets.
>

This does not match the analytic framework established for TLS 1.3, which
explicitly includes key separation between handshake and traffic keys. This
was very important when we did the protocol analysis, so I would not be in
favor of this change.

-Ekr

> Next, for not explicitly sending ACK frames in Initial packets, I
> personally don’t see the explicit event of TLS changing read encryption
> keys from initial to handshake as an implicit signal. To me, it seems very
> reasonable to call that out as the explicit signal to treat your initial
> packet(s?) as acknowledged.
>

>
> - Nick
>
>
>
> *From:* Patrick McManus <[email-masked]>
> *Sent:* Thursday, July 26, 2018 5:15 AM
> *To:* Kazuho Oku <[email-masked]>
> *Cc:* Martin Thomson <[email-masked]>; Nick Banks <
> [email-masked]>; QUIC WG <[email-masked]>
> *Subject:* Re: Go Back to Single Packet Number Space
>
>
>
>
>
>
>

---

From: Tommy Pauly <[email-masked]>
Date: Thu, 26 Jul 2018 09:09:24 -0700

First off, I'd like to +1 to the points Kazuho made, as I think he did a very good job of expressing the concern I have.

To elaborate on the point about separation of spaces making things easier to reason about:

While the table below does indicate that there are 4 different encryption levels/sets of keys, there can and should be a connection between the 0-RTT and 1-RTT spaces. 

| Packet Type     | Encryption Level | PN Space  |
|:----------------|:-----------------|:----------|
| Initial         | Initial secrets  | Initial   |
| 0-RTT Protected | 0-RTT            | 0/1-RTT   |
| Handshake       | Handshake        | Handshake |
| Retry           | N/A              | N/A       |
| Short Header    | 1-RTT            | 0/1-RTT   |

Effectively, there are three different levels of trust at play, which determine the type of frame content that may be sent:
- For Initial packets, there is no established trust at all
- For Handshake packets, there is only the established trust that the peers are the same ones that performed the Initial exchange; at this point it is safe to perform authentication
- For both 0-RTT and 1-RTT packets, there is the trust that the peers have completed an authenticated handshake; only here is it safe to send application data

These three levels of trust are not specific to TLS, but a common feature of security handshakes.

Separated packet number spaces allows an implementation to very discretely separate its handling of frames and retransmissions between the three levels of trust. The architecture that this promotes is one that (I hope) is less likely to have bugs in which frames that must only be sent in higher levels of trust are sent in lower levels.

Thanks,
Tommy

> On Jul 25, 2018, at 9:37 PM, Nick Banks <nibanks=[email-masked]> wrote:
> 
> Since there are four encryption levels, the fact that there are only three packet spaces only makes things more confusing IMO.. If your argument is that matching them together makes things easier, then I’d think there should be four packet spaces. I think having all this duplication and separation just adds unnecessary complexity.
>  
> From: [email-masked] <mailto:[email-masked]> <[email-masked] <mailto:[email-masked]>> on behalf of Tommy Pauly <[email-masked] <mailto:[email-masked]>>
> > On Jul 25, 2018, at 8:01 PM, Dmitri Tikhonov <[email-masked] <mailto:[email-masked]>> wrote:
> > 
> > 1. https://na01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fquicwg%2Fbase-drafts%2Fissues%2F1579%23issuecomment-405720217&amp;data=02%7C01%7Cnibanks%40microsoft.com%7C86b0eb2ea03c48a3fc7808d5f2b00684%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C1%7C636681760204180396&amp;sdata=fstGdvwnKKfApVKVQZFuJYdWAZkXCafUsEH0t1YtH8U%3D&amp;reserved=0 <https://na01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fquicwg%2Fbase-drafts%2Fissues%2F1579%23issuecomment-405720217&amp;data=02%7C01%7Cnibanks%40microsoft.com%7C86b0eb2ea03c48a3fc7808d5f2b00684%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C1%7C636681760204180396&amp;sdata=fstGdvwnKKfApVKVQZFuJYdWAZkXCafUsEH0t1YtH8U%3D&amp;reserved=0>
> > 
>