varint packet numbers

[britram]

Now that we have varints in the protocol, the only integers not using them are packet numbers. This seems a little odd. Using varints for packet numbers could simplify implementations, as well as s simplifying the short header, by removing the need for a Type field.

There seem to be to be two broad approaches for doing this (well, three, including "don't")

• Do nothing. Packet numbers continue to be defined as modular, and to have a separate integer encoding from varint encoding in the frames. This requires two separate bits of code for handling packet numbers and all other integers in the protocol.

• Use varint packet numbers, and require the full packet number to always be transmitted. This has the advantage that integer code can be used everywhere, but now that we're starting the packet number space between 0 and 2^32-1 (which would probably be 2^29-1 with this proposal to ensure that varint 30 could always be used for short flows), would be less efficient on the wire. updated: discussion below seems to be converging on the fact that this isn't a great idea, and I agree.

• Use varint packet numbers, but allow the sender to choose to use a 6-, 14-, 30-, or 62-byte varint to represent the least significant 6, 14, 30, or 62 bytes of the packet number as with the current logic. This would retain the advantage of simplifying the short header, and following the principle of least surprise, but nullifies some of the code simplification advantages.

[ianswett]

I like the fact this would allow us to specify the full 62 bit packet number if we wanted.

If we do this, I think we should do this for both the short and long header.

I do not want to require the full packet number always be transmitted. TCP has used a similar approach for wrapping sequence numbers for decades without issue.

[britram]

Agree; this should appear the same in both the long and short header. Reducing the number of encodings is the point.

To be clear, IMO the third option (allow sender to choose truncation, require receiver to interpret wrapping) is the preferred one, and the second one is probably worse than doing nothing, but I wanted to point out all the options for completeness.

[ekr]

I also favor the third option.

…

On Tue, Dec 5, 2017 at 8:29 AM, Brian Trammell ***@***.***> wrote: Agree; this should appear the same in both the long and short header. Reducing the number of encodings is the point. To be clear, IMO the third option (allow sender to choose truncation, require receiver to interpret wrapping) is the preferred one, and the second one is probably worse than doing nothing, but I wanted to point out all the options for completeness. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#989 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ABD1oa5zxcfd8Y1Jy3ZLm3BI8pjQwgJEks5s9W91gaJpZM4Q2Id8> .

[mikkelfj]

I also prefer the third option. The single byte variant is not very useful unless you only send a ping every other minute or so. It could be used for encoding 126-bit packet numbers in some future QUIC version.

Using the varint format throughout while only encoding the modulo would make such a change fairly easy. There are probably some gremlins hidden in the frame headers - for example the flow control max values could be modulo 2^64.

[martinthomson]

Since the varints won't affect the invariants [1], we can decide this more or less at our leisure. For the record, this won't be in -08.

Note that this isn't as simple as is being made out. With a varint encoder you pass a byte offset and you get back a number and a new byte offset. With a varint, you need to pay attention to how much the byte offset moves so that you can overwrite the correct number of bits to the left of the bits you got.

[1] ... not to mention the varmints.

[britram]

Since the varints won't affect the invariants [1], we can decide this more or less at our leisure...

Yep, I mainly filed this now because it seems logical enough that I figured someone else had already filed it, and I couldn't find it.

Re: difficulty: agreed, this is not quite as simple as overlaying 32 LSB on a 64 bit internal packet number and wrapping around (as with the present headers), but an informational appendix on How To Use Varints / a wiki / a reference implementation would go a long way to showing people how to keep the gremlins at bay.

[martinduke]

I'm not sure if this is a related issue or not, but the "Packet Numbers" section is very clear on how to size the packet number in the packet header, but there is no corresponding advice for sizing the largest_acknowledged field in the ACK frame. In general Varints refer to numbers that start at zero, so there is a natural occasion to truncate them. Packet numbers have 32 bits, so right away we're at 32.

To be specific, the packet header part requires enough bits to encode 2 * (max_pkt - lowest_pkt_unacked). This obviously doesn't work so well on the receiver side. We could just mandate a de facto min size of 4, tie it to the peer's packet number size, or something else.

[martinthomson]

The largest_acknowledged is NOT truncated. I made that same assumption once too, but I thought we'd addressed that with text... It is the entire packet number. It's also the reason that packet numbers can't exceed 2^62-1 now. That means that it will be rare to ever find an ACK packet with a short encoding for largest_acknowledged. That said, if you read some of the ideas in my new draft, maybe we can turn that around.

You might recall that the packet number size in STOP_WAITING was tied to the packet header. And it was loathsome to implement. There is probably some way to shorten the packet number in ACK, but I'd want to see a complete write-up.

[martinduke]

The draft just says "variable length". I suppose this means that it's variable as in 30 or 62 bits. If there's clarifying language somewhere I simply missed it. If not, it could probably use some.

[mikkelfj]

There is AFAIK no requirement for varints to be stored in the shortest possible form, i.e. in canonical form.

For packet numbers the canonical form would include leading zeroes as an exception because it is a modulo operation but for other values that would not be the case. This makes it fairly easy to conclude how much of the stored reference packet number to update.

I'm not sure if there is value in requiring canonical form in general, but I guess some implementations would make that assumption anyway which could lead to problems down the road.

[mcmanus]

It is the entire packet number. It's also the reason that packet numbers can't exceed 2^62-1 now. That means that it will be rare to ever find an ACK packet with a short encoding for largest_acknowledged.

I think that the benefits of starting PN at 0 in order to get better encoding in ack frames is a good reason to not go with random PN. It looks like you make a couple non-random grease suggestions in your new draft which sounds promising.

[mcmanus]

he draft just says "variable length". I suppose this means that it's variable as in 30 or 62 bits. If there's clarifying language somewhere I simply missed it. If not, it could probably use some.

the PN in the ack has to be explicit because of reordering.. ack the wrong implicit thing and you're not a reliable protocol anymore.. the envelope PN can get away with implicit because its the nonce to the trial decrpytion.

[ianswett]

I think that the benefits of starting PN at 0 in order to get better encoding in ack frames is a good reason to not go with random PN. It looks like you make a couple non-random grease suggestions in your new draft which sounds promising.

If we have varint packet numbers in the header, then we can do 'random' packet numbers only within a single byte, instead of the current 4 bytes of randomness, which I think achieves both greasing and low byte overhead.

[martinduke]

Varints aren't strictly necessary to have one-byte packet numbers. Just the first 3 bytes have to be zero. But I'm fine with varint packet numbers.

[mcmanus]

If we have varint packet numbers in the header, then we can do 'random' packet numbers only within a single byte, instead of the current 4 bytes of randomness, which I think achieves both greasing and low byte overhead.

its pretty obvious looking at 08 logs that we are currently using a lot of 8 byte varints in acks on trivially short connections. 3/4 of initial packet numbers require them immediately.

[britram]

It would be useful to have a PR for this one. I'm happy to volunteer to put one together, but ISTM that #1043 should land first, as it impacts packet number encoding, how a sender determines which varint size it should use.

[martinthomson]

When #1079 lands, assuming that it does, @britram we'd appreciate a PR.

Note that I really, really don't want an 8 octet encoding, so maybe something bespoke is warranted. We might need some information on what number of bits is most often needed so we can optimize for that case.

[britram]

ACK.

IMO this makes sense to do in either case, though the language depends a bit on whether the varinted number will be subsequently encrypted. Do we plan on determining whether #1079 is in next week? I don't see it explicitly called out in the agenda yet.

[britram]

#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?

[martinthomson]

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.

[britram]

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.

[ianswett]

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

[mikkelfj]

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, both 1079 PNE, and subsequent varlength, requires that the buffer be updated before AEAD can be applied.

[janaiyengar]

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 ***@***.***> 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. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#989 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AKjg1NpF79xyVS8yDxLJZBc7nI_EH2bVks5tuy5dgaJpZM4Q2Id8> .

[martinthomson]

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.

[kazuho]

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 #1322 (comment)).

[britram]

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.

[britram]

@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...

[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)

@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.

[britram]

@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 :) )

[martinthomson]

Closed by #1334.