Subject: Re: [quicwg/base-drafts] varint packet numbers (#989)

From: Brian Trammell <[email-masked]>
Date: Thu, 03 May 2018 01:25:53 -0700

#1079 landed (and there was much.. rejoicing?), which means it's my turn on this one now. 

I'd like to discuss the proposal briefly before proposing text:

First, it does not appear to me that anyone other than the endpoint needs to know the offset of the protected payload in short headers. Therefore, encryption can work as:

```
encrypted_pn = AES-CTR(pn_key, sample, varint_encode(packet_number, encoded_length))
```

or

```
encrypted_pn = ChaCha20(pn_key, counter, nonce, varint_encode(packet_number, encoded_length))
```

where `varint_encode` takes a plaintext packet number and a target encoded length (1, 2, or 4 bytes), and is to be described in section 4.8 of -transport. (For purposes of the text, I'd probably leave what's in -tls as-is, and make it clear that the plaintext `packet_number` is varint-encoded "as described in section 4.8 of -transport").

Decryption would then decrypt a max-length (4 byte) packet number, then discard trailing bytes of the plaintextœ based on the varint bits in the first byte of the plaintext. (This works with AES-CTR; I'm less familiar with ChaCha20 but I presume it works there too.) This implies that an endpoint must decrypt the packet number before knowing where to start decrypting the payload; does this raise additional issues?

Second, I agree with @martinthomson that varint 0x11 (uint62) packet numbers are not helpful.

Third, I'd propose *not* to varint-encode packet numbers in the long header. This is a _little_ messy, in that long headers now have completely different PN parsing/unparsing code, but reducing the entropy by two bits seems like a higher price to pay.

Comments?

-- 
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/issues/989#issuecomment-386223956

---

From: Martin Thomson <[email-masked]>
Date: Thu, 03 May 2018 03:21:20 -0700

One thing that I've been concerned about here is that the typical varint decoder won't work in this case.  A typical varint decoder consumes bytes and returns a 64-bit value. Here, you have to also track how many bytes were consumed so that you know how many bits to use.  So you need a bespoke parser, or to modify your generic parser to return size as well as the value.  Then you need an error check in case you get the 8 octet value out.

I ran a test with an encoding that looks like this: 0 followed by 7 bits; 10 followed by 14 bits; and 11 followed by 22 bits.  That performed noticeably worse than the standard varint code for random 22 bit values.  The problem was the 3 byte value; changing to a 4 byte value made the encoder considerably faster instead.  That leads me to suggest that we at least consider: 0 followed by 7 bits; 10 followed by 14 bits; and 11 followed by 30 bits.

Think of the ChaCha PN encrypt as CTR mode - it's almost identical, apart from some differences in the API.

I agree re: the long header.

-- 
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/issues/989#issuecomment-386250744

---

From: Brian Trammell <[email-masked]>
Date: Thu, 03 May 2018 04:21:58 -0700

> That leads me to suggest that we at least consider: 0 followed by 7 bits; 10 followed by 14 bits; and 11 followed by 30 bits. 

Since the parser needs to be bespoke *anyway*, and there are indeed situations in which a 7 bit packet number is twice as useful as a six-bit one, I can write this up and we can have something concrete to argue about.

-- 
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/issues/989#issuecomment-386263215

---

From: ianswett <[email-masked]>
Date: Thu, 03 May 2018 14:22:34 +0000 (UTC)

I agree with your and Martin's points and will take a look at the PR.

-- 
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/issues/989#issuecomment-386312732

---

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

Instead of encrypting more than the packet number the encrypted packet number could be placed under authenticated data and encrypted at its exact length. Decryption is a simple xor operation so the PN can be decrypted at length 4 resulting in trailing garbage but the decrypted data is not stored inside the buffer, so it doesn't matter.

The current proposal, but PNE, and subsequent varlength, requires that the buffer be updated before AEAD can be applied.

-- 
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/issues/989#issuecomment-386352601

---

From: janaiyengar <[email-masked]>
Date: Thu, 03 May 2018 18:27:42 -0700

I like the 3-value encoding idea and I like @martinthomson's encoding.
I don't think I understand the reasoning behind not using the same enc/dec
for long headers as well. I'm sure I'm missing something - what's the
rationale?

On Thu, May 3, 2018 at 9:20 AM, MikkelFJ <[email-masked]> wrote:

> Instead of encrypting more than the packet number the encrypted packet
> number could be placed under authenticated data and encrypted at its exact
> length. Decryption is a simple xor operation so the PN can be decrypted at
> length 4 resulting in trailing garbage but the decrypted data is not stored
> inside the buffer, so it doesn't matter.
>
> The current proposal, but PNE, and subsequent varlength, requires that the
> buffer be updated before AEAD can be applied.
>
> —
> Reply to this email directly, view it on GitHub
> <https://github.com/quicwg/base-drafts/issues/989#issuecomment-386352601>,
> or mute the thread
> <https://github.com/notifications/unsubscribe-auth/AKjg1NpF79xyVS8yDxLJZBc7nI_EH2bVks5tuy5dgaJpZM4Q2Id8>
> .
>

-- 
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/issues/989#issuecomment-386484108

---

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

That's a good question.  One fewer bespoke encoder/decoder would be nice.  Given that we lost the fight to keep long headers fixed length, I think that we could use the 7/14/30 encoding there as well.

-- 
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/issues/989#issuecomment-386488729

---

From: Kazuho Oku <[email-masked]>
Date: Thu, 03 May 2018 21:46:33 -0700

I am sorry for being late, but may I propose *not* moving the length bits into the PN field?

Instead, I would like to propose encrypting the length bits, all the reserved bits, and possibly also the KEY_PHASE bit of the first octet in-place.

The reason I propose this is because it simplifies the encoding logic. At the moment, the logic looks like below. The issue is that step 1 is pure overhead, and that people might forget to implement it.

1. fill the reserved bits of the first octet with random value (i.e. greasing)
2. AEAD-encrypt the packet
3. XOR the PN field using the output of a CTR cipher (i.e. pseudo-random octets)

Encrypting the bits in-place solves the issue. The encoding logic becomes:
1. AEAD-encrypt the packet
2. XOR the PN field and also PN length bits and the reserved bits of the first octet using the output of a CTR cipher

As you can see, the need for greasing the bits goes away. Since the output of a CTR cipher is a pseudo-random bitstream, applying CTR to the bits has the same effect as greasing them.

The downside of the approach is that you would need to first apply XOR to the first octet of the incoming packet, and then decrypt the encrypted PN field. But I do not think that is a minor issue compared to the benefit of removing one call to a pseudorandom function on the sender side (i.e. step 1 of the current encoding logic).

And if we decide to not apply key rotation to the PN key, then we can apply the in-place XOR to the KEY_PHASE bit as well, fixing #1322 (see also https://github.com/quicwg/base-drafts/issues/1322#issuecomment-386488960).

-- 
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/issues/989#issuecomment-386504853

---

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

> I don't think I understand the reasoning behind not using the same enc/dec for long headers as well. I'm sure I'm missing something - what's the rationale?

on review, basically, I just forgot we're encrypting the packet numbers now. In the long header as it was, the 32 bits included the random initial offset, and having more bits meant you got more (relative) randomness in the handshake. PNE makes that rationale go away.

-- 
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/issues/989#issuecomment-386828667

---

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

@kazuho aside from the fact that unless I'm missing something, this would break any non-QUIC-end-to-QUIC-end use of the first octet (spin bit, protocol demux), this seems like a separate proposal/issue (which has "you don't need to make PNs varint to protect their length" as a side effect, not as a primary aim) to me...

-- 
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/issues/989#issuecomment-386829253

---

From: Kazuho Oku <[email-masked]>
Date: Mon, 07 May 2018 01:51:33 +0000 (UTC)

> aside from the fact that unless I'm missing something, this would break any non-QUIC-end-to-QUIC-end use of the first octet (spin bit, protocol demux)

@britram Maybe I should have been clearer in my proposal. I am proposing something like below. It does does not break spin bits, etc.

```
+-+-+-+-+-+-+-+-+
|0|K|T T|0|R R R|
+-+-+-+-+-+-+-+-+
  |<----->|
 encrypt here

K - key-phase bit
T - PN length bits
R - the reserved bits (e.g. spin bit)
```

As for the background, I had initially thought that using varint format _within_ the PN field (as proposed in #1334) was fine. But now, to me it seems that many of us agree on the necessity of *not* sending the key-phase bit in clear (see #1322), and to me it seems that protecting the bit using the PN key seems like the straightforward solution.

We can move the key-phase bit into the encrypted PN area for sure. But that would mean that we would only have 6 bits available for the 1-octet encoding of the encrypted PN. That has led me to wonder if we could encrypt the PN lengths bits and the key-phase bit in the first octet, without moving them.

I am sorry for proposing an alternative solution after you have devoted your time on #1334, but it wasn't until late last week that I realized the possibility of protecting the key-phase bit using the PN-key.

-- 
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/issues/989#issuecomment-386936009

---

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

@kazuho okay, this makes sense now. thanks! (and no worries about the time on #1334) -- seems like the discussion over on #1322 is starting to converge, so the ISTM the next step is to propose an alternate PR, and we can talk about this in Stockholm, erm, Kista if we haven't converged by then...

(I remain skeptical about the *actual* utility of this, but I'll put my skepticism over in the other thread :) )

-- 
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/issues/989#issuecomment-386963278

---

From: Martin Thomson <[email-masked]>
Date: Wed, 09 May 2018 21:48:44 -0700

Closed by #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/issues/989#issuecomment-387951012

---

From: Martin Thomson <[email-masked]>
Date: Wed, 09 May 2018 21:48:44 -0700

Closed #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/issues/989#event-1619060855