Subject: A better way to do conn id?

From: Martin Duke <[email-masked]>
Date: Wed, 24 Jan 2018 16:08:33 +1100

Today's variable-length connection ID discussion made me realize some
problems with the current architecture, while the new architecture doesn't
fix some of them and creates whole new ones. Issues:

- The client desires unlinkability, but I suspect the market will provide
no incentives for servers to work very hard to be unlinkable. There were
conflicting "layer 9" arguments that variable conn ID makes this problem
worse or better.

- 16 Bytes is more overhead than 8 bytes.

- The severity of this remains to be seen, but variable length conn ids
will introduce more complexity in parsers and anything that utilizes the
conn id (e.g. handshake key generation). It might make the invariants more
complex as well. The whole thing, frankly, makes my head hurt.

I humbly suggest the following proposal might avoid or mitigate some of
these problems:

1. Every connection has a long-lived Client-generated Connection ID (CGCID)
and Server-generated Connection ID (SGCID). The CGCID is 8 bytes and the
SGCID is 16 bytes.

2. The CGCID is used to derive the handshake key. (unchanged from status
quo)

3. The initial packet uses the CGCID.  All other handshake packets use the
SGCID. This is unchanged from the status quo.

4. All 1-RTT packets by sent by the client use the SGCID. All 1-RTT packets
sent by the server use the CGCID. This has two important properties:
           a) The server gets the 16 Bytes of entropy the load balancer
needs
           b) The server->client direction, which in the usual case has
most of the data, has a lower-overhead CID.

5. The algorithm that generates SGCID MUST have different output given a
different CGCID. [We might strengthen this language further: you wouldn't
want to simply add the NEW_CONN_ID sequence number to the existing SGCID,
for instance].

6. In advance of migration, the client sends a NEW_CONN_ID frame to provide
a new CGCID (possibly omitting the stateless reset token). The server MUST
respond with a NEW_CONN_ID that provides a new SGCID derived from the new
CGCID. All packets on the new path use these CIDs.

If people like this, I can generate a PR. I am very open to various tweaks
to the general approach as well. I wanted to get this out there before the
variable-length CID team gets deep in the weeds.

Martin Duke

---

From: Martin Thomson <[email-masked]>
Date: Wed, 24 Jan 2018 16:19:39 +1100

We have already concluded that if you want to do sane crypto, plus
some sort of key identification, then you need MORE than 16 octets
(though not much more).  That makes things more complicated.  ekr has
an outcome that he will write up.

On Wed, Jan 24, 2018 at 4:08 PM, Martin Duke <[email-masked]> wrote:
> - The client desires unlinkability, but I suspect the market will provide no
> incentives for servers to work very hard to be unlinkable. There were
> - The severity of this remains to be seen, but variable length conn ids will
> introduce more complexity in parsers and anything that utilizes the conn id
> (e.g. handshake key generation). It might make the invariants more complex
> as well. The whole thing, frankly, makes my head hurt.
>
>            b) The server->client direction, which in the usual case has most
> of the data, has a lower-overhead CID.
>

---

From: Martin Duke <[email-masked]>
Date: Wed, 24 Jan 2018 16:21:15 +1100

Very well, replace 16 with whatever number you guys come up with.

On Wed, Jan 24, 2018 at 4:19 PM, Martin Thomson <[email-masked]>
wrote:

> will

---

From: "Lubashev, Igor" <[email-masked]>
Date: Wed, 24 Jan 2018 05:34:47 +0000

The two alternatives to allow for key rotation to “avoid” going over 16 octets are:

  1.  (Victor voiced this today) Steal a code point from the packet type: have 2 bits that represent:
0-byte connection id;
8-byte connection id;
16-byte connection id (key a);
16-byte connection id (key b)

  1.  “Trial Encryption” : Steal a bit from your 128 bit connection ID

Your bit 0 of your Connection ID will represent the key used for encryption.
Since you have entropy in your Connection ID, keep generating new entropy and encrypting, until bit 0 comes out just the way you want it.  On average, you will do 0.75 extra encryption operations.

  *   Igor

From: Martin Duke [mailto:[email-masked]]
Sent: Wednesday, January 24, 2018 12:21 AM
To: Martin Thomson <[email-masked]>
Cc: IETF QUIC WG <[email-masked]>
Subject: Re: A better way to do conn id?

On Wed, Jan 24, 2018 at 4:19 PM, Martin Thomson <[email-masked]<mailto:[email-masked]>> wrote:

---

From: Subodh Iyengar <[email-masked]>
Date: Wed, 24 Jan 2018 08:00:38 +0000

> (Victor voiced this today) Steal a code point from the packet type: have 2 bits that represent

Why do we need to represent the size of the connection id as bits in the packet? We usually represent the lengths as bits in the packet for 2 reasons:

  1.  to be able to change them per packet
  2.  If they need to be interpreted by unrelated parties.

I raised this question in the meeting today whether or not connid size needs to change with every packet and the answer seemed no. Also in the current design the interpretation of connid is only relevant to the server / related parties, in which case the server could represent it's connid in its own self describing format which doesn't need any new bits. L3 load balancers and L7 load balancers would share the knowledge of the format of the connection id to determine how long it is. So it would seem like we don't need any extra bits. Are any of these assumptions I'm making incorrect?

Subodh

________________________________
From: QUIC <[email-masked]> on behalf of Lubashev, Igor <[email-masked]>
Sent: Tuesday, January 23, 2018 9:34:47 PM
To: Martin Duke; Martin Thomson
Cc: IETF QUIC WG
Subject: RE: A better way to do conn id?

0-byte connection id;

8-byte connection id;

  *   Igor

---

From: "Lubashev, Igor" <[email-masked]>
Date: Wed, 24 Jan 2018 13:42:43 +0000

The argument that connection id can be self-describing is not wrong.

Connection id can be self-describing, and it would need to be, if the sever is to allow using different lengths for different connections and to do key rotation. It does add complexity to connection id generation (cannot easily use AES instruction to do encryption) and reduces the number of available bits, even for shorter connection IDs.

Victor's suggestion is to use just one extra bit in the packet type octet to avoid all of these troubles. It does bring up questions of requiring consistency in those bits throughout the connection lifetime - a definite "cost" of the scheme. But it also has benefits (see above). So this seems to be a viable option, but not a obvious option (since trade-offs are needed).

- Igor

-----Original Message-----
From: Subodh Iyengar [[email-masked]]
Received: Wednesday, 24 Jan 2018, 3:00AM
To: Lubashev, Igor [[email-masked]]; Martin Duke [[email-masked]]; Martin Thomson [[email-masked]]
CC: IETF QUIC WG [[email-masked]]
Subject: Re: A better way to do conn id?

Subodh

0-byte connection id;

8-byte connection id;

  *   Igor

---

From: "Fossati, Thomas (Nokia - GB/Cambridge, UK)" <[email-masked]>
Date: Wed, 24 Jan 2018 13:53:33 +0000

Why do we need to represent the size of the connection id as bits in the packet? We usually represent the lengths as bits in the packet for 2 reasons:
1.      to be able to change them per packet
2.      If they need to be interpreted by unrelated parties.
This same thing came out in the discussion around connection-id in DTLS.  If troubleshooting is a concern (and I think it should), then an “unrelated” party might need to decode CID (e.g., to single out a flow among gazillion others).

Cheers

---

From: Kazuho Oku <[email-masked]>
Date: Thu, 25 Jan 2018 01:20:20 +1100

2018-01-24 16:34 GMT+11:00 Lubashev, Igor <[email-masked]>:

> Since you have entropy in your Connection ID, keep generating new entropy
> and encrypting, until bit 0 comes out just the way you want it.  On
> average, you will do 0.75 extra encryption operations.
>

Thank you for summarizing the two approaches.

What I am bit afraid of using the bits in the packet type is that the
approach hardcodes the relation between the frequency of key rotation and
the maximum lifetime of a QUIC connection.

Consider the case where you want to switch from key A to key B. Correct me
if I am wrong, but IIUC there is no way for a server to enforce the client
to switch to a new connection ID. Therefore, the server will be enforced to
shutdown all the connections using the IDs generated by using key A before
the key gets retired.

For example, if you plan to do the rollover from key A to key B in 24
hours, the minimum maximum of the lifetime of a connection will be
restricted to 24 hours.

Do we want to bake such restriction into the protocol?

If we use trial encryption, the issue between the sped of key rotation and
the minimum maximum of a QUIC connection would be left to each server-side
implementation, though you might end up being required to do more "mining"
(i.e., find a connection ID that can survive _multiple_ generations of key
rotations).

Or, should we introduce a mechanism that allows a server to _enforce_
connection ID migration, considering the fact that the issue exists in both
approaches?

>
>    - Igor
>
>
>
> *From:* Martin Duke [mailto:[email-masked]]
> *Sent:* Wednesday, January 24, 2018 12:21 AM
> *To:* Martin Thomson <[email-masked]>
> *Cc:* IETF QUIC WG <[email-masked]>
> *Subject:* Re: A better way to do conn id?
>
>
>

-- 
Kazuho Oku

---

From: "Lubashev, Igor" <[email-masked]>
Date: Wed, 24 Jan 2018 16:33:26 +0000

Thanks for pointing out the hazard of key rotation frequency vs connection duration.

  *   Do we want to bake such restriction into the protocol?

The extra codepoint proposal is a helpful common-case optimization, in case the frequency of key rotation is sufficiently low.  It is definitely not a solution for all possible use cases.  However, there is nothing to prevent a server with more frequent key rotations to do something else.  The “something else” could be:

  1.  Encode additional bit(s) in the connection ID
  2.  Before expiring key A, create state on the load balancers for the few very long-lasting connections still using A.
  3.  Something else

Your idea of having a mechanism to force a switch to the new connection ID is an interesting and separate idea.  I am in favor of this, as it may give us more flexibility.  Don’t see that this must be a v1 feature.

  *   Igor

From: Kazuho Oku [mailto:[email-masked]]
Sent: Wednesday, January 24, 2018 9:20 AM
To: Lubashev, Igor <[email-masked]>
Cc: Martin Duke <[email-masked]>; Martin Thomson <[email-masked]>; IETF QUIC WG <[email-masked]>
Subject: Re: A better way to do conn id?

2018-01-24 16:34 GMT+11:00 Lubashev, Igor <[email-masked]<mailto:[email-masked]>>:
The two alternatives to allow for key rotation to “avoid” going over 16 octets are:

What I am bit afraid of using the bits in the packet type is that the approach hardcodes the relation between the frequency of key rotation and the maximum lifetime of a QUIC connection.

Consider the case where you want to switch from key A to key B. Correct me if I am wrong, but IIUC there is no way for a server to enforce the client to switch to a new connection ID. Therefore, the server will be enforced to shutdown all the connections using the IDs generated by using key A before the key gets retired.

For example, if you plan to do the rollover from key A to key B in 24 hours, the minimum maximum of the lifetime of a connection will be restricted to 24 hours.

If we use trial encryption, the issue between the sped of key rotation and the minimum maximum of a QUIC connection would be left to each server-side implementation, though you might end up being required to do more "mining" (i.e., find a connection ID that can survive _multiple_ generations of key rotations).

Or, should we introduce a mechanism that allows a server to _enforce_ connection ID migration, considering the fact that the issue exists in both approaches?

  *   Igor

From: Martin Duke [mailto:[email-masked]<mailto:[email-masked]>]
Sent: Wednesday, January 24, 2018 12:21 AM
To: Martin Thomson <[email-masked]<mailto:[email-masked]>>
Cc: IETF QUIC WG <[email-masked]<mailto:[email-masked]>>
Subject: Re: A better way to do conn id?

--
Kazuho Oku

---

From: Hannes Tschofenig <[email-masked]>
Date: Wed, 24 Jan 2018 16:36:09 +0000

Hi Martin,

Your entire story is built on the claim that “variable length conn ids will introduce more complexity in parsers”.

Having implemented parsing of variable length fields in TLS 1.3 extensively last year I have to say that it is not such a big deal, particularly compared to all the complexity found elsewhere (which is also true for QUIC).

In essence you are talking about a few lines of code. Your solution then also requires additional lines of code elsewhere.

Ciao
Hannes

From: QUIC [mailto:[email-masked]] On Behalf Of Martin Duke
Sent: 23 January 2018 23:09
To: IETF QUIC WG
Subject: A better way to do conn id?

Today's variable-length connection ID discussion made me realize some problems with the current architecture, while the new architecture doesn't fix some of them and creates whole new ones. Issues:

- The client desires unlinkability, but I suspect the market will provide no incentives for servers to work very hard to be unlinkable. There were conflicting "layer 9" arguments that variable conn ID makes this problem worse or better.

- The severity of this remains to be seen, but variable length conn ids will introduce more complexity in parsers and anything that utilizes the conn id (e.g. handshake key generation). It might make the invariants more complex as well. The whole thing, frankly, makes my head hurt.

I humbly suggest the following proposal might avoid or mitigate some of these problems:

1. Every connection has a long-lived Client-generated Connection ID (CGCID) and Server-generated Connection ID (SGCID). The CGCID is 8 bytes and the SGCID is 16 bytes.

2. The CGCID is used to derive the handshake key. (unchanged from status quo)

3. The initial packet uses the CGCID.  All other handshake packets use the SGCID. This is unchanged from the status quo.

4. All 1-RTT packets by sent by the client use the SGCID. All 1-RTT packets sent by the server use the CGCID. This has two important properties:
           a) The server gets the 16 Bytes of entropy the load balancer needs
           b) The server->client direction, which in the usual case has most of the data, has a lower-overhead CID.

5. The algorithm that generates SGCID MUST have different output given a different CGCID. [We might strengthen this language further: you wouldn't want to simply add the NEW_CONN_ID sequence number to the existing SGCID, for instance].

6. In advance of migration, the client sends a NEW_CONN_ID frame to provide a new CGCID (possibly omitting the stateless reset token). The server MUST respond with a NEW_CONN_ID that provides a new SGCID derived from the new CGCID. All packets on the new path use these CIDs.

If people like this, I can generate a PR. I am very open to various tweaks to the general approach as well. I wanted to get this out there before the variable-length CID team gets deep in the weeds.

Martin Duke

IMPORTANT NOTICE: The contents of this email and any attachments are confidential and may also be privileged. If you are not the intended recipient, please notify the sender immediately and do not disclose the contents to any other person, use it for any purpose, or store or copy the information in any medium. Thank you.