GREASE the packet type octet

[ianswett]

Google-QUIC had an issue where post-handshake QUIC packets were being dropped, because a bit changed in the public flags, and a middlebox no longer identified it as QUIC.

In order to ensure the entire public flags byte is usable, I suggest we GREASE it by defining the entire space as valid.

Building on Jana's proposal for the public header with a flags byte as a set of codepoints: https://gist.github.com/janaiyengar/b05acb3af17d6e938d25befc69c11eae

The goal is to provide a simple mathematical mapping from any value of the public flags onto a frame type.

My suggestion is to lookup the frame type, and if it's not defined, mod the flags value by the number of frame types defined in that phase(short or long form) and pick the type with that index when ordering the frame types by value.

If an initial packet number is chosen randomly, and the connection ID is as well, greasing the flags byte and version (#112 and #296) covers everything that is not encrypted.

[marten-seemann]

I like this idea very much.

If I understand @ianswett's proposal correctly, we might have to be a bit more careful when it comes to the long packets. Different QUIC versions might define a different number of packet types, so we can't grease before version negotiation is finished. If I understand that correctly, excluding the long packets from greasing would solve that problem (we do slightly modified greasing here if we define a fixed modulo value that is guaranteed to stay constant between all QUIC versions).

Furthermore, in order to simplify the mapping, if we define an ordering of the frame types anyway, wouldn't it be easier to get rid of the explicit values defined in Jana's proposal? I.e. the packet type would just be numbered 1 to n.

Then the rule for the sender is easy: Just add random number x number of frame types to the type number (mod 256). Decoding boils down to a simple mod operation as well.

[ianswett]

Consecutive numbers would be easier, but it does present deployment challenges for Google and anyone else who has Google-QUIC deployed, as we transition from one flags approach to another. This might be solvable other ways, but it'd take some serious thought.

[martinduke]

It's worth pointing out that this absolutely requires authentication of the public header. Otherwise firewalls could zero out the greased bits to avoid potential information leakage.

[RyanTheOptimist]

Agreed. I think we have consensus on that point, but we should confirm on the list. (Google QUIC authenticates the public header.)

[martinthomson]

This requires positive identification of short vs. long form. I think that it also fixes the size of the space in which long form packets can be sent. If the next version of the protocol needs an additional long-form packet, then n_long increases and greased packets suddenly fall into different slots.

That's not workable if you ever want to change this protocol. I believe that long form packets are most in need of this sort of protection - experience with TLS shows that issues are most likely to occur on the very first packet. That doesn't mean that greasing the short form isn't valuable, it's just that greasing the initial packets is more important. We need to balance that with having an escape valve - a way to deploy a new version of the protocol.

We could say that version has to be understood before identifying type (else, send a version negotiation packet and don't grease type there). That requires that only long form packets either be distinct from short form or that only long form packets arrive prior to establishing state. The latter of these doesn't work in light of NAT rebinding, since short form packets will arrive with no context. That leads me to conclude the distinguishing long and short is still useful.

So we say that long form packets are identified by some clearly defined operation. Pick a permutation operation. &0x08 or &0x80 could work, or even something like n%3!=1 so that there can be twice as many long form layouts as short form. After that you know that version is present and can use version to determine if you even have a hope of recovering the type.

Here is where I think @marten-seemann is right about packing the space of valid codepoints. A sparsely populated space makes this easier to build. A complicated PRP hurts, especially since this octet is likely to to need hardware implementation. That accepts that greasing the type loses any hope of preserving bitwise compatibility with Google-QUIC (why didn't anyone pick up on that in Jana's proposal, or am I just being dense through severe lack of sleep?).

That means that adding a new long form packet layout and type requires a new version. I think that's a perfectly reasonable compromise.

Short form packets are easier in a way: since those are only exchanged after version negotiation, the only wrinkle is how they are managed after NAT rebinding. For that, the connection ID remains our best way to ensure that they can be correctly recovered. Once the server can correlate the packet with a connection, then it's easy to recover type.

@martinduke, @RyanAtGoogle, see #302.

[ianswett]

I believe a plausible solution is for the server to supply the client a list of all type byte codepoints in the ServerHello that have been defined in versions subsequent to this connection's version and the server supports, and hence should not be greased by the client. And greasing would never be done until the handshake completes, of course.

This is not that elegant, but ensures all codepoints are in use at all times, either by valid connections or by greasing the value.

[MikeBishop]

Maybe I'm missing something, but if the handshake has completed and we know what version is in use, why do we care if the client collides with a value defined in a different version? Server should interpret based on the agreed version, and if something that was grease becomes valid in a different version... that's kind of the point.

[ianswett]

There is a very real practical concern Google and others may have in the near future, which is that we may want IETF-QUIC to not grease codepoints still in use by GQUIC. But that's not the reason I came up with this originally.

Here's my weak argument, maybe others can do better: If a client comes in from a new IP/Port, then the server has to know how to decode the packet and it can't use version, because it's unknown(unless the server only supports one version, and this is moot). If connection ID is always the same length in the same location, then I believe there's no issue, but otherwise mapping a packet back to it's connection is impossible or speculative.

I think this is more of a challenge for a load balancer that's not terminating the connection than one that is, particularly if one wants that load balancer to be relatively or completely stateless.

[MikeBishop]

Ah, so it's a migration issue: When seeing a packet from a new source, the server has to first decide whether it's an existing connection that has migrated versus an initial packet from a new client, and this decision has to be made before it can know what version to use in interpreting the packet.

Whether it's a bit or a restricted set of values, that seems like an argument for the model of "These are handshake packets, and everything else is post-handshake." The problem scenario seems to be that the client picks as a post-handshake-with-grease value something that a server thinks could be a handshake value in a different version. Is that right?

[martinthomson]

Yep, that's right Mike, that is what I had in mind when I said:

That requires that only long form packets either be distinct from short form or that only long form packets arrive prior to establishing state. The latter of these doesn't work in light of NAT rebinding, since short form packets will arrive with no context.

I appreciate that GQUIC has a problem here. The checksum could be sufficient though.

[martinthomson]

I tweaked the title to reflect recent changes in the packet format.

[ekr]

As I said in the meeting, I have an alternative proposed design:

• Packet has type P
• Encrypt the packet and call the last byte of the packet (the auth tag) T
• Set the new packet type to be P ^ (T & 0x7f) [the 0x7f mask preserves the leading bit]

This randomizes the packet type without placing any special requirements on the construction of the code points.

[mnot]

Discussed in Paris; generally agreed to be a good thing.

Jana and Ian to check to see if this makes migration from Google QUIC easy/hard.

[ekr]

@huitema points out that we might want to have a keyed mask function because any static transformation is easily degreased. The observation here is that you can have a key that's shared across all of the connections, because we're not really worried about the middlebox connecting to the server and extracting the key for the transformation. With that in mind, here's an alternate keeed proposal.

1. Server generates a key K_static which it uses for all connections.
2. Packet has type P and last byte T
3. The server delivers K_static in its first flight.
4. For every packet, you compute P' = P ^(PRF(K, T) & 0x7f) where
    K = 0 for initial packets
    K = K_static for other packets.

This allows stateless unmasking.

[kazuho]

@ekr I am afraid that the approach might not work well with a deployment that uses either connection ID or 5-tuple for load balancing, depending on the type of a packet.

In the past, we have discussed of deployments that would use some bits of a connection ID to route a packet to the correct server sitting behind a load balancer (or to the correct POP within an anycast deployment). Note that such a load balancer will typically not maintain any state of a QUIC connection.

OTOH, I also anticipate that even in a deployment that does connection ID-based load balancing, you might want to route packets to backend servers based on the 5-tuple during the handshake. This is for avoiding attacks targeting a specific server behind a load balancer. Note that processing of handshake packets could be much more computationally intensive due to public-key operations when compared to other types of packets.

The issue with the proposed approach is that it is impossible for a stateless load balancer to determine the correct type of the packet, since whether K=0 or K=K_static should be used depends on the state of the connection. Therefore, with the proposed approach, it becomes impossible to change how the packet is load balanced depending on the type of a packet.

Am I missing something?

[ekr]

Hmm.. I see your point. That is a problem. There's probably some way around that (one idea would be to steal one more bit for that), but I'll have to think about the best approach.

[kazuho]

Thank you for the response. I agree that stealing a bit could fix the problem.

Reconsidering this, it seems to me that there is another issue (sorry for the fuss).

My understanding is that some load balancers start streaming packets to the correct port before seeing the end of the packet. Making the actual type depend on the final octet of a packet prevents us from using such a load balancer.

Would it be possible to use an octet that exists at the beginning of the packet for greasing?

[ekr]

The problem is that then if you are not encrypting, than those bytes are not random. @larseggert suggested that this shouldn't really be a big deal

[huitema]

The greasing requires some kind of "obfuscation" or "encryption" of the packet type. Simple obfuscation would be to combine the packet type with some fields in the packet, and would not require any "key". Problem with that is that middleboxes will quickly learn the obfuscation algorithm, and then reverse it. So if we want to actually grease, we need to use some kind of key-driven encryption.

[huitema]

Yesterday, we briefly mentioned a potential solution in which the packet type would be encrypted with a key known by the load balancer. Of course, having the same key used by the load balancer and every client does not work. The middleboxes would just have to set a connection to the service to learn the key. In any solution like that, the key has to be specific to a single client. It will have to depend on the connection ID, something like f(ConnectionID, local secret).

The good part is that if we do something like that, we can also encrypt the packet number.

[MikeBishop]

There was an action item on @janaiyengar and @ianswett here, and it's been pretty quiet since Paris. Any updates?

[ianswett]

Sorry, this fell off my radar. We'll discuss and document any potential issues if they exist.

[ianswett]

Parked until everyone gets onto the invariants. Somewhat dependent upon Packet Number Encryption #1079

[martinthomson]

Changes to the first octet have addressed this. With header protection, there are no unused values to grease left.

[ianswett]

Woohoo!