Subject: Increasing QUIC connection ID size

From: Victor Vasiliev <[email-masked]>
Date: Thu, 11 Jan 2018 18:16:10 -0500

Hi everyone,

In the current version of QUIC, the connection ID size is fixed to be a
64-bit opaque blob, and that is set as an invariant in the protocol.

I’ve looked into possibility of using a connection ID to encode the
specific server details into it (to provide stability of the connection in
case of load balancing changes, especially BGP flaps for anycast IPs), and
have chatted about this with other people I knew were interested in this.
It seems like 64 bits might be too small for this purpose, and we might
want to leave an opportunity to extend the connection ID size.

The basic idea is that you want to be able to:

   1. Store some routing metadata in the connection ID.
   2. Have some entropy that allows distinguish users with identical
   routing metadata.
   3. Have a checksum to ensure the validity of routing information
   4. Encrypt the information above to prevent disclosing the route
   information and allow generating uncorrelatable connection IDs.

There are two underlying issues here.  The first problem is that all of
this does not fit well into 64 bits, and you have to seriously compromise
on the strength of the checksum (which is bad especially if you want it to
be a MAC rather than a checksum).  The second problem is that encrypting
64-bit values fast is actually fairly hard since the block ciphers easily
available in hardware have 128-bit block size, and the performance
requirements on load balancers are tighter than on servers.

In other words, having a 128-bit connection ID provides for an easy secure
way to generate unlinkable connection IDs on migration.

So, the problem we’re trying to solve is that the connection ID is too
small.  There are two questions I believe the working group should answer
at this point:

   1. Do we want to address this problem at this point in standardization
   process?
   2. If we don’t address this problem right now, how do we structure the
   standard in a way that we can extend the connection ID in the future?

There are multiple ways to solve the problem of making connection ID
larger.  One is to just add extra bit to the “omit connection ID” field to
allow 128-bit connection IDs.  Another approach is to allow connection ID
size to be explicitly specified by the server, and then assume that the
load balancer knows that size and no one else on the path needs to read it.

There’s also a question of how much of connection IDs do middleboxes
(excluding load balancers and other boxes owned by the same entity as
either client or server) need to know.  We could go for both “middleboxes
should be always able to read the entire ID” and “middleboxes should not
read connection IDs at all options”, but I think there’s also a room for
more flexible formulations like “middleboxes always get first 64 bits and
they have useful entropy to distinguish connections”.

  -- Victor.

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Thu, 11 Jan 2018 15:51:39 -0800

I can also see a need for larger connection ID’s for routing purposes in
overlay networks, but I decided it was probably better to prefix the QUIC
header in that case.

It is worth noting that if you have a non-unique tuple of port-address
pairs, you need the connection ID in every packet, and that can be a lot of
overhead. So a large ID would likely isolate that version to a dedicated
purpose, and then you might as well add a packet prefix.

An alternative solution is to use the connection ID as an index into a
routing table that has the real details, but this requires that early
packets of the connection carry those details in a way that routers can
pick up which probably isn’t practical.

A more practical solution is to keep the connection ID as is to serve its
primary purpose. A given protocol version could negotiate an extension the
the clear text header. Even if those data are not directly following the
connection ID, they can easily be picked up by router. This is essentially
the same as a packet prefix, except that the QUIC invariants are now
maintained.

As to encryption: block encryption generally works by xor’ing a “random”
value to the clear text. AES produces such a value from a counter or
similar unique value per block but does not need the clear text data at
all. The output of AES is simply XOR’ed with the clear text data (this can
be different when encrypting multiple blocks). This means that if the block
size is 128 bit you can easily encrypt 64 bytes by XOR’ing with the first
64-bits of the AES output. But you likely want to zero extend instead due
to auth tag:

It is not safe to use block encryption alone. It must nearly always be
associated with an authentication tag as with AES-GCM. Otherwise an
attacker will quickly learn that, say, bit 53 and bit 32 affects routing
and can trivially cause at least 1/4 packets to land somewhere else just be
flipping either bit. A compact auth tag does not have to be very long for
such a short message but it adds to the overall size requirement and
complexity of the solution.It could be generated with CMAC that are two AES
encryption rounds. (CMAC on connection ID could, BTW, also be used to very
quickly reject invalid QUIC packets, which I have proposed earlier). The
CMAC output will be one AES block, but it can be truncated depending on the
security level required.

Kind Regards,
Mikkel Fahnøe Jørgensen

On 12 January 2018 at 00.16.21, Victor Vasiliev ([email-masked]) wrote:

Hi everyone,

  -- Victor.

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Thu, 11 Jan 2018 15:54:20 -0800

EDIT: I didn’t propose CMAC on connection ID - it needs to change, so it
would be on the packet number for the sake of fast rejection of invalid
packets. The counter argument was that it is fast enough to check the auth
tag of the entire message.

Kind Regards,
Mikkel Fahnøe Jørgensen

On 12 January 2018 at 00.51.39, Mikkel Fahnøe Jørgensen ([email-masked])
wrote:

Kind Regards,
Mikkel Fahnøe Jørgensen

Hi everyone,

  -- Victor.

---

From: "Lubashev, Igor" <[email-masked]>
Date: Thu, 11 Jan 2018 23:56:52 +0000

I am interested in exploring this proposal, since it allows for more flexible schemes of encoding routing metadata and a checksum.  I would also like to be explicit about the connection ID size in a packet header, though, since it greatly simplifies the implementation.

  *   Igor
From: Victor Vasiliev [mailto:[email-masked]]
Sent: Thursday, January 11, 2018 6:16 PM
To: IETF QUIC WG <[email-masked]>
Subject: Increasing QUIC connection ID size

Hi everyone,

In the current version of QUIC, the connection ID size is fixed to be a 64-bit opaque blob, and that is set as an invariant in the protocol.

I’ve looked into possibility of using a connection ID to encode the specific server details into it (to provide stability of the connection in case of load balancing changes, especially BGP flaps for anycast IPs), and have chatted about this with other people I knew were interested in this.  It seems like 64 bits might be too small for this purpose, and we might want to leave an opportunity to extend the connection ID size.

  1.  Store some routing metadata in the connection ID.
  2.  Have some entropy that allows distinguish users with identical routing metadata.
  3.  Have a checksum to ensure the validity of routing information
  4.  Encrypt the information above to prevent disclosing the route information and allow generating uncorrelatable connection IDs.
There are two underlying issues here.  The first problem is that all of this does not fit well into 64 bits, and you have to seriously compromise on the strength of the checksum (which is bad especially if you want it to be a MAC rather than a checksum).  The second problem is that encrypting 64-bit values fast is actually fairly hard since the block ciphers easily available in hardware have 128-bit block size, and the performance requirements on load balancers are tighter than on servers.

In other words, having a 128-bit connection ID provides for an easy secure way to generate unlinkable connection IDs on migration.

So, the problem we’re trying to solve is that the connection ID is too small.  There are two questions I believe the working group should answer at this point:

  1.  Do we want to address this problem at this point in standardization process?
  2.  If we don’t address this problem right now, how do we structure the standard in a way that we can extend the connection ID in the future?
There are multiple ways to solve the problem of making connection ID larger.  One is to just add extra bit to the “omit connection ID” field to allow 128-bit connection IDs.  Another approach is to allow connection ID size to be explicitly specified by the server, and then assume that the load balancer knows that size and no one else on the path needs to read it.

There’s also a question of how much of connection IDs do middleboxes (excluding load balancers and other boxes owned by the same entity as either client or server) need to know.  We could go for both “middleboxes should be always able to read the entire ID” and “middleboxes should not read connection IDs at all options”, but I think there’s also a room for more flexible formulations like “middleboxes always get first 64 bits and they have useful entropy to distinguish connections”.

  -- Victor.

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Thu, 11 Jan 2018 16:25:27 -0800

Actually, on encryption of connection ID, this is not so simple.

We must assume there is only a single key for many connections because the
router is not part of a key exchange. This unique value or counter used for
encrypting a single block cannot be the same for two different connections
ID’s, but it can be public. This means that it must be stored in the packet
header. And, as it turns out, random connection ID chosen by a trusted
source, can be used for such a unique value. But then it must be used to
encrypt and/or authenticate something else carrying the actual routing
information. So now you start to really need some extra payload.

Alternatively the routing information is entirely random such as content
hashed routing. Then you only need to authenticate the routing data. You
can do that with a HMAC, and CMAC could probably also work. The additional
benefit is that you can probably get away with 64-bits for all routing
information possibly including the auth tag. Say 48 bits of routing data
and 16 bits of auth tag.

Kind Regards,
Mikkel Fahnøe Jørgensen

On 12 January 2018 at 00.57.21, Lubashev, Igor ([email-masked]) wrote:

I am interested in exploring this proposal, since it allows for more
flexible schemes of encoding routing metadata and a checksum.  I would also
like to be explicit about the connection ID size in a packet header,
though, since it greatly simplifies the implementation.

   - Igor

*From:* Victor Vasiliev [mailto:[email-masked]]
*Sent:* Thursday, January 11, 2018 6:16 PM
*To:* IETF QUIC WG <[email-masked]>
*Subject:* Increasing QUIC connection ID size

Hi everyone,

  -- Victor.

---

From: Roberto Peon <[email-masked]>
Date: Fri, 12 Jan 2018 00:45:16 +0000

Having the server specify the connID-size as part of the connection setup+version negotiation would certainly be grease-y.

A larger connID helps to solve a lot of L4<->L7 routing issues, agreed, pre-supposing that the server always picks the new/alternate conn-ID for the client.
-=R

From: QUIC <[email-masked]> on behalf of Victor Vasiliev <[email-masked]>
Date: Thursday, January 11, 2018 at 3:16 PM
To: IETF QUIC WG <[email-masked]>
Subject: Increasing QUIC connection ID size

Hi everyone,

  -- Victor.

---

From: "Lubashev, Igor" <[email-masked]>
Date: Fri, 12 Jan 2018 00:55:03 +0000

I think the idea is that the key used to encrypt connection ID is known to both the server and the router.  That key would need to be rotated periodically, and the router would need to understand which key was used for this particular connection, but that can be solved.

From: Mikkel Fahnøe Jørgensen [mailto:[email-masked]]
Sent: Thursday, January 11, 2018 7:25 PM
To: Lubashev, Igor <[email-masked]>; Victor Vasiliev <[email-masked]>; IETF QUIC WG <[email-masked]>
Subject: RE: Increasing QUIC connection ID size

We must assume there is only a single key for many connections because the router is not part of a key exchange. This unique value or counter used for encrypting a single block cannot be the same for two different connections ID’s, but it can be public. This means that it must be stored in the packet header. And, as it turns out, random connection ID chosen by a trusted source, can be used for such a unique value. But then it must be used to encrypt and/or authenticate something else carrying the actual routing information. So now you start to really need some extra payload.

Alternatively the routing information is entirely random such as content hashed routing. Then you only need to authenticate the routing data. You can do that with a HMAC, and CMAC could probably also work. The additional benefit is that you can probably get away with 64-bits for all routing information possibly including the auth tag. Say 48 bits of routing data and 16 bits of auth tag.

Kind Regards,
Mikkel Fahnøe Jørgensen

On 12 January 2018 at 00.57.21, Lubashev, Igor ([email-masked]<mailto:[email-masked]>) wrote:
I am interested in exploring this proposal, since it allows for more flexible schemes of encoding routing metadata and a checksum.  I would also like to be explicit about the connection ID size in a packet header, though, since it greatly simplifies the implementation.

  *   Igor
From: Victor Vasiliev [mailto:[email-masked]<mailto:[email-masked]>]
Sent: Thursday, January 11, 2018 6:16 PM
To: IETF QUIC WG <[email-masked]<mailto:[email-masked]>>
Subject: Increasing QUIC connection ID size

Hi everyone,

  -- Victor.

---

From: Jana Iyengar <[email-masked]>
Date: Thu, 11 Jan 2018 17:00:23 -0800

Having thought about this a bit, I like the idea of encrypting CIDs. The
strongest argument for me is that we really want unlinkable CIDs, and
crypto is a quite simple way of generating such CIDs.  Encrypted CIDs also
allows for a simple solution to the problem of generating server-chosen
CIDs that route back to the same server, since any structure in the
plaintext is not visible in the CID that is sent on the wire.

Crypto in 128 bits is readily available, making it less expensive for
hardware (load balancers) to do it per packet, so using 128 bits seems like
a good idea.

On Thu, Jan 11, 2018 at 4:45 PM, Roberto Peon <[email-masked]> wrote:

> Having the server specify the connID-size as part of the connection
> setup+version negotiation would certainly be grease-y.
>
> A larger connID helps to solve a lot of L4<->L7 routing issues, agreed,
> pre-supposing that the server always picks the new/alternate conn-ID for
> the client.
>
> -=R
>
>
>
> *From: *QUIC <[email-masked]> on behalf of Victor Vasiliev <
> [email-masked]>
> *Date: *Thursday, January 11, 2018 at 3:16 PM
> *To: *IETF QUIC WG <[email-masked]>
> *Subject: *Increasing QUIC connection ID size
>
>
>
> Hi everyone,
>
>
>

---

From: Roberto Peon <[email-masked]>
Date: Fri, 12 Jan 2018 01:05:02 +0000

Correct/agreed. The L4 ‘router’ must be able to decrypt/interpret the data in order to act upon it. This requires sharing of some key material.
-=R

From: QUIC <[email-masked]> on behalf of "Lubashev, Igor" <[email-masked]>
Date: Thursday, January 11, 2018 at 4:55 PM
To: Mikkel Fahnøe Jørgensen <[email-masked]>, Victor Vasiliev <[email-masked]>, IETF QUIC WG <[email-masked]>
Subject: RE: Increasing QUIC connection ID size

Kind Regards,
Mikkel Fahnøe Jørgensen

  *   Igor

Hi everyone,

  -- Victor.

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Thu, 11 Jan 2018 17:09:02 -0800

This was also my intention. That the server and router share the key. But
also that multiple connection ID’s are encrypted with the same key and a
unique identifier.

Igor says the key can be matched to the connection. This is true, each
connection can have a unique derived key. But it is largely the same as
using a single key with different IV since we are only encrypting a single
block. Details may very on how insecure the solution is if the unique value
is not unique. But the challenge remains that there needs to be a unique
identifier and packet number and 4-tuple is not it.

Kind Regards,
Mikkel Fahnøe Jørgensen

On 12 January 2018 at 02.05.18, Roberto Peon ([email-masked]) wrote:

Correct/agreed. The L4 ‘router’ must be able to decrypt/interpret the data
in order to act upon it. This requires sharing of some key material.

-=R

*From: *QUIC <[email-masked]> on behalf of "Lubashev, Igor" <
[email-masked]>
*Date: *Thursday, January 11, 2018 at 4:55 PM
*To: *Mikkel Fahnøe Jørgensen <[email-masked]>, Victor Vasiliev <
[email-masked]>, IETF QUIC WG <[email-masked]>
*Subject: *RE: Increasing QUIC connection ID size

I think the idea is that the key used to encrypt connection ID is known to
both the server and the router.  That key would need to be rotated
periodically, and the router would need to understand which key was used
for this particular connection, but that can be solved.

*From:* Mikkel Fahnøe Jørgensen [mailto:[email-masked]]
*Sent:* Thursday, January 11, 2018 7:25 PM
*To:* Lubashev, Igor <[email-masked]>; Victor Vasiliev <
[email-masked]>; IETF QUIC WG <[email-masked]>
*Subject:* RE: Increasing QUIC connection ID size

Kind Regards,

Mikkel Fahnøe Jørgensen

   - Igor

Hi everyone,

  -- Victor.

---

From: Jana Iyengar <[email-masked]>
Date: Thu, 11 Jan 2018 17:09:12 -0800

Just thinking aloud about key rotation -- you could always use the
high-order bit as an expicit key selection bit... the server and load
balancer can then use this bit during rotation to change keys without
breakages.

---

From: Roberto Peon <[email-masked]>
Date: Fri, 12 Jan 2018 01:12:59 +0000

Yup!
If you’re paranoid, you can encrypt twice: One less-secure key which allows decryption of the key ID bits (and the rest of the bits, which are along for the ride), and then another key (indicated by the first) which allows decryption and subsequent interpretation of encoding of the the L7 address (plus salt somewhere in there) into the remaining bits.

Ultimately, knowing a scheme is possible is sufficient here so long as we delegate connID assignment to the server.
-=R

From: Jana Iyengar <[email-masked]>
Date: Thursday, January 11, 2018 at 5:09 PM
To: Roberto Peon <[email-masked]>
Cc: "Lubashev, Igor" <[email-masked]>, Mikkel Fahnøe Jørgensen <[email-masked]>, Victor Vasiliev <[email-masked]>, IETF QUIC WG <[email-masked]>
Subject: Re: Increasing QUIC connection ID size

Just thinking aloud about key rotation -- you could always use the high-order bit as an expicit key selection bit... the server and load balancer can then use this bit during rotation to change keys without breakages.

On Thu, Jan 11, 2018 at 5:05 PM, Roberto Peon <[email-masked]<mailto:[email-masked]>> wrote:
Correct/agreed. The L4 ‘router’ must be able to decrypt/interpret the data in order to act upon it. This requires sharing of some key material.
-=R

From: QUIC <[email-masked]<mailto:[email-masked]>> on behalf of "Lubashev, Igor" <[email-masked]<mailto:[email-masked]>>
Date: Thursday, January 11, 2018 at 4:55 PM
To: Mikkel Fahnøe Jørgensen <[email-masked]<mailto:[email-masked]>>, Victor Vasiliev <[email-masked]<mailto:[email-masked]>>, IETF QUIC WG <[email-masked]<mailto:[email-masked]>>

From: Mikkel Fahnøe Jørgensen [mailto:[email-masked]<mailto:[email-masked]>]
Sent: Thursday, January 11, 2018 7:25 PM
To: Lubashev, Igor <[email-masked]<mailto:[email-masked]>>; Victor Vasiliev <[email-masked]<mailto:[email-masked]>>; IETF QUIC WG <[email-masked]<mailto:[email-masked]>>
Subject: RE: Increasing QUIC connection ID size

Kind Regards,
Mikkel Fahnøe Jørgensen

  *   Igor

Hi everyone,

  -- Victor.

---

From: Christian Huitema <[email-masked]>
Date: Thu, 11 Jan 2018 16:47:19 -1000

We have a prototype implementation in Picoquic in which the connection
ID can be split so some bits are random and some bits are used for
routing to a specific server -- thanks Igor for that. It makes for nice
experiments, but it is a denial of service waiting to happen. For
example, attackers could set the bits in such a way as to target a
specific server in a pool, or they could learn which connections are on
the same server and use that later for some kind of same server attack.
It would be better if that information was not in clear text. In fact,
the picoquic implementation use a callback to ask for the new value --
presumably from the router. That callback could return anything,
including an encrypted value.

On the other hand, it is not clear to me that we need full encryption.
For example, assume that the server that needs a connection ID can ask
it from the router. The router could pick one at random, make sure that
it is properly documented in the routing tables and that there is no
collision, and then pass it back to the server. No encryption needed,
but of course lots of state.

If the router does not want to keep the state, it can indeed create a
connection ID by encrypting a <nonce, server-ID> tuple. But it does not
follow that the encryption needs to be 128 bits. For example, it could
use a 64 bit algorithm like Blowfish.

So I am not sure that we actually need to change the length. And I am a
bit concerned by the incremental overhead if the connection ID suddenly
becomes very large.

On 1/11/2018 2:25 PM, Mikkel Fahnøe Jørgensen wrote:
> We must assume there is only a single key for many connections because
> the router is not part of a key exchange. This unique value or counter
> used for encrypting a single block cannot be the same for two
> different connections ID’s, but it can be public. This means that it
> must be stored in the packet header. And, as it turns out, random
> connection ID chosen by a trusted source, can be used for such a
> unique value. But then it must be used to encrypt and/or authenticate
> something else carrying the actual routing information. So now you
> start to really need some extra payload.
>
> Alternatively the routing information is entirely random such as
> content hashed routing. Then you only need to authenticate the routing
> data. You can do that with a HMAC, and CMAC could probably also work.
> The additional benefit is that you can probably get away with 64-bits
> for all routing information possibly including the auth tag. Say 48
> bits of routing data and 16 bits of auth tag.
>
> Kind Regards,
> Mikkel Fahnøe Jørgensen
>
>
>> flexible schemes of encoding routing metadata and a checksum.  I
>> would also like to be explicit about the connection ID size in a
>> packet header, though, since it greatly simplifies the implementation.
>>
>>  
>>
>>   * Igor
>>
>> *From:* Victor Vasiliev [mailto:[email-masked]
>> <mailto:[email-masked]>]
>> *To:* IETF QUIC WG <[email-masked] <mailto:[email-masked]>>
>> In the current version of QUIC, the connection ID size is fixed to be
>> a 64-bit opaque blob, and that is set as an invariant in the protocol.
>>
>>  
>>
>> specific server details into it (to provide stability of the
>> connection in case of load balancing changes, especially BGP flaps
>> for anycast IPs), and have chatted about this with other people I
>> knew were interested in this.  It seems like 64 bits might be too
>> small for this purpose, and we might want to leave an opportunity to
>> extend the connection ID size.
>>
>>  
>>
>> There are two underlying issues here.  The first problem is that all
>> of this does not fit well into 64 bits, and you have to seriously
>> compromise on the strength of the checksum (which is bad especially
>> if you want it to be a MAC rather than a checksum).  The second
>> problem is that encrypting 64-bit values fast is actually fairly hard
>> since the block ciphers easily available in hardware have 128-bit
>> block size, and the performance requirements on load balancers are
>> tighter than on servers.  
>>
>>  
>>
>> In other words, having a 128-bit connection ID provides for an easy
>> secure way to generate unlinkable connection IDs on migration.
>>
>>  
>>
>> So, the problem we’re trying to solve is that the connection ID is
>> too small.  There are two questions I believe the working group
>> should answer at this point:
>>
>>  2. If we don’t address this problem right now, how do we structure
>>     the standard in a way that we can extend the connection ID in the
>>     future?
>>
>> larger.  One is to just add extra bit to the “omit connection ID”
>> field to allow 128-bit connection IDs.  Another approach is to allow
>> connection ID size to be explicitly specified by the server, and then
>> assume that the load balancer knows that size and no one else on the
>> path needs to read it.
>>
>>  
>>
>> either client or server) need to know.  We could go for both
>> “middleboxes should be always able to read the entire ID” and
>> “middleboxes should not read connection IDs at all options”, but I
>> think there’s also a room for more flexible formulations like
>> “middleboxes always get first 64 bits and they have useful entropy to
>> distinguish connections”.
>>
>>  
>>
>>   -- Victor.
>>

---

From: Willy Tarreau <[email-masked]>
Date: Fri, 12 Jan 2018 06:55:54 +0100

On Fri, Jan 12, 2018 at 01:05:02AM +0000, Roberto Peon wrote:
> Correct/agreed. The L4 'router' must be able to decrypt/interpret the data in
> order to act upon it. This requires sharing of some key material.

At least we need to keep in mind that it's critical to ensure consistency
between all front nodes (think DNS+anycast BGP+ECMP LB before reaching the
L7 LB). It's critical that all equipments in the path are able to coherently
find the correct path to the origin node without having to actually learn
anything from the packets. And synchronizing keys between multiple nodes
is often a pain (though never impossible).

At the HTTP workshop 2 years ago, I proposed to place some upfront routing
information on TLS to save LBs from having to decrypting the stream to
find what server the stream had to be sent to. The proposal was to have
a small ID, typically 16 bits, for this. In my opinion this is another
option we can consider here : with only 16 bits, you can easily store a
server ID in a reasonable farm size (even dynamic), but you don't have
enough information to track users. So it could remain accessible in
clear, saving front nodes from having to decrypt anything or share keys.

Willy

---

From: Martin Thomson <[email-masked]>
Date: Fri, 12 Jan 2018 17:18:52 +1100

https://tools.ietf.org/html/draft-ietf-tls-dtls-connection-id-00 is
currently DTLS specific.  Is this something that you feel should be
more general?

I think that people reading this thread should be aware of the
alternative design options here, the above draft identifies one.  Note
that there are several key ways in which this might be unsuitable for
QUIC in its current form; it makes a different set of trade-offs.

---

From: Göran Eriksson AP <[email-masked]>
Date: Fri, 12 Jan 2018 06:20:21 +0000

On 2018-01-12, 01:45, "QUIC on behalf of Roberto Peon" <[email-masked]<mailto:[email-masked]> on behalf of [email-masked]<mailto:[email-masked]>> wrote:

> +1. And settling this issue early in the QUIC development would secure wide support in servers such as envoy and ngnx early on for connection establisment.

---

From: Willy Tarreau <[email-masked]>
Date: Fri, 12 Jan 2018 08:29:49 +0100

> currently DTLS specific.  Is this something that you feel should be

Hmm I don't know yet, this makes me think. I'm realizing that very often
the LB will not decide on the server from the initial packet if it starts
to take certain elements in consideration, so it may be needed to pass the
server identifier later. In the most basic DSR case it will work though.
But above there's provision for changing the connection ID later so that
could possibly work to some extents.

I need more time to think about it and I'm lagging behind on QUIC design,
so I'm mostly focusing on general architectural points that I want to be
sure we don't forget to address.

Willy

---

From: Ian Swett <[email-masked]>
Date: Fri, 12 Jan 2018 08:58:24 -0500

I would like to leave QUIC open for longer connection IDs in future
versions, so I'd like to specify the invariants in such a way that longer
connection Ids wouldn't violate them(ie: Victor's suggestion
of “middleboxes always get first 64 bits and they have useful entropy to
distinguish connections”.) but I'm reluctant to include 128 bit connection
IDs in v1 at this point.

I would also echo Christian's sentiment that the incremental overhead
starts becoming fairly large.

On Thu, Jan 11, 2018 at 9:47 PM, Christian Huitema <[email-masked]>
wrote:

> We have a prototype implementation in Picoquic in which the connection ID
> can be split so some bits are random and some bits are used for routing to
> a specific server -- thanks Igor for that. It makes for nice experiments,
> but it is a denial of service waiting to happen. For example, attackers
> could set the bits in such a way as to target a specific server in a pool,
> or they could learn which connections are on the same server and use that
> later for some kind of same server attack. It would be better if that
> information was not in clear text. In fact, the picoquic implementation use
> a callback to ask for the new value -- presumably from the router. That
> callback could return anything, including an encrypted value.
>
> On the other hand, it is not clear to me that we need full encryption. For
> example, assume that the server that needs a connection ID can ask it from
> the router. The router could pick one at random, make sure that it is
> properly documented in the routing tables and that there is no collision,
> and then pass it back to the server. No encryption needed, but of course
> lots of state.
>
> follow that the encryption needs to be 128 bits. For example, it could use
> a 64 bit algorithm like Blowfish.
>

---

From: "Lubashev, Igor" <[email-masked]>
Date: Fri, 12 Jan 2018 14:13:53 +0000

If the 128-bit option is not in V1, then it will be required for the 128-bit option to be signaled in the packet's invariant section (like a bit in the 1st byte). Otherwise, the very load balancers this is designed for will not know whether the connection ID has 64- or 128-bit format. (It would need to support both, since there would be clients stuck at V1.)

In fact, the security promises of having a 128-bit connection ID option (allows for making routing info harder to forge) are greatly diminished, when a load balancer has to support 64-bit connection IDs "forever".

-----Original Message-----
From: Ian Swett [[email-masked]]
Received: Friday, 12 Jan 2018, 8:59AM
To: Christian Huitema [[email-masked]]
CC: IETF QUIC WG [[email-masked]]
Subject: Re: Increasing QUIC connection ID size

I would like to leave QUIC open for longer connection IDs in future versions, so I'd like to specify the invariants in such a way that longer connection Ids wouldn't violate them(ie: Victor's suggestion of “middleboxes always get first 64 bits and they have useful entropy to distinguish connections”.) but I'm reluctant to include 128 bit connection IDs in v1 at this point.

I would also echo Christian's sentiment that the incremental overhead starts becoming fairly large.

On Thu, Jan 11, 2018 at 9:47 PM, Christian Huitema <[email-masked]<mailto:[email-masked]>> wrote:
We have a prototype implementation in Picoquic in which the connection ID can be split so some bits are random and some bits are used for routing to a specific server -- thanks Igor for that. It makes for nice experiments, but it is a denial of service waiting to happen. For example, attackers could set the bits in such a way as to target a specific server in a pool, or they could learn which connections are on the same server and use that later for some kind of same server attack. It would be better if that information was not in clear text. In fact, the picoquic implementation use a callback to ask for the new value -- presumably from the router. That callback could return anything, including an encrypted value.

On the other hand, it is not clear to me that we need full encryption. For example, assume that the server that needs a connection ID can ask it from the router. The router could pick one at random, make sure that it is properly documented in the routing tables and that there is no collision, and then pass it back to the server. No encryption needed, but of course lots of state.

If the router does not want to keep the state, it can indeed create a connection ID by encrypting a <nonce, server-ID> tuple. But it does not follow that the encryption needs to be 128 bits. For example, it could use a 64 bit algorithm like Blowfish.

So I am not sure that we actually need to change the length. And I am a bit concerned by the incremental overhead if the connection ID suddenly becomes very large.

Kind Regards,
Mikkel Fahnøe Jørgensen

  *   Igor

Hi everyone,

  -- Victor.

---

From: Ian Swett <[email-masked]>
Date: Fri, 12 Jan 2018 09:34:48 -0500

I think we'll want support for both no matter how we do this.

On Fri, Jan 12, 2018 at 9:13 AM, Lubashev, Igor <[email-masked]> wrote:

> If the 128-bit option is not in V1, then it will be required for the
> 128-bit option to be signaled in the packet's invariant section (like a bit
> in the 1st byte). Otherwise, the very load balancers this is designed for
> will not know whether the connection ID has 64- or 128-bit format. (It
> would need to support both, since there would be clients stuck at V1.)
>
> In fact, the security promises of having a 128-bit connection ID option
> (allows for making routing info harder to forge) are greatly diminished,
> when a load balancer has to support 64-bit connection IDs "forever".
>
>
> *From:* Ian Swett [[email-masked]]
> *Received:* Friday, 12 Jan 2018, 8:59AM
> *To:* Christian Huitema [[email-masked]]
> *CC:* IETF QUIC WG [[email-masked]]
> *Subject:* Re: Increasing QUIC connection ID size
>
>> For example, assume that the server that needs a connection ID can ask it
>> from the router. The router could pick one at random, make sure that it is
>> the router is not part of a key exchange. This unique value or counter used
>> for encrypting a single block cannot be the same for two different
>> connections ID’s, but it can be public. This means that it must be stored
>> in the packet header. And, as it turns out, random connection ID chosen by
>> a trusted source, can be used for such a unique value. But then it must be
>> used to encrypt and/or authenticate something else carrying the actual
>> routing information. So now you start to really need some extra payload.
>>
>>    the standard in a way that we can extend the connection ID in the future?
>>

---

From: "Lubashev, Igor" <[email-masked]>
Date: Fri, 12 Jan 2018 15:50:56 +0000

The point here is that if 128-bit is an option from V1, then all clients will support it, and the server can choose to always use 128-bit connection IDs.  The load balancer then can be sure that valid connection IDs (in packets featuring server connection ID) can only be 128-bit.  If V1 does not have 128-bit support, then the server must develop a less secure version of the connection ID to fit into 64 bits, and the load balancer must treat 64-bit connection IDs as acceptable.  Then, there is nothing to prevent an attacker from using 64-bit connection IDs, if that’s more convenient for them.

From: Ian Swett [mailto:[email-masked]]
Sent: Friday, January 12, 2018 9:35 AM
To: Lubashev, Igor <[email-masked]>
Cc: [email-masked]; [email-masked]
Subject: Re: Increasing QUIC connection ID size

On Fri, Jan 12, 2018 at 9:13 AM, Lubashev, Igor <[email-masked]<mailto:[email-masked]>> wrote:
If the 128-bit option is not in V1, then it will be required for the 128-bit option to be signaled in the packet's invariant section (like a bit in the 1st byte). Otherwise, the very load balancers this is designed for will not know whether the connection ID has 64- or 128-bit format. (It would need to support both, since there would be clients stuck at V1.)

-----Original Message-----
From: Ian Swett [[email-masked]<mailto:[email-masked]>]
Received: Friday, 12 Jan 2018, 8:59AM
To: Christian Huitema [[email-masked]<mailto:[email-masked]>]
CC: IETF QUIC WG [[email-masked]<mailto:[email-masked]>]
Subject: Re: Increasing QUIC connection ID size

Kind Regards,
Mikkel Fahnøe Jørgensen

  *   Igor

Hi everyone,

  -- Victor.

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Fri, 12 Jan 2018 11:57:31 -0500

It could also be fixed 62 bit connection identifier and 2 msg of the first
CID byte stores the additional length. The requirement is then that the
first 62 bits must have “enough entropy” and the remaining bits are
application or deployment specific. This will force routers to support
128-bits, but it will allow them to require it if so desired.

A router need not be concerned with the variable length aspect if the QUIC
invariant ensures that a packet length is at least long enough to read 128
bits from CID start. It can just assume the length it expects and then
validate as needed with auth tag or length, or just assume it is safe under
the conditions.

In all cases the QUIC endpoint MUST include the CID in the additional data
authentication to ensure routing data has not been tampered.

One could also take this a step further and shorten the first 64 bits, but
that is probably a rats nest: 16, 32, 64, 128 bits.

Kind Regards,
Mikkel Fahnøe Jørgensen

On 12 January 2018 at 16.51.19, Lubashev, Igor ([email-masked]) wrote:

The point here is that if 128-bit is an option from V1, then all clients
will support it, and the server can choose to always use 128-bit connection
IDs.  The load balancer then can be sure that valid connection IDs (in
packets featuring server connection ID) can only be 128-bit.  If V1 does
not have 128-bit support, then the server must develop a less secure
version of the connection ID to fit into 64 bits, and the load balancer
must treat 64-bit connection IDs as acceptable.  Then, there is nothing to
prevent an attacker from using 64-bit connection IDs, if that’s more
convenient for them.

*From:* Ian Swett [mailto:[email-masked]]
*Sent:* Friday, January 12, 2018 9:35 AM
*To:* Lubashev, Igor <[email-masked]>
*Cc:* [email-masked]; [email-masked]
*Subject:* Re: Increasing QUIC connection ID size

-----Original Message-----

So I am not sure that we actually need to change the length. And I am a bit
concerned by the incremental overhead if the connection ID suddenly becomes
very large.

Kind Regards,

Mikkel Fahnøe Jørgensen

   - Igor

Hi everyone,

  -- Victor.

---

From: Praveen Balasubramanian <[email-masked]>
Date: Fri, 12 Jan 2018 17:46:12 +0000

IMO we need to settle on a size for CID and make it an invariant in v1. Let’s also not introduce more encoding into one of the very few fields that is plaintext. We should aim for easy and fast adoption of QUIC by middleware. Requiring infrastructure components like load balancer or DDoS protection to decrypt is going to mean an order of magnitude reduction in performance and will be hard for deployment and shared keys are certainly not an option for IaaS scenario.

Particularly in relation to load balancer we have the following cases:

  1.  Connection remains on the same 4-tuple for its lifetime. Here today’s unmodified load balancers just work since they hash on 2- or 4-tuple (UDP/IP).
  2.  NAT rebinding. For this load balancer needs to hash based on CID and not 4-tuple. So there needs to be QUIC (version specific) awareness. Not a deal breaker and seems doable. But it does imply that server will always have to force inclusion of CID from client.
  3.  Connection migration. This is complicated because it seems to require the server to pick a new connection ID such that load balancer will pick the same server again. This coupling will be problematic in IaaS scenario where the load balancer may be owned by the cloud provider and the backend server terminating QUIC owned by a tenant. For this reason it seems to me that to support connection migration we need a standard load balancing scheme defined in a “deployment issues” section in the RFC. Am I missing something?

My preference for CID is still 64-bit since we have gone out of our way to save space in the headers using VLE but 128-bit is not a deal breaker. We should also leave the encoding of the CID to the server rather than specify any particular scheme but specifying what load balancers should do seems important for supporting connection migration.

Thanks

From: QUIC [mailto:[email-masked]] On Behalf Of Mikkel Fahnøe Jørgensen
Sent: Friday, January 12, 2018 8:58 AM
To: Lubashev, Igor <[email-masked]>; Ian Swett <[email-masked]>
Cc: [email-masked]; huitema <[email-masked]>
Subject: RE: Increasing QUIC connection ID size

It could also be fixed 62 bit connection identifier and 2 msg of the first CID byte stores the additional length. The requirement is then that the first 62 bits must have “enough entropy” and the remaining bits are application or deployment specific. This will force routers to support 128-bits, but it will allow them to require it if so desired.

A router need not be concerned with the variable length aspect if the QUIC invariant ensures that a packet length is at least long enough to read 128 bits from CID start. It can just assume the length it expects and then validate as needed with auth tag or length, or just assume it is safe under the conditions.

In all cases the QUIC endpoint MUST include the CID in the additional data authentication to ensure routing data has not been tampered.

One could also take this a step further and shorten the first 64 bits, but that is probably a rats nest: 16, 32, 64, 128 bits.

Kind Regards,
Mikkel Fahnøe Jørgensen

On 12 January 2018 at 16.51.19, Lubashev, Igor ([email-masked]<mailto:[email-masked]>) wrote:
The point here is that if 128-bit is an option from V1, then all clients will support it, and the server can choose to always use 128-bit connection IDs.  The load balancer then can be sure that valid connection IDs (in packets featuring server connection ID) can only be 128-bit.  If V1 does not have 128-bit support, then the server must develop a less secure version of the connection ID to fit into 64 bits, and the load balancer must treat 64-bit connection IDs as acceptable.  Then, there is nothing to prevent an attacker from using 64-bit connection IDs, if that’s more convenient for them.

From: Ian Swett [mailto:[email-masked]<mailto:[email-masked]>]
Sent: Friday, January 12, 2018 9:35 AM
To: Lubashev, Igor <[email-masked]<mailto:[email-masked]>>
Cc: [email-masked]<mailto:[email-masked]>; [email-masked]<mailto:[email-masked]>
Subject: Re: Increasing QUIC connection ID size

-----Original Message-----
From: Ian Swett [[email-masked]<mailto:[email-masked]>]
Received: Friday, 12 Jan 2018, 8:59AM
To: Christian Huitema [[email-masked]<mailto:[email-masked]>]
CC: IETF QUIC WG [[email-masked]<mailto:[email-masked]>]
Subject: Re: Increasing QUIC connection ID size

Kind Regards,
Mikkel Fahnøe Jørgensen

  *   Igor

Hi everyone,

  -- Victor.

---

From: Roberto Peon <[email-masked]>
Date: Fri, 12 Jan 2018 19:56:39 +0000

So long as:

  *   The server determines CIDs
  *   All parties agree on CID length
then various L4<->L7 strategies can be safely attempted, whether the strategy is:

  1.  Encrypting L7 address+salt as CID
  2.  Encoding of L7 IP address + HMAC into CID
  3.  Encoding of L7 MAC
Or something else.

If we agree on that, then we need a strategy to determine CID length.

I’d suggest, for simplicity in V1, just making it 128 bits. We can get fancy later and have multiple sizes, negotiated per connection, or frame, as desired.
Yes, it will be more overhead in the protocol, but it will unlock folks ability to experiment with L7<->L4 balancing in reasonable ways.
-=R

From: QUIC <[email-masked]> on behalf of Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Friday, January 12, 2018 at 8:58 AM
To: "Lubashev, Igor" <[email-masked]>, Ian Swett <[email-masked]>
Cc: "[email-masked]" <[email-masked]>, "[email-masked]" <[email-masked]>
Subject: RE: Increasing QUIC connection ID size

Kind Regards,
Mikkel Fahnøe Jørgensen

-----Original Message-----
From: Ian Swett [[email-masked]<mailto:[email-masked]>]
Received: Friday, 12 Jan 2018, 8:59AM
To: Christian Huitema [[email-masked]<mailto:[email-masked]>]
CC: IETF QUIC WG [[email-masked]<mailto:[email-masked]>]
Subject: Re: Increasing QUIC connection ID size

Kind Regards,
Mikkel Fahnøe Jørgensen

  *   Igor

Hi everyone,

  -- Victor.

---

From: Victor Vasiliev <[email-masked]>
Date: Fri, 12 Jan 2018 15:25:58 -0500

> callback could return anything, including an encrypted value.

Indeed.  Besides DOS concerns, there's also desire to preserve privacy
across connection migration.

> and then pass it back to the server. No encryption needed, but of course

This is in fact fairly painful from operational standpoint.

> bit concerned by the incremental overhead if the connection ID suddenly

Well, the general idea I was considering goes like this: assume F(x) is a
block cipher, and H(x) is a hash function the load balances uses to route
packets.  Then the LB computes F(CID), and checks if it's formatted as
<server-ID, client nonce, N zeroes>.  If it is well-formed, route based on
server-ID or H(server-ID), otherwise route based on H(CID).  This way, the
server-specified CIDs are tamper-proof in a sense that based on the usual
assumptions about block ciphers, you can't do better than rolling a random
CID and bypassing the check with probability 2^-N.  This of course,
requires large N, and if you're running a lot of servers, have a lot of
clients, it's very hard to fit everything into 64 bits.

Another idea is that you just always compute <server entropy, client
entropy> = F(CID), and just do H(server entropy).  This is also secure and
allows the server to create unlinkable "come back to me" connection IDs
while only sharing the key between the LB and the server, but assumes you
don't want to be clever with your server IDs and just hash on them.

Both of them suffer from the problem that F(x) has to be 64-bit, which
leads into an uncomfortably exciting territory of non-standard crypto
constructions (since all block ciphers made and standardized by IETF in
this century have 128-bit blocks as far as I know), where you end up
either using
older stuff like Blowfish or using FPE techniques -- both of which are
going to be slower than hardware AES.

I do very much agree with the overhead concern, though, this is a tough
question.

---

From: Jana Iyengar <[email-masked]>
Date: Fri, 12 Jan 2018 17:06:48 -0800

I'm not entirely convinced of the overhead concern. In the common HTTP
case, we expect server->client to not carry CIDs, so this is a NOP in the
commonly bandwidth-limited case.
I do think that this makes CID generation at servers substantially simpler
-- you can simply add 1 to the current CID to generate a new one, and
encryption makes it unlinkable to the previous one. This is a substantial
benefit.

On Fri, Jan 12, 2018 at 12:25 PM, Victor Vasiliev <[email-masked]>
wrote:

> either using older stuff like Blowfish or using FPE techniques -- both of
> which are going to be slower than hardware AES.
>

---

From: Christian Huitema <[email-masked]>
Date: Fri, 12 Jan 2018 16:12:31 -1000

On 1/12/2018 3:06 PM, Jana Iyengar wrote:
> case, we expect server->client to not carry CIDs, so this is a NOP in
> the commonly bandwidth-limited case.

Not just the transmission overhead. You are also increasing the memory
footprint of the connection context, which stores at least 2 CNX-ID, and
maybe more if we want to support migration.

But I agree that this is not the end of the world.

Also, following Victor's message, I was doing the maths on the size of
the ID. 64 bits allows for 24 bits of server ID, 32 bits of client
nonce, and 8 bits of zero -- for checking. 8 bits check will still let
0.4% of forged packets through, which is probably OK since the server
acts as a backstop. 24 bits would work for 16M servers, which should be
OK, but assumes that servers have a unique serial ID, which is not
necessarily OK. Then 32 bits look like they allow 4G connections per
server, but we start seeing collisions after 65K connections per server,
which seems not good. So, yes, 64 bits probably will be very tight if we
want the router to be stateless.

> I do think that this makes CID generation at servers substantially
> simpler -- you can simply add 1 to the current CID to generate a new
> one, and encryption makes it unlinkable to the previous one. This is a
> substantial benefit.

Yes, you can do that without relying on a secure random generator, and
thus without exposing more of the state of the crypto PRNG. Which is
nice. Another advantage, if the router can reliably map connection-ID to
servers, then we don't need to have the same reset secret for every server.

Just one request. If we do make a change, please go for a fixed size.

-- Christian Huitema

---

From: Marten Seemann <[email-masked]>
Date: Sat, 13 Jan 2018 04:53:24 +0000

I’m corcerned about the overhead. In the p2p use case, there’s no need for
encoding any routing information into the connection ID, and since every
node just handles a small number of connections, even 4 bytes would be more
than enough to distinguish between connections.
I can see the use case for 128 bit connection IDs, but in order to reduce
the overhead for other applications, we should either do some kind of
negotiation or a varlen encoding.

---

From: Martin Thomson <[email-masked]>
Date: Mon, 15 Jan 2018 20:41:45 +1100

Hi Victor,

I've opened an issue for this here:
https://github.com/quicwg/base-drafts/issues/1052

On Fri, Jan 12, 2018 at 10:16 AM, Victor Vasiliev <[email-masked]> wrote:
> I’ve looked into possibility of using a connection ID to encode the specific
> server details into it (to provide stability of the connection in case of
> load balancing changes, especially BGP flaps for anycast IPs), and have
> chatted about this with other people I knew were interested in this.  It
> seems like 64 bits might be too small for this purpose, and we might want to
> leave an opportunity to extend the connection ID size.
>
> Store some routing metadata in the connection ID.
> Have some entropy that allows distinguish users with identical routing
> metadata.
> Have a checksum to ensure the validity of routing information
> Encrypt the information above to prevent disclosing the route information
> and allow generating uncorrelatable connection IDs.
>
> There are two underlying issues here.  The first problem is that all of this
> does not fit well into 64 bits, and you have to seriously compromise on the
> strength of the checksum (which is bad especially if you want it to be a MAC
> rather than a checksum).  The second problem is that encrypting 64-bit
> values fast is actually fairly hard since the block ciphers easily available
> in hardware have 128-bit block size, and the performance requirements on
> load balancers are tighter than on servers.
>
> small.  There are two questions I believe the working group should answer at
> this point:
>
> Do we want to address this problem at this point in standardization process?
> If we don’t address this problem right now, how do we structure the standard
> in a way that we can extend the connection ID in the future?
>
> There are multiple ways to solve the problem of making connection ID larger.
> One is to just add extra bit to the “omit connection ID” field to allow
> 128-bit connection IDs.  Another approach is to allow connection ID size to
> be explicitly specified by the server, and then assume that the load
> balancer knows that size and no one else on the path needs to read it.
>
> (excluding load balancers and other boxes owned by the same entity as either
> client or server) need to know.  We could go for both “middleboxes should be
> always able to read the entire ID” and “middleboxes should not read
> connection IDs at all options”, but I think there’s also a room for more
> flexible formulations like “middleboxes always get first 64 bits and they
> have useful entropy to distinguish connections”.
>
>   -- Victor.

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Mon, 15 Jan 2018 05:24:00 -0500

This is true. In some cases you might want a long routing ID in p2p, but
messages are routed inside established connections where each node has only
a few “physical” connections and each message has a large number of
possible targets. Having both a connection ID and a long internal routing
ID, and the auth tag would be a lot to carry for short status messages.

I earlier suggested a possible varlen extension to 64 bits. An alternative
is to have the client always connect with 128-bits and have the server
respond with a connection id of chosen size.

Having a 128-bit client ID that only exists during handshake ought to be
always enough. It could also be used for fast rejection of invalid
connection attempts by placing some hashed knowledge in the ID, which is
deployment specific. Or it could provide priority access during a DoS
scenario.

The server can choose an established connection ID length that is agreeable
with the infrastructure, which could be down to a single byte - which still
allows for single port client usage with little overhead. This is
especially useful on micro-controller deployments where a UDP header might
be skipped. Routers can assume a fixed size connection ID because the
servers will use something the routers can understand.

I am a bit concerned about connection migration because a new path might
need a different kind of connection ID both in size and in encoding. Simply
using the next NEW_CONNECTION_ID might not be optimal because the routers
on the new path might be different.

---

From: Victor Vasiliev <[email-masked]>
Date: Tue, 16 Jan 2018 01:02:38 -0500

> negotiation or a varlen encoding.

We already vary the CID length in header (0 bits vs 64 bits), so if we
decide to make a 64/128 switch, I would consider that to be more of just
adding another length option.