Subject: Need your help: different connection IDs in the same datagram

From: "Martin Thomson" <[email-masked]>
Date: Wed, 15 Jul 2020 17:23:57 +1000

https://github.com/quicwg/base-drafts/issues/3800 discovered a minor "discrepancy" in our requirements for coalescing packets.  We required that:

* senders not coalesce packets for different connections in the same datagram.

* receivers reject packets with different connection **IDs** in the same datagram.

https://github.com/quicwg/base-drafts/pull/3870/files was the result of a discussion where I was convinced that looser constraints here weren't harmful.  The requirements would identify connections, not connection IDs.

Originally, my inclination was to fix the requirement on the sender to use connection IDs, which would remove some linkability.  But then I was reminded that linkability is already defeated for several reasons.  You can't coalesce outside of the handshake and we require a stable path for the handshake AND long headers include a source connection ID that can be used for linkability.  So the linkability concern is basically lost.

We also learned that some implementations were generating packets while processing incoming packets.  Later they would coalesce these into a datagram that might then have different connection IDs on the packets it contains.

There has been some opposition to the proposed resolution in PR 3870.  

Apparently, for some, having multiple connection IDs in the same datagram complicates processing.  I don't understand this objection.  It seems to me more difficult to retain state across packets than it is to process each atomically.  I was hoping that Christian or Nick can explain more about how this affects them.

Marten also indicated that there was a reason not to allow this, but if I understand that, this is based on some potential for future optimization, which could be conditional on having consistent connection IDs.  If we moved to a scheme that required consistent connection IDs, anyone using that scheme could be required to avoid coalescing different connection IDs.  So this seems more of a theoretical concern.

And - in anticipation of maybe choosing to make senders use a consistent connection ID - if you might be generating coalesced datagrams with different connection IDs in packets, how hard would it be to ensure that these are consistent?  Lars and Ian, I think both of you indicated that you might do this.

---

From: Marten Seemann <[email-masked]>
Date: Wed, 15 Jul 2020 18:54:02 +0700

Let's have a look where this situation can occur:

During the early stages of the handshake it is not possible: The client
changes its connection ID used for Initial and 0-RTT packets as soon as it
receives a new connection ID provided by the server in a Retry or Initial
packet. The earliest time where a client could possibly coalesce packets
with different connection IDs is after receiving the Server Preferred
Address, and decides (for whatever reason) to not migrate to that address,
but to use that connection ID on the original path (and before the
handshake is confirmed).

The server needs to receive a NEW_CONNECTION_ID frame before it can change
connection IDs. The earliest this can happen is in a 0-RTT packet, so in
principle a server could start using that connection ID in its first flight.

I can see little reason to 1. start using a new connection ID during the
handshake and at the same time 2. to not completely switch to that
connection ID, but instead to continue using both at the same time.
To be clear, it isn't prohibited to use multiple connection IDs at the same
time (and on the same path), it's just that there's no good reason to do
so. I don't think it's too much of a burden to ask implementations that
still decide to do so to make sure that the connection IDs used in a
coalesced packet match, considering that for the receiver it's more
cumbersome to check that all connection IDs are actually valid for this
connection than to just validate that all packets use the same connection
ID.

On Wed, Jul 15, 2020 at 2:24 PM Martin Thomson <[email-masked]> wrote:

> https://github.com/quicwg/base-drafts/issues/3800 discovered a minor
> "discrepancy" in our requirements for coalescing packets.  We required that:
>
> https://github.com/quicwg/base-drafts/pull/3870/files was the result of a
> discussion where I was convinced that looser constraints here weren't
> harmful.  The requirements would identify connections, not connection IDs.
>
> Originally, my inclination was to fix the requirement on the sender to use
> connection IDs, which would remove some linkability.  But then I was
> reminded that linkability is already defeated for several reasons.  You
> can't coalesce outside of the handshake and we require a stable path for
> the handshake AND long headers include a source connection ID that can be
> used for linkability.  So the linkability concern is basically lost.
>
> We also learned that some implementations were generating packets while
> processing incoming packets.  Later they would coalesce these into a
> datagram that might then have different connection IDs on the packets it
> contains.
>
> Apparently, for some, having multiple connection IDs in the same datagram
> complicates processing.  I don't understand this objection.  It seems to me
> more difficult to retain state across packets than it is to process each
> atomically.  I was hoping that Christian or Nick can explain more about how
> this affects them.
>
> Marten also indicated that there was a reason not to allow this, but if I
> understand that, this is based on some potential for future optimization,
> which could be conditional on having consistent connection IDs.  If we
> moved to a scheme that required consistent connection IDs, anyone using
> that scheme could be required to avoid coalescing different connection
> IDs.  So this seems more of a theoretical concern.
>
> And - in anticipation of maybe choosing to make senders use a consistent
> connection ID - if you might be generating coalesced datagrams with
> different connection IDs in packets, how hard would it be to ensure that
> these are consistent?  Lars and Ian, I think both of you indicated that you
> might do this.
>
>

---

From: Nick Banks <[email-masked]>
Date: Wed, 15 Jul 2020 14:19:38 +0000

Generally, I agree with Marten’s comments that that there is little reason to use multiple connections IDs in the same datagram. Specifically, for our implementation, MsQuic, validating the connection ID in each packet is much simpler if they’re all the same.; our UDP datagram context structure holds a pointer to the first connection ID in the datagram, so all that needs to be done (for each QUIC packet) is compare the current QUIC packet’s connection ID to that pointer. The logic requires no additional connection state. If we allowed any connection ID that’s valid for the connection, then we’d have to go to the connection object and do a lookup each time instead. It’s definitely possible to do, but requires a bit more work (CPU) and synchronization of state. For those reasons, I’d prefer to keep the connection IDs consistent.

Thanks,
- Nick

From: QUIC <[email-masked]> On Behalf Of Marten Seemann
Sent: Wednesday, July 15, 2020 4:54 AM
To: Martin Thomson <[email-masked]>
Cc: QUIC WG <[email-masked]>
Subject: Re: Need your help: different connection IDs in the same datagram

During the early stages of the handshake it is not possible: The client changes its connection ID used for Initial and 0-RTT packets as soon as it receives a new connection ID provided by the server in a Retry or Initial packet. The earliest time where a client could possibly coalesce packets with different connection IDs is after receiving the Server Preferred Address, and decides (for whatever reason) to not migrate to that address, but to use that connection ID on the original path (and before the handshake is confirmed).

The server needs to receive a NEW_CONNECTION_ID frame before it can change connection IDs. The earliest this can happen is in a 0-RTT packet, so in principle a server could start using that connection ID in its first flight.
I can see little reason to 1. start using a new connection ID during the handshake and at the same time 2. to not completely switch to that connection ID, but instead to continue using both at the same time.
To be clear, it isn't prohibited to use multiple connection IDs at the same time (and on the same path), it's just that there's no good reason to do so. I don't think it's too much of a burden to ask implementations that still decide to do so to make sure that the connection IDs used in a coalesced packet match, considering that for the receiver it's more cumbersome to check that all connection IDs are actually valid for this connection than to just validate that all packets use the same connection ID.

On Wed, Jul 15, 2020 at 2:24 PM Martin Thomson <[email-masked]<mailto:[email-masked]>> wrote:
https://github.com/quicwg/base-drafts/issues/3800<https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fquicwg%2Fbase-drafts%2Fissues%2F3800&data=02%7C01%7Cnibanks%40microsoft.com%7C75dfe6046cbe489852d908d828b5d4be%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637304108718116239&sdata=ixeFxeDjp0kzD87SZz3APaSAnHoAbP5K%2Bl53TSEDfe8%3D&reserved=0> discovered a minor "discrepancy" in our requirements for coalescing packets.  We required that:

https://github.com/quicwg/base-drafts/pull/3870/files<https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fquicwg%2Fbase-drafts%2Fpull%2F3870%2Ffiles&data=02%7C01%7Cnibanks%40microsoft.com%7C75dfe6046cbe489852d908d828b5d4be%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637304108718126227&sdata=zb1PUsYnpLqkEIyD%2B3cmxSKtjvivb05or70XnqMFUyc%3D&reserved=0> was the result of a discussion where I was convinced that looser constraints here weren't harmful.  The requirements would identify connections, not connection IDs.

---

From: Dmitri Tikhonov <[email-masked]>
Date: Wed, 15 Jul 2020 14:02:32 -0400

On Wed, Jul 15, 2020 at 05:23:57PM +1000, Martin Thomson wrote:
> Apparently, for some, having multiple connection IDs in the same
> datagram complicates processing.  I don't understand this objection.
> It seems to me more difficult to retain state across packets than it
> is to process each atomically.  I was hoping that Christian or Nick
> can explain more about how this affects them.

I can provide an example from lsquic.  The datagram is parsed into
QUIC packets in one function, lsquic_engine_packet_in():

  https://github.com/litespeedtech/lsquic/blob/v2.18.1/src/liblsquic/lsquic_engine.c#L2781L2816

Each QUIC packet is processed by process_packet_in(), where a
connection is looked up:

  https://github.com/litespeedtech/lsquic/blob/v2.18.1/src/liblsquic/lsquic_engine.c#L1352L1360

The DCID check is performed lsquic_engine_packet_in(), before
process_packet_in() is called:

  https://github.com/litespeedtech/lsquic/blob/v2.18.1/src/liblsquic/lsquic_engine.c#L2793L2806

The DCID information is readily available in the datagram parsing
loop, while connection information is not.

For lsquic to support the proposed change, it would have to remember
the current connection and then query it whether it is indeed the
owner of the next DCID (A) or look up DCID in the global hash (B):

    conn = NULL;
    while (quic_packet = parse_udp(pointers)) {
        dcid = parse(quic_packet);
        if (conn)
        {
  #if VARIANT_A
            if (!conn_owns_scid(conn, dcid))
  #else
            if (conn != lookup_by_dcid(dcid))
  #endif
                continue;
        }
        conn = process_packet(quic_packet);
    }

Not that it could not be done, of course, but it is both extra work
to modify lsquic and a more inefficient mechanism: what was a simple
CID comparison is now a hash lookup.

That's why I argued [1] for having solid rationale behind the change
rather than a personal preference.

  - Dmitri.

1. https://github.com/quicwg/base-drafts/issues/3800#issuecomment-656851626

---

From: Ian Swett <[email-masked]>
Date: Wed, 15 Jul 2020 15:30:56 -0400

I don't think this change would be difficult for our implementation, but I
also don't see it as necessary.  Given where we are in the process, that
alone argues for not changing it I believe.

On Wed, Jul 15, 2020 at 2:02 PM Dmitri Tikhonov <[email-masked]>
wrote:

> 1.
> https://github.com/quicwg/base-drafts/issues/3800#issuecomment-656851626
>
>

---

From: David Schinazi <[email-masked]>
Date: Wed, 15 Jul 2020 13:30:46 -0700

As I understand this, the current draft contradicts itself: it allows
senders to coalesce packets with different CIDs, and recommends that
receivers drop them.
I'll second Ian's comment that for us either option will be easy to
implement, but I believe we should fix the contradiction in the draft
before publication.

David

On Wed, Jul 15, 2020 at 12:31 PM Ian Swett <ianswett=
[email-masked]> wrote:

> On Wed, Jul 15, 2020 at 2:02 PM Dmitri Tikhonov <
> [email-masked]> wrote:
>

---

From: Mike Bishop <[email-masked]>
Date: Wed, 15 Jul 2020 20:42:47 +0000

Fundamentally, I think there has to be a change, because we currently have an inconsistent mandate – mixed-CID packets are acceptable to send, but SHOULD be dropped on receipt.

First, there’s the privacy argument, in that the CIDs in the same datagram will become linked to external observers.  I think Marten has already argued convincingly why this will be rare during a typical handshake; Christian and Kazuho have argued that a privacy-sensitive implementation will need to do a CID jump once the handshake is confirmed, at which point you’re mostly not coalescing packets anyway.  So this is a mild argument for not mixing, but I don’t think it’s dispositive.

Second, the implementation arguments appear to boil down to two camps:

  *   Implementation X generates packets independently, then packages them into datagrams.  Since all packets waiting for packaging are from the same connection, there’s currently nothing to check to see whether they’re allowed in the same datagram.  Requiring the CIDs to match would require a new check and a code path for not coalescing packets in certain cases.
  *   Implementation Y consumes packets within a datagram independently, so the validation has to be done at the datagram level before doing any packet-level activities.  A requirement that can be evaluated solely on the contents of the datagram, independent of any connection state, is more efficient.

Of these two, I currently find the latter slightly more persuasive.  The first is a check that can be done between packets without needing to access any connection state, and there are already presumably code paths for handling when a waiting packet can’t go in the datagram currently being constructed (e.g. it’s too large to fit the remaining MTU).  However, I’m sure someone with such an implementation could tell me why it’s more complicated than that.  😊

Neither of the resolutions seems more technically correct than the other; we just need to pick one.

From: QUIC <[email-masked]> On Behalf Of Ian Swett
Sent: Wednesday, July 15, 2020 3:31 PM
To: Martin Thomson <[email-masked]>; IETF QUIC WG <[email-masked]>
Subject: Re: Need your help: different connection IDs in the same datagram

I don't think this change would be difficult for our implementation, but I also don't see it as necessary.  Given where we are in the process, that alone argues for not changing it I believe.

On Wed, Jul 15, 2020 at 2:02 PM Dmitri Tikhonov <[email-masked]<mailto:[email-masked]>> wrote:

    conn = NULL;

  - Dmitri.

---

From: Ian Swett <[email-masked]>
Date: Wed, 15 Jul 2020 17:17:18 -0400

I forgot there's a contradiction, because I thought we disallowed sending
mixed-CID packets.  So I'd prefer changing to MUST NOT coalesce packets
with different CIDs.  Even if you generate them and then coalesce
them(which we do), that's not that hard to enforce in the coalescing code.

On Wed, Jul 15, 2020 at 4:42 PM Mike Bishop <[email-masked]> wrote:

> Fundamentally, I think there has to be a change, because we currently have
> an inconsistent mandate – mixed-CID packets are acceptable to send, but
> SHOULD be dropped on receipt.
>
>
>
> First, there’s the privacy argument, in that the CIDs in the same datagram
> will become linked to external observers.  I think Marten has already
> argued convincingly why this will be rare during a typical handshake;
> Christian and Kazuho have argued that a privacy-sensitive implementation
> will need to do a CID jump once the handshake is confirmed, at which point
> you’re mostly not coalescing packets anyway.  So this is a mild argument
> for not mixing, but I don’t think it’s dispositive.
>
>
>
>    - Implementation X generates packets independently, then packages them
>    into datagrams.  Since all packets waiting for packaging are from the same
>    connection, there’s currently nothing to check to see whether they’re
>    allowed in the same datagram.  Requiring the CIDs to match would require a
>    new check and a code path for *not* coalescing packets in certain
>    cases.
>    - Implementation Y consumes packets within a datagram independently,
>    so the validation has to be done at the datagram level before doing any
>    packet-level activities.  A requirement that can be evaluated solely on the
>    contents of the datagram, independent of any connection state, is more
>    efficient.
>
>
>
> Of these two, I currently find the latter slightly more persuasive.  The
> first is a check that can be done between packets without needing to access
> any connection state, and there are already presumably code paths for
> handling when a waiting packet can’t go in the datagram currently being
> constructed (e.g. it’s too large to fit the remaining MTU).  However, I’m
> sure someone with such an implementation could tell me why it’s more
> complicated than that.  😊
>
>
>
> *From:* QUIC <[email-masked]> *On Behalf Of * Ian Swett
> *Sent:* Wednesday, July 15, 2020 3:31 PM
> *To:* Martin Thomson <[email-masked]>; IETF QUIC WG <[email-masked]>
> *Subject:* Re: Need your help: different connection IDs in the same
> datagram
>
>
>

---

From: "Martin Thomson" <[email-masked]>
Date: Thu, 16 Jul 2020 08:41:27 +1000

>             if (conn != lookup_by_dcid(dcid))
# else
             if (false)
#endif

This would also work, would it not?

---

From: "Martin Thomson" <[email-masked]>
Date: Thu, 16 Jul 2020 08:49:20 +1000

On Thu, Jul 16, 2020, at 07:17, Ian Swett wrote:
> I forgot there's a contradiction, because I thought we disallowed 
> sending mixed-CID packets.  So I'd prefer changing to MUST NOT coalesce 
> packets with different CIDs.  Even if you generate them and then 
> coalesce them(which we do), that's not that hard to enforce in the 
> coalescing code.

OK, this is good information.  I had understood that you were concerned that you might violate a requirement to have consistent connection IDs.

Here's one example of how you might:

Client receives server's first flight, which comprises Initial, Handshake, 1-RTT (which includes NEW_CONNECTION_ID, because this is a good time to send that in a lot of cases).  Assume this all comes at once, in a single datagram.

1. Client processes Initial and Handshake.
2. Client generates a Handshake packet (that includes TLS Finished) and sets that aside.  This uses the connection ID from the servers Initial.
3. Client processes 1-RTT.  Sees NEW_CONNECTION_ID, decides to use it.
4. Client generates first application data, and makes a 1-RTT packet using the new connection ID.
5. Client gathers all generated packets and sends them.

Does anyone care about doing this, or something like it? Because if not, I make a new proposal that changes the requirements to:

* Senders MUST ensure that all coalesced packets include the same value for the Destination Connection ID field.
* Receivers SHOULD discard coalesced packets if they are for a different connection than the first; senders MAY discard coalesced packets that contain a different value in the Destination Connection ID field than the first.

---

From: Dmitri Tikhonov <[email-masked]>
Date: Wed, 15 Jul 2020 19:59:58 -0400

You've lost me a bit, Martin.  Is this the code you aimed for?

    conn = NULL;
  #elif VARIANT_B

---

From: David Schinazi <[email-masked]>
Date: Wed, 15 Jul 2020 17:00:15 -0700

On Wed, Jul 15, 2020 at 3:49 PM Martin Thomson <[email-masked]> wrote:

> OK, this is good information.  I had understood that you were concerned
> that you might violate a requirement to have consistent connection IDs.
>
> Client receives server's first flight, which comprises Initial, Handshake,
> 1-RTT (which includes NEW_CONNECTION_ID, because this is a good time to
> send that in a lot of cases).  Assume this all comes at once, in a single
> datagram.
>
> 2. Client generates a Handshake packet (that includes TLS Finished) and
> sets that aside.  This uses the connection ID from the servers Initial.
> Does anyone care about doing this, or something like it?

I think we should disallow this unless someone can show it provides real
benefit.
If an implementation supports coalescing, it has to handle cases where the
last
packet doesn't fit so it needs to have code to for example send the
handshake
packet by itself if the 1-RTT packet is too big. Once one has such code,
it's pretty
simple to add a check that also triggers this if the connection IDs differ.
If someone
really cares about not losing the benefits of coalescing, then they can
make sure
that they don't act on NEW_CONNECTION_ID until the handshake is confirmed.

> Because if not, I make a new proposal that changes the requirements to:
>
> * Receivers SHOULD discard coalesced packets if they are for a different
> connection than the first; senders MAY discard coalesced packets that
> contain a different value in the Destination Connection ID field than the
> first.
>

I support this proposal.

---

From: Dmitri Tikhonov <[email-masked]>
Date: Wed, 15 Jul 2020 20:11:35 -0400

> connection than the first; senders MAY discard coalesced packets that
                             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> contain a different value in the Destination Connection ID field than
> the first.

I don't understand this.  What do you mean by "*senders* MAY
discard packets?"

  - Dmitri.

---

From: "Martin Thomson" <[email-masked]>
Date: Thu, 16 Jul 2020 10:29:07 +1000

> You've lost me a bit, Martin.  Is this the code you aimed for?
...
>         conn = process_packet(quic_packet);

Yeah, the point being that the check here is added at your discretion.  It is possible to rely on the crypto to ensure that the connection rejects anything that isn't intended for it.

---

From: "Martin Thomson" <[email-masked]>
Date: Thu, 16 Jul 2020 10:31:53 +1000

> > connection than the first; senders MAY discard coalesced packets that

Brain misfire.  That should have been receivers.  Senders are required to make them all the same.

---

From: Dmitri Tikhonov <[email-masked]>
Date: Wed, 15 Jul 2020 20:32:44 -0400

On Thu, Jul 16, 2020 at 10:29:07AM +1000, Martin Thomson wrote:
> ....
> Yeah, the point being that the check here is added at your discretion.
> It is possible to rely on the crypto to ensure that the connection
> rejects anything that isn't intended for it.

I see.  That's true, this is another way to do it.  On the other hand,
this is even less efficient than a hash lookup.

  - Dmitri.

---

From: Jana Iyengar <[email-masked]>
Date: Wed, 15 Jul 2020 22:08:43 -0700

The spirit of the text, as far as I remember, _was_ meant to prevent
multiple connections from being coalesced.

The text for a sender prohibits packets from multiple connections being
coalesced.

A receiver can be one of three things:
1. It can compare state across packets within a datagram. In this case, it
can enforce the policy of not coalescing packets from multiple connections.
2. It cannot compare CIDs across packets within a connection, and it
delivers all packets to the connection with the first CID. In this case, if
multiple coalesced packets belong to multiple connections, then subsequent
packets are undecryptable by the chosen connection, and dropped.
3. It cannot compare CIDs across packets within a connection, but it does a
lookup and delivers each coalesced packet to the correct connection. This
violates the SHOULD that PR 3870 proposes, but that is not a MUST, and one
could use this wiggle room if it's difficult to change the implementation.

In all three cases, I don't see that the new behavior in PR 3870 (SHOULD
drop subsequent coalesced packets belonging to a different connection)
makes it harder for any implementation in question. What am I missing?

All that said, I am fine with prohibiting mixing CIDs if that's where we're
leaning.

---

From: Kazuho Oku <[email-masked]>
Date: Thu, 16 Jul 2020 15:40:39 +0900

> SHOULD be dropped on receipt.

+1 to what Mike says here (as well as others).

We need to fix either the send side or the receive side.

Regarding which side to fix, my preference goes to fixing the receive side
(i.e. change the text to allow coalesced QUIC packets using different
DCIDs).

IIUC, that's the extension of our principle that "datagrams" can be routed,
while packets have to be handled individually.

I do understand that some of us want to reduce the cost of checking the
CIDs when their stacks receive a coalesced QUIC packet. I am not sure if
that is worth having an exception on the aforementioned principle. The
performance gain is going to be much smaller than (un)protecting packets or
processing TLS handshake messages contained in the coalesced packets.

All that said, as an implementer, I am fine with either way of fixing it.

-- 
Kazuho Oku