Subject: Read-out on offline connection ID discussion

From: Eric Rescorla <[email-masked]>
Date: Wed, 24 Jan 2018 14:36:42 -0800

Hi folks,

We didn't really reach a conclusion, but here's, I think what there
was at least some support for:

- The long header has a variable length connection ID which has an
  explicit length field on the wire, with a max length (strawman: 32
  bytes). The exact wire encoding to be designed by the editor.
  Similarly, NEW_CONNECTION_ID would have a variable length
  encoding.

- The short header has a variable length connection ID which has
  an implicit length (i.e., it cannot be decoded unambiguously
  by an observer who is not part of the connection). However,
  the CID may be self-describing, so that the server may include
  a length field if it so chooses.

There was rough consensus on the second point, but some disagreement
about the first point. The major alternative proposal was to have
a fixed-length CID field in the long header and NEW_CONNECTION_ID
and then truncate it to an amount carried in transport_parameters.
This would have the benefit that the length of the CID would be
throughout the connection whereas if we wanted that rule for the
other design we would need a rule.

One thing that makes this second approach unattractive is that we want
the server to be able to use a 16 byte connection ID (thus allowing it
to be AES-encrypted) but it also needs to be able to include
meta-data, such as a key-id for rotation or potentially a length. This
tells us that you need to have a maximum connection ID larger than 16
bytes, and having a fixed 17-20 byte CID seems odd.

-Ekr

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Wed, 24 Jan 2018 17:51:03 -0500

I don’t understand this requirement for the CID to be 16 bytes in order to
be encrypted.
If you have a unique key you can encrypt 0, truncate and xor with the CID.
If you don’t have a unique key, you can encrypt a unique counter value and
do the same, or derive a unique key.

Kind Regards,
Mikkel Fahnøe Jørgensen

On 24 January 2018 at 23.37.30, Eric Rescorla ([email-masked]) wrote:

Hi folks,

-Ekr

---

From: Eric Rescorla <[email-masked]>
Date: Wed, 24 Jan 2018 15:16:13 -0800

On Wed, Jan 24, 2018 at 2:51 PM, Mikkel Fahnøe Jørgensen <[email-masked]
> wrote:

> do the same, or derive a unique key.

I don't believe what you are describing works correctly, but I'm not sure I
understand your proposal. Can you please flesh out precisely what you have
in mind? In particular, who is "you", who has the key, etc.?

-Ekr

---

From: Christian Huitema <[email-masked]>
Date: Wed, 24 Jan 2018 13:25:28 -1000

I get the argument for 16+n, var length, etc. But I am concerned that
the specific length, and maybe the clear text prefixes of a CID, can be
used for fingerprinting, and then provide linkability.

-- Christian Huitema

---

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

> But I am concerned that the specific length, and maybe the clear text prefixes of a CID, can be used for fingerprinting, and then provide linkability.

I would expect non-trivial things to CIDs done by servers in client-server scenarios, so you are fingerprinting the server, not the client.  Ae you concerned with a p2p case?  

- Igor

-----Original Message-----
From: Christian Huitema [mailto:[email-masked]] 
Sent: Wednesday, January 24, 2018 6:25 PM
To: Eric Rescorla <[email-masked]>; Mikkel Fahnøe Jørgensen <[email-masked]>
Cc: IETF QUIC WG <[email-masked]>
Subject: Re: Read-out on offline connection ID discussion

I get the argument for 16+n, var length, etc. But I am concerned that the specific length, and maybe the clear text prefixes of a CID, can be used for fingerprinting, and then provide linkability.

-- Christian Huitema

---

From: Roberto Peon <[email-masked]>
Date: Wed, 24 Jan 2018 23:51:28 +0000

Imagine allowing the server to send multiple CIDs, and provide the server with some revocation mechanism (TTL or explicit, or what-have-you).

A client may use any of these CIDs until they are revoked.

Thus, a server which cares to prevent ossification could provide multiple CIDs, and the client could switch between them on a per-packet basis.

-=R

________________________________
From: QUIC <[email-masked]> on behalf of Lubashev, Igor <[email-masked]>
Sent: Wednesday, January 24, 2018 3:46:16 PM
To: Christian Huitema; Eric Rescorla; Mikkel Fahnøe Jørgensen
Cc: IETF QUIC WG
Subject: RE: Read-out on offline connection ID discussion

- Igor

-----Original Message-----
From: Christian Huitema [mailto:[email-masked]]
Sent: Wednesday, January 24, 2018 6:25 PM
To: Eric Rescorla <[email-masked]>; Mikkel Fahnøe Jørgensen <[email-masked]>
Cc: IETF QUIC WG <[email-masked]>
Subject: Re: Read-out on offline connection ID discussion

-- Christian Huitema

---

From: "Lubashev, Igor" <[email-masked]>
Date: Thu, 25 Jan 2018 00:12:28 +0000

If you are worried that the client's privacy can be compromised by CIDs linkable to the same server, I'd be worried that server's IP will give this away even more reliably.

  *   Igor

From: Roberto Peon [mailto:[email-masked]]
Sent: Wednesday, January 24, 2018 6:51 PM
To: Lubashev, Igor <[email-masked]>; Christian Huitema <[email-masked]>; Eric Rescorla <[email-masked]>; Mikkel Fahnøe Jørgensen <[email-masked]>
Cc: IETF QUIC WG <[email-masked]>
Subject: Re: Read-out on offline connection ID discussion

-=R

From: QUIC <[email-masked]<mailto:[email-masked]>> on behalf of Lubashev, Igor <[email-masked]<mailto:[email-masked]>>

- Igor

-----Original Message-----
From: Christian Huitema [mailto:[email-masked]]
Sent: Wednesday, January 24, 2018 6:25 PM
To: Eric Rescorla <[email-masked]<mailto:[email-masked]>>; Mikkel Fahnøe Jørgensen <[email-masked]<mailto:[email-masked]>>
Cc: IETF QUIC WG <[email-masked]<mailto:[email-masked]>>
Subject: Re: Read-out on offline connection ID discussion

-- Christian Huitema

---

From: Roberto Peon <[email-masked]>
Date: Thu, 25 Jan 2018 00:20:31 +0000

I suspect you mean the 5-tuple, and not just the server IP, as that leaks more information.

I agree that (the 5-tuple and/or server address) gives away information.
I suspect it makes it somewhat more difficult. Once multipath and/or 5-tuple migration is available, the combinations of 5-tuple plus CID changes does provide some substantial improvements.

Regardless, it is certainly helpful to prevent ossification, which is what I was commenting on.
-=R

________________________________
From: Lubashev, Igor <[email-masked]>
Sent: Wednesday, January 24, 2018 4:12:28 PM
To: Roberto Peon; Christian Huitema; Eric Rescorla; Mikkel Fahnøe Jørgensen
Cc: IETF QUIC WG
Subject: RE: Read-out on offline connection ID discussion

If you are worried that the client’s privacy can be compromised by CIDs linkable to the same server, I’d be worried that server’s IP will give this away even more reliably.

  *   Igor

-=R

- Igor

-----Original Message-----
From: Christian Huitema [mailto:[email-masked]]
Sent: Wednesday, January 24, 2018 6:25 PM
To: Eric Rescorla <[email-masked]<mailto:[email-masked]>>; Mikkel Fahnøe Jørgensen <[email-masked]<mailto:[email-masked]>>
Cc: IETF QUIC WG <[email-masked]<mailto:[email-masked]>>
Subject: Re: Read-out on offline connection ID discussion

-- Christian Huitema

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Thu, 25 Jan 2018 00:45:07 -0800

On 25 January 2018 at 00.16.55, Eric Rescorla ([email-masked]) wrote:

I’m merely stating that if you want to encrypt with AES and you do not care
about authentication, then AES works fine with shorter inputs than 16
bytes. You may still have to provide an initialisation vector so the +n
still holds. The last block of AES-GCM is not a full block and works as i
described - see sect. 2.3 and figure 1 in link to GCM paper. If the last
block is the only block, you encrypt less than 16 bytes without any magic.

There are many reasons you might want to use 16 bytes, or you might want to
add authentication, but it is not AES itself that imposes those constraints
as already argued. My point is that if you need 16 bytes, please state why,
instead of blaming it on AES.

As to a possible scheme:

Assume a server cluster wants to encode routing data by selecting one out
of 256 possible routes and a 8 bit unique id for each route. This can be
done with 16 bits. (Not saying this is a good idea). Or, let’s make it
simple for a start: just have 1 routing bit R to choose between two servers
and 1 IV bit to identify the connection, and one phase bit P. The objective
is to make it unpredictable which server is hit. The encryption of the two
bits happen by encrypting the IV bit with a cluster key that all routers
are aware of. The phase bit is not needed but avoids guessing which router
key is active since it rotates every hour derived from a master key. The
encrypted CID is just 1 bit flipped randomly based on XOR’ing with
encrypting 1 or 0, depending the IV is 1 or 0. key = derive(master, R), P =
not P if key changed since last derivation. The encrypted CID ECID =
<AES(key, IV) XOR R, IV, P>.

We can readily extend the above to as many R bits as needed. The IV must be
unique but if we only care about making it hard to force a route rather
than protecting information, it is less critical, assuming we hide the
master key behind strong derivation.

The problem is that an attacker can easily flip the first bit in the ECID.
We can make this harder by having more than R bits than valid routes and
having more IV bits chosen at random. The R bits now either map to a valid
route or not. It becomes harder to guess a valid route.

We can make this harder by adding an auth tag - say of length 16 bits.
AES-GCM is not suited for short tags, but there CMACs that can do this I
believe (two times AES + padding and truncation to desired length, from
memory). However, if it is sufficiently hard to guess a route, and it is
easy to decide if a route is valid or not, it may not be necessary with an
auth tag.

In addition we want to identify the connection uniquely with respect to the
chosen server route so we add U bits to make the connection id unique.
These do not have to be encrypted, but they might as well be thrown in.

http://www.mindspring.com/~dmcgrew/gcm-nist-6.pdf

AES-GCM goes horribly wrong if the same encrypted counter value is used
twice - but we may not have a problem with horribly wrong in our use case,
which also only uses the CTR mode part.

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Thu, 25 Jan 2018 01:07:35 -0800

Another thing is that such a scheme is somewhat broken because an off-path
attacker can connect to a host as any other client and retrieve a
connection ID. Then it has sufficient information about the routing table
for the next our to flood a specific route.

It’s not really possible to avoid unless each router has more information
than a key rotating every hour.

The targeted server can protect itself by not accepting any encrypted ECID
in a new handshake and drop packets via ordinary auth failure on other
packets.

To handle stateless retry, the encryption ECID for retry must be different,
so we name it RECID. The targeted server will generate ECID for client
initiated communication with a random client CID, or accept RECID based
handshakes, but will not accept ECID for handshake because that is a DoS
waiting to happen.

Kind Regards,
Mikkel Fahnøe Jørgensen

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

As to a possible scheme:

---

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

I’m not even sure that will work because the RECID could also be replayed.

Kind Regards,
Mikkel Fahnøe Jørgensen

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

Kind Regards,
Mikkel Fahnøe Jørgensen

As to a possible scheme:

---

From: Christian Huitema <[email-masked]>
Date: Wed, 24 Jan 2018 23:11:28 -1000

> On Jan 24, 2018, at 10:45 PM, Mikkel Fahnøe Jørgensen <[email-masked]> wrote:
> 
>> I don’t understand this requirement for the CID to be 16 bytes in order to be encrypted.
>> If you don’t have a unique key, you can encrypt a unique counter value and do the same, or derive a unique key.
>> 
>> I don't believe what you are describing works correctly, but I'm not sure I understand your proposal. Can you please flesh out precisely what you have in mind? In particular, who is "you", who has the key, etc.?
> 
> I’m merely stating that if you want to encrypt with AES and you do not care about authentication, then AES works fine with shorter inputs than 16 bytes. You may still have to provide an initialisation vector so the +n still holds. The last block of AES-GCM is not a full block and works as i described - see sect. 2.3 and figure 1 in link to GCM paper. If the last block is the only block, you encrypt less than 16 bytes without any magic.
> 
AES GCM is a stream cipher. It is OK in AEAD mode, but using that without authentication opens the way to all the known attacks against stream ciphers. If we don't have room for authentication, then ECB mode seems much preferable.

--Christian Huitema

---

From: "Brian Trammell (IETF)" <[email-masked]>
Date: Thu, 25 Jan 2018 10:49:02 +0100

> On 24 Jan 2018, at 23:36, Eric Rescorla <[email-masked]> wrote:
> 
> Hi folks,
> 

This seems like a perfectly reasonable starting point.

>   a length field if it so chooses.

A question about the details here:

We put the CID (if present) up front in the short header so that it's easy for load balancers to find; the packet number in -08 (which is necessary to sequence and decrypt packets) is similarly easy for the endpoint to find -- CID is fixed length and either present or not.

If the CID is varlen and its length is implicit in the CID itself, then the receiver needs to decode the CID in order to find the offset to the packet number so that it can decrypt the packet number in order to sequence the packet and decrypt the rest of it. This implies the receiver always needs to know how to decode enough of the CID to skip it (which can be trivially done in a transport parameter, but still).

I presume the encrypted representation of the packet number on the wire will be fixed-length, so we can fix this by moving the CID back behind the packet number, but I'm not sure where we are in the tradeoff space between forcing load balancers to skip N bytes before making a routing decision and forcing packet receivers on both sides to always do more work to parse the packet.

Cheers,

Brian

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Thu, 25 Jan 2018 03:43:19 -0800

But I now think I understand the concerns with AES block size.
You want to spread a few bits over multiple bits, like with a hash function
except reversible.

I stated below that you could add more than the necessary R routing bits.
But if you don’t don’t mix those bits it is easy to flip bits. If you take
the R routing bits as input to AES instead of a counter, you achieve the
desired mixing, but then it is correct that you need 16 bytes to recover
the information.

You could still use the XOR method and use a shorter authentication tag
instead - this would not make the routing bit locations unidentifiable, but
it would make the unmodifiable with a certain probability.

Kind Regards,
Mikkel Fahnøe Jørgensen

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

Kind Regards,
Mikkel Fahnøe Jørgensen

Kind Regards,
Mikkel Fahnøe Jørgensen

As to a possible scheme: