Subject: Removing packet number gaps

From: Martin Thomson <[email-masked]>
Date: Tue, 2 Jan 2018 12:57:10 +1100

There are number of problems with packet number gaps that I think we
need to address.  Most are minor.  For instance, the initial packet
number is not close to zero, which inflates the size of ACK frames
from the very beginning of a connection.

However, Christian just identified one that I think makes this more
important to address: when using a new connection ID, the gap is the
same size on both client and server.  This makes flows linkable.  The
gaps between the last packet on the old flow and the first packet on
the new flow can be calculated in both directions.  Flows can be
linked by finding flows where client-to-server packets have the same
(or very close) gaps as server-to-client packets.

With a few small tweaks to the current design, I think that we get a
much better solution.  Here is what I propose:

Firstly, packet numbers start at zero and always increase
monotonically, with no gaps.  A side benefit of this is that the first
ACK frame will have a small encoding for largest_acknowledged (1 octet
rather than 8 in most cases).

Packet numbers are never encoded directly onto the wire, they are
XORed with a masking value.  This value will change for different
packet protection keys, and for different connection IDs.  Client and
server will use different values so that gaps are hard to detect.

Thus, we will have a third key derivation:

   key = QHKDF-Expand(S, "key", key_length)
   iv  = QHKDF-Expand(S, "iv", iv_length)
   pnmask = QHKDF-Expand(S, "pnmask", 4)

To make this work seamlessly, I'm proposing a tweak to QHKDF-Expand
that includes the connection ID.  For that, the "Context" field that
we currently do not use seems like a good choice.

This will mean changes to the other uses of QHKDF-Expand:

* the handshake secret can be changed to be a fixed rather than a
derived value, so that we don't need to use the function (connection
ID will be added during expansion into the separate keys)

* during a key update, a zero-length or fixed connection ID will need
to be used so that there is no confusion about which connection ID was
in use at the time the update was made (editorially, I'm not certain
how to manage this one, I might just go back to using
HKDF-Expand-Label directly for that)

Finally, we need to be very clear that even if the connection ID is
omitted, those packets still use the implied connection ID in key
derivation.  We will probably want to recommend that endpoints include
a connection ID if they intend to support NEW_CONNECTION_ID or any of
the related functions, at least around the time when a connection ID
change is in place or the recipient of their packets could have
difficulty picking the right keys.  This is already a problem of
course, but this change would make it worse.

---

From: Christian Huitema <[email-masked]>
Date: Mon, 1 Jan 2018 18:13:03 -0800

For clarification: are you proposing to make the encryption key and IV dependent on the connection ID, or just the packet number mask?

Also, are you proposing applying the mask before encoding the packet header on 1, 2, 4 or 8 bytes, or after that?

-- Christian Huitema 

> On Jan 1, 2018, at 5:57 PM, Martin Thomson <[email-masked]> wrote:
>

---

From: "Lubashev, Igor" <[email-masked]>
Date: Tue, 2 Jan 2018 02:15:22 +0000

Could we use PLUS instead of XOR?  My understanding is that there is little cryptographic difference between XOR and PLUS, and it is nicer to have consecutive packet numbers on the wire...

-----Original Message-----
From: Martin Thomson [mailto:[email-masked]] 
Sent: Monday, January 01, 2018 8:57 PM
To: QUIC WG <[email-masked]>
Subject: Removing packet number gaps

There are number of problems with packet number gaps that I think we need to address.  Most are minor.  For instance, the initial packet number is not close to zero, which inflates the size of ACK frames from the very beginning of a connection.

However, Christian just identified one that I think makes this more important to address: when using a new connection ID, the gap is the same size on both client and server.  This makes flows linkable.  The gaps between the last packet on the old flow and the first packet on the new flow can be calculated in both directions.  Flows can be linked by finding flows where client-to-server packets have the same (or very close) gaps as server-to-client packets.

With a few small tweaks to the current design, I think that we get a much better solution.  Here is what I propose:

Firstly, packet numbers start at zero and always increase monotonically, with no gaps.  A side benefit of this is that the first ACK frame will have a small encoding for largest_acknowledged (1 octet rather than 8 in most cases).

Packet numbers are never encoded directly onto the wire, they are XORed with a masking value.  This value will change for different packet protection keys, and for different connection IDs.  Client and server will use different values so that gaps are hard to detect.

To make this work seamlessly, I'm proposing a tweak to QHKDF-Expand that includes the connection ID.  For that, the "Context" field that we currently do not use seems like a good choice.

* the handshake secret can be changed to be a fixed rather than a derived value, so that we don't need to use the function (connection ID will be added during expansion into the separate keys)

* during a key update, a zero-length or fixed connection ID will need to be used so that there is no confusion about which connection ID was in use at the time the update was made (editorially, I'm not certain how to manage this one, I might just go back to using HKDF-Expand-Label directly for that)

Finally, we need to be very clear that even if the connection ID is omitted, those packets still use the implied connection ID in key derivation.  We will probably want to recommend that endpoints include a connection ID if they intend to support NEW_CONNECTION_ID or any of the related functions, at least around the time when a connection ID change is in place or the recipient of their packets could have difficulty picking the right keys.  This is already a problem of course, but this change would make it worse.

---

From: Martin Thomson <[email-masked]>
Date: Tue, 2 Jan 2018 14:38:59 +1100

> For clarification: are you proposing to make the encryption key and IV dependent on the connection ID, or just the packet number mask?

Both.  As you argue in your draft, this makes some things easier, and
it fits more naturally if the key, IV, and mask all have similar
derivations.

> Also, are you proposing applying the mask before encoding the packet header on 1, 2, 4 or 8 bytes, or after that?

After.  We'd have to be careful to get the bit alignment right, of course.

---

From: Martin Thomson <[email-masked]>
Date: Tue, 2 Jan 2018 14:39:58 +1100

> Could we use PLUS instead of XOR?  My understanding is that there is little cryptographic difference between XOR and PLUS, and it is nicer to have consecutive packet numbers on the wire...

It depends on what your goals are, but sure.  XOR won't make it
impossible to recover numbers, but it would make it annoying and
that's petty.  Addition modulo the field size works for me.

---

From: Christian Huitema <[email-masked]>
Date: Mon, 1 Jan 2018 20:11:04 -0800

> On Jan 1, 2018, at 7:38 PM, Martin Thomson <[email-masked]> wrote:
> 

Yes, it seems natural. But there is at least one downside: both peers need the master secret available when creating or receiving a new connection ID. In the current design, the master secret can be erased once encryption keys have been initialized.

OTOH, with that design we can get rid of the key phase mechanism. To refresh the key, just start using a new connection ID.

> After.  We'd have to be careful to get the bit alignment right, of course.

You don't actually need to be careful with the XOR solution. Just XOR four bytes after completing the payload encryption, and XOR then again before decrypting the payload.

By the way, can we get 5 bytes instead of just 4? With the 5th byte, we could grease the lower bits of the first byte, greasing the packet type.

-- Christian Huitema

---

From: Martin Thomson <[email-masked]>
Date: Tue, 2 Jan 2018 15:40:31 +1100

> Yes, it seems natural. But there is at least one downside: both peers need the master secret available when creating or receiving a new connection ID. In the current design, the master secret can b…

You need the packet protection secret around if you ever want to do a
key update.

> OTOH, with that design we can get rid of the key phase mechanism. To refresh the key, just start using a new connection ID.

True, but that would remove the post-compromise security that we get
from the current design.

> You don't actually need to be careful with the XOR solution. Just XOR four bytes after completing the payload encryption, and XOR then again before decrypting the payload.

You have to get the right part of the 4 (or 5) bytes or it will fail.
That means a htonl() call, but that's easy.  Though I note that if we
do as Igor suggests, then we get that number just once per connection
ID (with  a call to ntohl() at that point) and add before encoding and
you don't have to worry about the truncation bit.

> By the way, can we get 5 bytes instead of just 4? With the 5th byte, we could grease the lower bits of the first byte, greasing the packet type.

Sure.  I didn't want to burden everyone with this, but it's an obvious
extension.

---

From: "Roni Even (A)" <[email-masked]>
Date: Tue, 2 Jan 2018 06:12:17 +0000

+1
Roni

---

From: Victor Vasiliev <[email-masked]>
Date: Tue, 2 Jan 2018 09:43:52 -0500

> (or very close) gaps as server-to-client packets.

Why not just have different gaps for the client and the server?

---

From: Martin Thomson <[email-masked]>
Date: Wed, 3 Jan 2018 10:03:15 +1100

> Why not just have different gaps for the client and the server?

That fixes only that issue, and there have been several other issues
identified.  They are each on their own relatively minor, but together
I'd say that a more principled change is justified.

---

From: Marcus Ihlar <[email-masked]>
Date: Wed, 3 Jan 2018 10:37:15 +0000

+1
Consecutive packet numbers are important for spin bit observers.

/Marcus
-----Original Message-----
From: QUIC [mailto:[email-masked]] On Behalf Of Roni Even (A)
Sent: den 2 januari 2018 07:12
To: Lubashev, Igor <[email-masked]>; Martin Thomson <[email-masked]>; QUIC WG <[email-masked]>
Subject: RE: Removing packet number gaps

+1
Roni

---

From: Martin Thomson <[email-masked]>
Date: Tue, 9 Jan 2018 17:36:21 +1100

PR here: https://github.com/quicwg/base-drafts/pull/1043