Connection ID lengths 1, 2 and 3 bytes can't be encoded

[marten-seemann]

The connection IDs can be either 0 bytes or anything between 4 and 18 bytes (inclusive). Lengths of 1, 2 and 3 bytes are not possible.

There are several use cases that would benefit from using shorter connection IDs, especially in p2p applications. An endpoint could encode the length of the connection ID into the first few bits, and then starts using 1 byte connection IDs first, and successively moves to longer lengths only when handling more connections. For p2p hosts, in many cases 2 bytes would be sufficient for all use cases.

In the connection ID length field in the Long Header, we only have 4 bits to encode a range of 19 values (we want 0 byte connection IDs, and we want to support 18 byte connection IDs), so some values have to be left out. It seems there are few use cases for 13, 14 and 15 bytes.

We could achieve this by changing the definition of the length to:

An encoded length between 0 and 12 inclusive indicates that the connection ID is also 0 to 12 octets in length. Any larger value is increased by 3 to get the full length of the connection ID, producing a length between 16 and 18 octets inclusive.

If people are supportive of this change, I'd be happy to write a PR.

[janaiyengar]

We should fix this, especially since the CIDs will become ossified quickly. Skipping 13-15 is odd, but that's going to be true of anything we skip. I'm supportive.

[mikkelfj]

There are also use cases in radio based sensor networks and also wired lightweight protocols that use QUIC without IP/UDP framing. For example an I2C bus or similar microcontroller network might use QUIC for security and routing but really care about keeping individual message frames short. Such use cases might, BTW also opt to truncate the trailing authentication tag.

[ekr]

I don't have any objection to shorter lengths, but my memory of the discussion in Melbourne was that some people opposed short IDs because the natural way to allocation them was with some kind of counter (though I suppose you could build a shuffle table) and that therefore this would create privacy leaks

…

-Ekr

On Sun, Jul 15, 2018 at 11:36 AM, Marten Seemann ***@***.***> wrote: The connection IDs can be either 0 bytes or anything between 4 and 18 bytes (inclusive). Lengths of 1, 2 and 3 bytes are not possible. There are several use cases that would benefit from using shorter connection IDs, especially in p2p applications. An endpoint could encode the length of the connection ID into the first few bits, and then starts using 1 byte connection IDs first, and successively moves to longer lengths only when handling more connections. For p2p hosts, in many cases 2 bytes would be sufficient for all use cases. In the connection ID length field in the Long Header, we only have 4 bits to encode a range of 19 values (we want 0 byte connection IDs, and we want to support 18 byte connection IDs), so *some* values have to be left out. It seems there are few use cases for 13, 14 and 15 bytes. We could achieve this by changing the definition of the length to: An encoded length between 0 and 12 inclusive indicates that the connection ID is also 0 to 12 octets in length. Any larger value is increased by 3 to get the full length of the connection ID, producing a length between 16 and 18 octets inclusive. If people are supportive of this change, I'd be happy to write a PR. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#1570>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ABD1oUzh1HvIDS_VexwowDaDshxQQGlMks5uG4u1gaJpZM4VQV65> .

[martinthomson]

ekr's comment here is right. You can't use new connection IDs in the same way when the space is too small (arguably 4 is too small, but several people wanted 4).

[mikkelfj]

You can't use them the same way for sure, but they are useful in a different way. Unlinkability is not always a concern, or it may happen where linkability would happen anyway, such as a IP tuple but where the port number is not the best option to differentiate connections, e.g. due to avoid OS interference.

[janaiyengar]

@ekr @martinthomson : I think it's useful to have this degree of freedom for uses, for instance, where there's no migration, but only demultiplexing among a few connections. I understand the concern that having connection ID that's too small can lead to linkability, but I think there's a natural pushback here -- servers that use connection ID for demuxing will want to use a large CID because small ones are not enough, or they'll use no CID. The only place a small one becomes interesting is when (i) there are only a few connections being demuxed and (ii) where the bit cost matters. This is true in the p2p case, where I would argue that linkability is quite easy with just timing of packets.

[ekr]

@janaiyengar: I'm not sure I disagree, but I feel uncomfortable going against what I thought was consensus. Regrettably, I think a topic for NYC.

…

On Tue, Aug 7, 2018 at 12:40 PM, janaiyengar ***@***.***> wrote: @ekr <https://github.com/ekr> @martinthomson <https://github.com/martinthomson> : I think it's useful to have this degree of freedom for uses, for instance, where there's no migration, but only demultiplexing among a few connections. I understand the concern that having connection ID that's too small can lead to linkability, but I think there's a natural pushback here -- servers that use connection ID for demuxing will want to use a large CID because small ones are not enough, or they'll use no CID. The only place a small one becomes interesting is when (i) there are only a few connections being demuxed and (ii) where the bit cost matters. This is true in the p2p case, where I would argue that linkability is quite easy with just timing of packets. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#1570 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ABD1oaQcNqm140O3BhvaRU19r3qq1c5hks5uOe0pgaJpZM4VQV65> .

[ianswett]

Personally, I'm happy with this.

[kazuho]

In addition to linkability, the other issue with the proposal is that you could easily run out of CIDs when stateless reset is being used. Quoting from the editors' draft:

Revealing the Stateless Reset Token allows any entity to terminate the connection, so a value can only be used once. This method for choosing the Stateless Reset Token means that the combination of connection ID and static key cannot occur for another connection.
https://quicwg.org/base-drafts/draft-ietf-quic-transport.html#rfc.section.6.13.4

Considering the two issues, I prefer not allowing shorter CID lengths in QUICv2 (formerly called v1). P2P can be a post-v2 thing.

[mikkelfj]

I'd rather fix the text about being used once. It is not practical to track all ID's anyway - it can only be a stastical property.

[martinthomson]

Once you get beyond 80 or so bits, collisions aren't really a practical concern, but more a theoretical one.

[kazuho]

In addition to what @martinthomson has pointed out, I would like to note that it is possible to implement a deterministic approach for shorter CIDs (e.g. 4 octets).

One way is to let the endpoint track the CIDs for which it has generated a stateless reset, and rotate the reset key when the size of the tracked CIDs exceeds certain threshold, at the same time enforcing the active clients to switch to new CIDs (so that they can be reset using a stateless reset generated by the new key). You can use a probablistic structure (e.g. bloom filter) to track the CIDs for which stateless resets has been generated.

However, my understanding is that such approach does not work well for very short CIDs (e.g. 1 octet), because when under attack, the number space will be consumed by the attacker faster than clients migrate to new CIDs.

[mikkelfj]

You can state that CID must not be ambigious across active connections with high propability.

As to resets, perhaps they do not make sense for short CID's.

[kazuho]

As to resets, perhaps they do not make sense for short CID's.

I would rephrase that to a question: do we need to give (some small number of) implementations a chance to save 3 octets, even though some features will not work if they choose to save the bytes?

I do not think it is something worth doing.

Note that in the future we could introduce very short CIDs for short packets in future versions of QUIC, even though we decide to not have them in QUIC v1 nor in the long header defined in the invariants.

[MikeBishop]

@kazuho, also recall that the design we're discussing in the design team doesn't permit an endpoint to force a CID change on the peer.