Subject: [quicwg/base-drafts] Ordering of crypto stream packets (#1651)

From: Christian Huitema <[email-masked]>
Date: Sat, 11 Aug 2018 11:09:39 -0700

I am doing interop tests and self tests with the new crypto stream encoding (draft-13 + PR). I think we have an ordering problem. If the 0-RTT packet containing the EOED message is lost, the QUIC server may receive the Client Finished message before receiving the EOED. If it submits that message to TLS, the exchange will fail, because the EOED was not received. The server should keep the Client Finished message in memory and only submit it after EOED is received. But the server does not really know that without having some inside knowledge of the TLS state -- and one of the goal of the new Crypto Stream design was to avoid requiring that knowledge.

Of course, one solution is to explain the problem in details. The server knows that 0-RTT was negotiated, and should refrain from submitting the epoch 2 CS data until the epoch 1 data has been received. Note that this does not work in theory, because there is no FIN mark in the CS frames, so the server does not really know when epoch 1 data is finished, but it will work in practice if the server assumes that epoch 1 data is always sent as a single frame. That's a big wart in the stack. 

Another solution would be to send the EOED in epoch 2, because then the ordering would be natural. 

Another solution would be to make sure that the "offset" in the CS frame is computed from the beginning of the session, instead of from the beginning of the epoch. 

The client can minimize the risk by ensuring that EOED and Finished are always transmitted and retransmitted as coalesced segments. That's easy to do for the initial transmission, but not quite as natural for the retransmission, since different packet contexts will have different timers, sequence numbers, etc.

For the details, consider the following typical session exchanges:

1) Basic connection:
```
CHello (250 bytes) => Send CS frame offset 0, length 250 with Initial packet Epoch 0.
       <-- SHello (160 bytes) 
               => Send CS frame offset 0, length 160 with Initial packet, Epoch 0
       <-- server first flight (1500 bytes)
               => Send CS frame offset 0, length 1000 with Handshake packet, Epoch 2
               => Send CS frame offset 1000, length 500 with Handshake packet, Epoch 2
Client Finished =>  Send CS frame offset 0, length 46 with Handshake packet Epoch 2.
<process everything in order and life is good >
```
2) 0-RTT connection:
```
CHello (250 bytes) => Send CS frame offset 0, length 250 with Initial packet Epoch 0.
       <-- SHello (160 bytes) 
               => Send CS frame offset 0, length 160 with Initial packet, Epoch 0
       <-- server first flight (1500 bytes)
               => Send CS frame offset 0, length 1000 with Handshake packet, Epoch 2
               => Send CS frame offset 1000, length 500 with Handshake packet, Epoch 2
EOED =>Send CS frame offset 0, length 4 with 0-RTT packet Epoch 1.
Client Finished =>  Send CS frame offset 0, length 46 with Handshake packet Epoch 2.
<process everything in order and life is good >
```
2) 0-RTT connection with inconvenient packet loss :
```
CHello (250 bytes) => Send CS frame offset 0, length 250 with Initial packet Epoch 0.
       <-- SHello (160 bytes) 
               => Send CS frame offset 0, length 160 with Initial packet, Epoch 0
       <-- server first flight (1500 bytes)
               => Send CS frame offset 0, length 1000 with Handshake packet, Epoch 2
               => Send CS frame offset 1000, length 500 with Handshake packet, Epoch 2
Packet loss: EOED =>Send CS frame offset 0, length 4 with 0-RTT packet Epoch 1.
Client Finished =>  Send CS frame offset 0, length 46 with Handshake packet Epoch 2.
Retransmit: EOED =>Send CS frame offset 0, length 4 with 0-RTT packet Epoch 1.
<process everything in order and the exchange fails >
```

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

---

From: Kazuho Oku <[email-masked]>
Date: Sat, 11 Aug 2018 18:01:31 -0700

Could this be considered as an error of the TLS stack supplying the epoch 2 read key too early? I mean that we might argue that the TLS stack should provide the key after processing EOED.

-- 
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/1651#issuecomment-412311289

---

From: Christian Huitema <[email-masked]>
Date: Sat, 11 Aug 2018 20:12:20 -0700

Yes, I suppose that would help. Maybe worth writing in an appendix to the Quic/TLS draft.

-- 
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/1651#issuecomment-412315489

---

From: ekr <[email-masked]>
Date: Sun, 12 Aug 2018 06:03:41 -0700

On Sat, Aug 11, 2018 at 8:12 PM, Christian Huitema <[email-masked]
> wrote:

> Yes, I suppose that would help. Maybe worth writing in an appendix to the
This isn't the only time this can happen. Imagine that the server sends
SFIN, NST and you get reordering.

The general fix to this is for the implementation to maintain a single read
level for the TLS stack at a given time. The spec tries to tell you to do
this in S 4.1.1. https://tools.ietf.org/html/draft-ietf-quic-tls-13#
section-4.1.1

   At any given time, the TLS stack at an endpoint will have a current
   sending encryption level and receiving encryption level.  Each
   encryption level is associated with a different flow of bytes, which
   is reliably transmitted to the peer in CRYPTO frames.  When TLS
   provides handshake octets to be sent, they are appended to the
   current flow and any packet that includes the CRYPTO frame is
   protected using keys from the corresponding encryption level.

   When an endpoint receives a QUIC packet containing a CRYPTO frame
   from the network, it proceeds as follows:

   o  If the packet was in the TLS receiving encryption level, sequence
      the data into the input flow as usual.  As with STREAM frames, the
      offset is used to find the proper location in the data sequence.
      If the result of this process is that new data is available, then
      it is delivered to TLS in order.

   o  If the packet is from a previously installed encryption level, it
      MUST not contain data which extends past the end of previously
      received data in that flow.  Implementations MUST treat any
      violations of this requirement as a connection error of type
      PROTOCOL_VIOLATION.

   o  If the packet is from a new encryption level, it is saved for
      later processing by TLS.  Once TLS moves to receiving from this
      encryption level, saved data can be provided.  When providing data
      from any new encryption level to TLS, if there is data from a
      previous encryption level that TLS has not consumed, this MUST be
      treated as a connection error of type PROTOCOL_VIOLATION.

Note that this is not a matter of what keys you have, but rather of what
you are prepared to pass to the TLS stack.

Maybe this text isn't clear enough, though?

-Ekr

-- 
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/1651#issuecomment-412341564

---

From: Christian Huitema <[email-masked]>
Date: Sun, 12 Aug 2018 11:02:59 -0700

I think the text mixes two issues, receiving packets and delivering to the TLS stack. In my implementations attempts, I made two mistakes:

1) I initially thought that the offset in the CS frames was computed just like the stream0 offset, i.e. continuous from initial to finished. 

2) Once I realized that there was independent offsets starting at zero in each epoch, I made the mistake of delivering packets to the stack as soon as they were received.

I think there are a series of concepts that need to be specified in the spec:

* Separation of the exchanges in a series of epochs, each with each own encryption keys. The spec does explain that well.

* How to map messages to the CS frames, computing the offset within an epoch. This is currently left unsaid.

* How to ensure that TLS packets are delivered in the right order to the TLS stack. I find the current text a bit terse, and indeed I got it wrong initially.

I see on the chat a proposal to enforce delivery sequence by TLS refraining from providing an epoch's encryption key before the TLS stack is ready to absorb input for that epoch. This event would also indicate to the QUIC stack that the previous epoch is finished, that no more data is expected there, and that arrival of any new such data should be treated as a protocol violation.

We may debate whether overloading the provision of decryption keys is the right mechanism. Passing the keys as soon as they are available allow the stack to receive and acknowledge packets immediately, which is more efficient as long as the data is delivered to TLS in the right order. But clearly we need a mechanism by which the TLS stack signals when an epoch should be considered closed. And I think that the spec should at least present 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/1651#issuecomment-412360629

---

From: Christian Huitema <[email-masked]>
Date: Sun, 12 Aug 2018 11:26:01 -0700

There is an issue with not providing the epoch 2 (handshake) decryption key before the epoch 1 data has been received. Suppose that the server flight is very long. It will need to be carried over several packets, and the client will need to send acknowledgements and maybe challenge responses. The server's Quic stack will need to process these acknowledgements. It can only do so if it has access to the epoch 2 decryption key. Yet the client will normally only send the EOED after the server flight has been received.

I think that overloading decryption key provision to mean "end of previous epochs" does not work well.

-- 
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/1651#issuecomment-412362219

---

From: Kazuho Oku <[email-masked]>
Date: Sun, 12 Aug 2018 16:00:47 -0700

Now, I agree with @huitema. Let me retract my previous comment. A client is expected to:
* acknowledge server's epoch 2 packets (that could span across multiple RTs if the certificate is huge)
* send EOED in epoch 1 after receiving server's entire epoch 2 packets

The fact in turn means that the server needs to activate the epoch 2 read key before receiving EOED.

-- 
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/1651#issuecomment-412377804

---

From: Martin Thomson <[email-masked]>
Date: Sun, 12 Aug 2018 18:32:11 -0700

> the server needs to activate the epoch 2 read key before receiving EOED

In this problem case, the server accepts 0-RTT, sends its handshake messages (at epoch 2), but finds that it has to send more than 3 datagrams because it has a huge certificate.  At this point, it is reading from epoch 1 and the TLS stack will continue to do so until it gets EOED.  The client won't send that because it hasn't got the entirety of the server handshake yet.  The handshake deadlocks.

The fix is to make epoch 2 keys available to QUIC, but to retain the same constraints on what epoch is used for data passed to TLS.  But now the TLS handshake doesn't have a clear transition point, because key availability doesn't also mean that those keys are ready to be used.

This makes me want to reconsider my patches for NSS, where I let ekr convince me that the two transitions could be coupled.  The fix there is simple enough (I can refuse to accept epoch 2 data until epoch 1 is done), but it will be more annoying to 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/1651#issuecomment-412387442

---

From: Kazuho Oku <[email-masked]>
Date: Sun, 12 Aug 2018 19:32:39 -0700

@martinthomson 
> This makes me want to reconsider my patches for NSS, where I let ekr convince me that the two transitions could be coupled. The fix there is simple enough (I can refuse to accept epoch 2 data until…

The situation is the same for picotls.

I think we have three options:

a) expose current read epoch from the TLS stack, and let the QUIC stack buffer handshake messages that have a higher epoch

I think that is the suggested approach in the TLS draft, as @ekr has pointed out. The draft states that "if the packet is from a new encryption level, it is saved for later processing by TLS. Once TLS moves to receiving from this encryption level, saved data can be provided".

The approach is simple on the TLS stack side, but might be complex from QUIC stack's viewpoint.

b) let the TLS stack buffer handshake messages until it receives EOED

The approach is simple from QUIC stack's viewpoint, but requires a new buffering layer.

c) in the TLS stack, manage the receipt of EOED using a separate flag

The TLS stack will substitute EOED and process handshake messages as they arrive, but delay the changes of the states being delivered to the QUIC stack until it actually receives EOED. The approach is simple from QUIC stack's viewpoint and also does not require additional buffering; however, the logic in the TLS stack will be complex.

-- 
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/1651#issuecomment-412393837

---

From: Martin Thomson <[email-masked]>
Date: Sun, 12 Aug 2018 19:55:25 -0700

For NSS, the best plan seems to be to let the QUIC stack feed any data it has into the TLS stack, starting from the data that is oldest.  Separate calls for data from different epochs will allow TLS to reject data for that epoch, which QUIC can then hold onto.  Any time QUIC has data for any epoch, it starts at the earliest for which it has unconsumed data and feeds that into TLS.

The only trick is that you have three return codes:
1. I got that, thanks.
2. Sorry, I'm not ready for that yet.
3. Explode!

-- 
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/1651#issuecomment-412396245

---

From: Kazuho Oku <[email-masked]>
Date: Sun, 12 Aug 2018 20:06:52 -0700

Maybe I am thinking too much, but IMO the restriction with that approach is that it works well only when the QUIC stack provides a "peek" API to access CRYPTO data in the receive buffer. Without a "peek" API, the QUIC stack will be required to introduce a new buffer that stores data rejected as not ready by the TLS stack.

-- 
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/1651#issuecomment-412397396

---

From: ekr <[email-masked]>
Date: Sun, 12 Aug 2018 20:07:18 -0700

I don't think this needs to be specified in the specification. 

As far as implementations go, Minq already buffers the data, so  option (a) is very straightforward. I just need to send out the key as soon as it's ready rather than when it's installed, and have a separate install call. I'm not sure I agree with Martin's assessment of what's best for NSS, but as above, I don't think this is an issue for the spec.

-- 
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/1651#issuecomment-412397443

---

From: Kazuho Oku <[email-masked]>
Date: Sun, 12 Aug 2018 20:12:51 -0700

What @ekr says. There is no need to update the draft. Though I think it is beneficial to have a discussion about the API that TLS stacks will provide (because having one style of API design will lead to less confusion).

-- 
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/1651#issuecomment-412398086

---

From: Subodh Iyengar <[email-masked]>
Date: Sun, 12 Aug 2018 21:34:57 -0700

@martinthomson why would the handshake deadlock? Wouldn’t the server receive acks if it’s handshake packets which would let it egress more to complete the handshake

-- 
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/1651#issuecomment-412406193

---

From: Christian Huitema <[email-masked]>
Date: Sun, 12 Aug 2018 21:48:21 -0700

@siyengar If the sender does not have the handshake decrypt key, it cannot get to data, and also cannot get to the PN. No way then to handle ACKs.

-- 
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/1651#issuecomment-412407559

---

From: Christian Huitema <[email-masked]>
Date: Sun, 12 Aug 2018 21:51:09 -0700

Given that several of us started implementations and made some wrong assumptions, one could think that the spec could add some clarification. Yes, this is a local implementation issue, and we don't want to standardize the details of the API between QUIC and TLS. But having an appendix about implementation would make sense. And there is already a fair bit of text in this thread.

-- 
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/1651#issuecomment-412407778

---

From: mirjak <[email-masked]>
Date: Tue, 14 Aug 2018 14:53:03 +0000 (UTC)

Quick question: is it actually necessary to also reset the (crypto) stream offset if the packet number space changes? If not, I guess that would solve the problem...?

-- 
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/1651#issuecomment-412900180

---

From: Nick Banks <[email-masked]>
Date: Tue, 14 Aug 2018 14:57:02 +0000 (UTC)

@mirjak that's what I was arguing for in #1592. IMO, that's a better, more explicit design at least at the QUIC layer. Other folks have argued against it, because they feel (I don't agree) it makes it harder to validate things were received in the correct TLS epoch, at the TLS layer. I already have my stack set up this way (a single stream), but I have a small translation layer to add/subtract offsets whenever I send/receive packets. It works really well for me and it a compact, simple layer at the QUIC layer. The QUIC to TLS interactions aren't really any more complicated IMO.

-- 
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/1651#issuecomment-412901548

---

From: mirjak <[email-masked]>
Date: Tue, 14 Aug 2018 08:02:07 -0700

Thanks! I'm currently reviewing the transport draft and I just found it logically weird that the crypto stream is reset but the data streams are not, or is that an oversight? 

-- 
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/1651#issuecomment-412903450

---

From: Nick Banks <[email-masked]>
Date: Tue, 14 Aug 2018 15:02:36 +0000 (UTC)

It's by design currently.

-- 
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/1651#issuecomment-412903648

---

From: Mike Bishop <[email-masked]>
Date: Tue, 14 Aug 2018 17:08:38 +0000 (UTC)

I was going to say that data streams aren’t reset because they exist only in one packet number space.  However, 0-RTT and 1-RTT are separate encryption contexts in the same packet number space, so CRYPTO offsets are reset between the two, aren’t they?  That *is* a bit unintuitive.

From: mirjak <[email-masked]>
Sent: Tuesday, August 14, 2018 8:02 AM
To: quicwg/base-drafts <[email-masked]>
Cc: Subscribed <[email-masked]>
Subject: Re: [quicwg/base-drafts] Ordering of crypto stream packets (#1651)

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub<https://github.com/quicwg/base-drafts/issues/1651#issuecomment-412903450>, or mute the thread<https://github.com/notifications/unsubscribe-auth/AEE2hajrZLU40TAE_obZchz-XkOyGhwhks5uQuZugaJpZM4V5Qix>.

-- 
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/1651#issuecomment-412945919

---

From: ianswett <[email-masked]>
Date: Tue, 14 Aug 2018 10:39:55 -0700

Mike, I agree that's unintuitive.

My understanding is that they're separate because the one thing sent in a CRYPTO frame in 0RTT is end of early data and that has to be sent in 0RTT for reasons I can't remember, but I believe are related to crypo theory/proofs.

This is unlike everything else in 0RTT which can be retransmitted with 1RTT keys, which is very odd from a transport perspective.  It'd be nice to fix, but I was told it was infeasible last time I asked.

-- 
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/1651#issuecomment-412955570

---

From: Christian Huitema <[email-masked]>
Date: Tue, 14 Aug 2018 12:26:43 -0700

Yes it is counter-intuitive. If a 0-RTT packet appears lost, any CRYPTO frame inside it would have to be resent in a new 0-RTT packet, but the STREAM frames should be resent in a DATA packet. And then, the 0-RTT packets can only be acknowledged by 1-RTT packet, which means that they should not be considered lost before the handshake completes and the server has a chance to send an ACK. But on the other hand the exchange cannot complete if the EOED message is lost, so those 0-RTT packets that contains crypto shall be considered lost if they are not acknowledged after a time-out. This whole thing is a ugly big wart. See issue #1518.

-- 
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/1651#issuecomment-412987586

---

From: Martin Thomson <[email-masked]>
Date: Tue, 14 Aug 2018 15:22:51 -0700

Closed #1651 via #1654.

-- 
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/1651#event-1788953130