Subject: [quicwg/base-drafts] First pass at 7, 14, and 30-bit varint packet numbers (#1334)

From: Brian Trammell <[email-masked]>
Date: Thu, 03 May 2018 05:17:06 -0700

Initial attempt at adding variable-length-ness to encrypted packet numbers, addressing #989. The encoding here is header-type-dependent, and inspired-by-but-not-compatible-with varint encoding.

This also assigns the two bits recovered from the short header Type field to experimentation.
You can view, comment on, or merge this pull request online at:

  https://github.com/quicwg/base-drafts/pull/1334

-- Commit Summary --

  * First pass at varint packet numbers

-- File Changes --

    M draft-ietf-quic-tls.md (7)
    M draft-ietf-quic-transport.md (58)

-- Patch Links --

https://github.com/quicwg/base-drafts/pull/1334.patch
https://github.com/quicwg/base-drafts/pull/1334.diff

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1334

---

From: ianswett <[email-masked]>
Date: Thu, 03 May 2018 09:52:51 -0700

ianswett commented on this pull request.

I think this largely looks good, but I want to be sure we're ok with expanding the experimentation space before we land that part.

> @@ -439,12 +439,8 @@ Google QUIC Demultipexing Bit:
 
 Reserved:
 
-: The sixth bit (0x4) of octet 0 is reserved for experimentation.
-
-Short Packet Type:
-
-: The remaining 2 bits of octet 0 include one of 4 packet types.
-  {{short-packet-types}} lists the types that are defined for short packets.
+: The sixth, seventh, and eighth bits (0x7) of octet 0 are reserved for
+experimentation.

I don't personally object to this, but does this have consensus in the WG?

> +In the long packet header, the least significant 32 bits are used. In the
+short packet header, the number of significant bits are encoded in the most
+significant two bits of the first octet of the encoded packet number:
+
+| First octet pattern | Encoded Length | Bits Present |
+|:--------------------|:---------------|:-------------|
+| 0b0xxxxxxx          | 1 octet        | 7            |
+| 0b10xxxxxx          | 2              | 14           |
+| 0b11xxxxxx          | 4              | 30           |
+
+Note that these encodings are similar to those in {{integer-encoding}}, but
+use different values.
+
+The encoded packet number is protected as described in Section 5.6 {{QUIC-TLS}}.
+Protection of the packet number is removed prior to recovering the full packet
+number.The full packet number is reconstructed at the receiver based on the

Add a space between the ".' and "The"

> +short packet header, the number of significant bits are encoded in the most
+significant two bits of the first octet of the encoded packet number:
+
+| First octet pattern | Encoded Length | Bits Present |
+|:--------------------|:---------------|:-------------|
+| 0b0xxxxxxx          | 1 octet        | 7            |
+| 0b10xxxxxx          | 2              | 14           |
+| 0b11xxxxxx          | 4              | 30           |
+
+Note that these encodings are similar to those in {{integer-encoding}}, but
+use different values.
+
+The encoded packet number is protected as described in Section 5.6 {{QUIC-TLS}}.
+Protection of the packet number is removed prior to recovering the full packet
+number.The full packet number is reconstructed at the receiver based on the
+value of the most significant two bits in the first octet (to determine the

This sentence is a bit confusing, I think the PN is decoded based on the number of significant bits and the number those significant bits encode.  Saying it's based on the value of the first two bits more of a wire format detail I don't think needs to be in this sentence.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1334#pullrequestreview-117342740

---

From: Brian Trammell <[email-masked]>
Date: Thu, 03 May 2018 10:28:23 -0700

britram commented on this pull request.

 Reserved:

>From @mnot's message "Spin Bit -- A Path Forward":
> - The transport draft editors will assure that at least three bits are available for experimentation in the next draft.

I don't think there's consensus yet that the Type field will go away, but the design direction of the protocol so far does not seem to point toward additional path-visible optional parts or forms for the short header, meaning these bits become useless once they're subsumed into the packet number encoding. This seemed like the lower-energy way to get to three bits than working around STUN and GUIC multiplexing.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1334#discussion_r185878789

---

From: Brian Trammell <[email-masked]>
Date: Thu, 03 May 2018 10:29:13 -0700

yep, this is better.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1334#discussion_r185879074

---

From: ianswett <[email-masked]>
Date: Thu, 03 May 2018 20:08:37 +0000 (UTC)

Reserved:

SGTM

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1334#discussion_r185921751

---

From: Martin Thomson <[email-masked]>
Date: Thu, 03 May 2018 19:02:08 -0700

martinthomson commented on this pull request.

Thanks for writing this up Brian.  90% of the way there already.

> @@ -960,6 +960,13 @@ To ensure that this process does not sample the packet number, packet number
 protection algorithms MUST NOT sample more ciphertext than the minimum
 expansion of the corresponding AEAD.
 
+Packet number protection is applied to the packet number encoded as described
+in Section 4.8 of {{QUIC-TRANSPORT}}. Since the length of the packet number is
+stored in the encoded packet number, it is necessary to decrypt the maximum
+length (4 octets) when removing packet number protection. The final 2 or 3

It isn't *strictly* necessary to decrypt 4 octets: you can decrypt one octet at a time.

One thing that concerns me here is that you are recommending a strategy that includes decrypting the IV; I don't know how to exploit that and it seems entirely possible that it can't be, but I would avoid recommending this implementation strategy (even if I have in the past; I'm not sure that I want that in an RFC).

Instead, I would observe that the packet number might need to progressively decrypted.

 Reserved:

I think that this is a fine thing.  Removing type is good; reserving is good.

I would more simply state this as "these bits are reserved".  We might ultimately decide that the spin bit experiment is an experiment no longer.  At that point we might assign them to the spin bit(s) or find an entirely different use for those bits.

> @@ -786,15 +775,30 @@ reaches 2^62 - 1, the sender MUST close the connection without sending a
 CONNECTION_CLOSE frame or any further packets; a server MAY send a Stateless
 Reset ({{stateless-reset}}) in response to further packets that it receives.
 
-For the packet header, the number of bits required to represent the packet
-number are reduced by including only the least significant bits of the packet
-number.
-
-The encoded packet number is protected as described in {{QUIC-TLS}}. Protection
-of the packet number is removed prior to recovering the full packet number. The
-full packet number is reconstructed at the receiver based on the largest packet
-number received on a successfully authenticated packet. Recovering the full
-packet number is necessary to successfully remove packet protection.
+In the QUIC long and short packet headers, the number of bits required to
+represent the packet number are reduced by including only the least
+significant bits of the packet number.
+
+In the long packet header, the least significant 32 bits are used. In the

"In the long packet header, the least significant 32 bits of the packet are encoded into the Packet Number field."

> -For the packet header, the number of bits required to represent the packet
-number are reduced by including only the least significant bits of the packet
-number.
-
-The encoded packet number is protected as described in {{QUIC-TLS}}. Protection
-of the packet number is removed prior to recovering the full packet number. The
-full packet number is reconstructed at the receiver based on the largest packet
-number received on a successfully authenticated packet. Recovering the full
-packet number is necessary to successfully remove packet protection.
+In the QUIC long and short packet headers, the number of bits required to
+represent the packet number are reduced by including only the least
+significant bits of the packet number.
+
+In the long packet header, the least significant 32 bits are used. In the
+short packet header, the number of significant bits are encoded in the most
+significant two bits of the first octet of the encoded packet number:

`<p>`
"In the short packet header, a variable number of significant bits are encoded.  One or two of the most significant bits of the first octet determine how many bits of the packet number are provided, as shown in {{pn-encodings}}."

> -number received on a successfully authenticated packet. Recovering the full
-packet number is necessary to successfully remove packet protection.
+In the QUIC long and short packet headers, the number of bits required to
+represent the packet number are reduced by including only the least
+significant bits of the packet number.
+
+In the long packet header, the least significant 32 bits are used. In the
+short packet header, the number of significant bits are encoded in the most
+significant two bits of the first octet of the encoded packet number:
+
+| First octet pattern | Encoded Length | Bits Present |
+|:--------------------|:---------------|:-------------|
+| 0b0xxxxxxx          | 1 octet        | 7            |
+| 0b10xxxxxx          | 2              | 14           |
+| 0b11xxxxxx          | 4              | 30           |
+

{: #pn-encodings title="Short Header Packet Number Encodings"}

I like Ian's suggestion too.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1334#pullrequestreview-117479433

---

From: MikkelFJ <[email-masked]>
Date: Thu, 03 May 2018 22:09:09 -0700

> Instead, I would observe that the packet number might need to progressively decrypted.

I'm not really sure why overdecrypting as opposed to one at a time would make things any worse if the output is not visible to any observer. If anything, constant time operations are much preferable as it avoids timing attacks.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1334#issuecomment-386506840

---

From: Brian Trammell <[email-masked]>
Date: Fri, 04 May 2018 06:10:12 -0700

>I'm not really sure why overdecrypting as opposed to one at a time would make things any worse if the output is not visible to any observer

ISTM either choice is an implementation detail, and can be left out here. Indeed, while always decrypting four octets is an easy way to go constant-time, it's not the only one. OTOH, the probable length of the encoded PN can already be deduced by anyone along the path with even the dimmest idea of the window size: if someone's willing to perform timing attacks to recover information they should already have, more power to them.

I'll roll all this up into another commit later today.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1334#issuecomment-386596385

---

From: Brian Trammell <[email-masked]>
Date: Fri, 04 May 2018 06:14:28 -0700

Reserved:

I'd still lean toward "reserved for experimentation", with the understanding that this language is necessarily transient and will collapse one way or another before V1 final.

One, because that's the current state and the outcome of the discussion in London; two, because given the WG's love of grease to date, simply stating "this is reserved" without discussion of how it's greased would seem odd.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1334#discussion_r186077777

---

From: Brian Trammell <[email-masked]>
Date: Fri, 04 May 2018 19:21:13 +0000 (UTC)

@britram pushed 1 commit.

fae6da8  tweaks, thanks Martin and Ian

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1334/files/b3bb4638d5678485cc25800d647b9387f3b162ec..fae6da88e698925e5d19300f51e40167303c4497

---

From: Brian Trammell <[email-masked]>
Date: Sat, 05 May 2018 19:26:13 +0000 (UTC)

50f0501  long headers too

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1334/files/fae6da88e698925e5d19300f51e40167303c4497..50f05017ff449405fe14305a510e8b554a86668d

---

From: Brian Trammell <[email-masked]>
Date: Sat, 05 May 2018 19:27:08 +0000 (UTC)

most recent commit uses variable encoding on long headers, too, per discussion in #989

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1334#issuecomment-386829055

---

From: ianswett <[email-masked]>
Date: Sat, 05 May 2018 19:34:47 +0000 (UTC)

ianswett approved this pull request.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1334#pullrequestreview-117823042

---

From: Martin Thomson <[email-masked]>
Date: Mon, 07 May 2018 00:50:50 +0000 (UTC)

martinthomson approved this pull request.

Let's give folks a bit more time to digest, but this looks good.

-full packet number is reconstructed at the receiver based on the largest packet
-number received on a successfully authenticated packet. Recovering the full
-packet number is necessary to successfully remove packet protection.
+In the QUIC long and short packet headers, the number of bits required to
+represent the packet number are reduced by including only a variable number of
+the least significant bits of the packet number.  One or two of the most
+significant bits of the first octet determine how many bits of the packet
+number are provided, as shown in {{pn-encodings}}.
+
+| First octet pattern | Encoded Length | Bits Present |
+|:--------------------|:---------------|:-------------|
+| 0b0xxxxxxx          | 1 octet        | 7            |
+| 0b10xxxxxx          | 2              | 14           |
+| 0b11xxxxxx          | 4              | 30           |
+{: #pn-encodings title="Short Header Packet Number Encodings"}

"Packet Number Encoding for Packet Headers" perhaps

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1334#pullrequestreview-117862158

---

From: Brian Trammell <[email-masked]>
Date: Mon, 07 May 2018 05:35:02 +0000 (UTC)

@britram pushed 2 commits.

4f8bb35  Both long and short have varint PN
8d49212  Merge pull request #1 from quicwg/long-and-short-varint-pn

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1334/files/50f05017ff449405fe14305a510e8b554a86668d..8d4921228db4dc4ed6a0f83531566987e16ae2ef

---

From: MikkelFJ <[email-masked]>
Date: Mon, 07 May 2018 06:05:42 +0000 (UTC)

I'm just wondering if 30 bits is sufficient? It effectively only allows for 2^29 packets outstanding which are half a million. Som NIC's push 40 mpps although probably only sustainable at low RTT.

At the other end, I'm guessing that 3 byte packet numbers are going to be the most needed packet number range: 2^22 / 2 * 1500 / sec = 3MB/s or 30Mbps which is a likely limit on domestic streaming video these days.

For these reasons, perhaps a modulo 128 schema where bit 7 of each byte, except the last is set. It would also future proof the design at much higher transmission rates and possibly above 2^62 packet number limit.

I do dislike this modulo 128 design and it goes against other varint encodings, but there are the arguments above.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1334#issuecomment-386966047

---

From: Kazuho Oku <[email-masked]>
Date: Mon, 07 May 2018 06:12:13 +0000 (UTC)

> I'm just wondering if 30 bits is sufficient? It effectively only allows for 2^29 packets outstanding which are half a million.

@mikkelfj Isn't it half a *billion*? I'd assume that that would be enough.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1334#issuecomment-386967117

---

From: Brian Trammell <[email-masked]>
Date: Mon, 07 May 2018 06:12:32 +0000 (UTC)

3335dd5  Update examples for shorter encodings
60811b2  Merge pull request #2 from quicwg/fix-pn-example

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1334/files/8d4921228db4dc4ed6a0f83531566987e16ae2ef..60811b2d4d47945223247bf2e5d1726f88cb8e68

---

From: MikkelFJ <[email-masked]>
Date: Mon, 07 May 2018 06:15:15 +0000 (UTC)

@kazuho indeed, I got confused about a decimal point vs. 1000 sep.

The 3 byte arg. still holds but it is no worse than what is today, and you can't have it all.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1334#issuecomment-386967636

---

From: Martin Thomson <[email-masked]>
Date: Mon, 07 May 2018 17:28:16 -0700

@martinthomson pushed 1 commit.

7b22bf0  Update table caption

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1334/files/60811b2d4d47945223247bf2e5d1726f88cb8e68..7b22bf02f5528f6e77f12b01a5aaa7fc13315fcc

---

From: janaiyengar <[email-masked]>
Date: Tue, 08 May 2018 16:40:52 -0700

@janaiyengar pushed 1 commit.

7fcd5a7  indent

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1334/files/7b22bf02f5528f6e77f12b01a5aaa7fc13315fcc..7fcd5a766ab224bd9fc9b44a7307ad6bd979e9aa

---

From: janaiyengar <[email-masked]>
Date: Tue, 08 May 2018 16:41:07 -0700

janaiyengar approved this pull request.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1334#pullrequestreview-118569610

---

From: janaiyengar <[email-masked]>
Date: Tue, 08 May 2018 16:43:00 -0700

Merged #1334.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1334#event-1616505032