Simple transform for improving PN ossification prevention

[Praveen Balasubramanian <[e-mail]>]

The current approach in the draft for preventing PN ossification is to use a random starting PN. Kazuho pointed out a problem with this approach where middleboxes could interpret the PN as a sequence number. And in an attempt to be "helpful", they could reorder the packets exacerbating the HoL blocking problem and may cause issues for unreliable semantics.

If the PN in the clear (the nonce value) didn't always monotonically increase then it will preclude such bad behavior by the middleboxes. Hence we need to find a simple transform that is not monotonically increasing and also not repeating.

Requirements for any PN transform in the single path case:

  1.  The actual PN must always increment by 1 and will be used for generating ACKs in ACK frames.
  2.  The transformed PN in the clear is a nonce and must not repeat over the connection lifetime.
  3.  Middleboxes must not be able to determine the actual PN. Only the QUIC receiver should be able to do so.

PNE is one possible transform that meets all these requirements but it is expensive CPU cost wise and has implications for hardware implementations.

Following is a proposal for an alternative simple transform with low CPU overhead which satisfies these three requirements. The goal is to produce a non-repeating shuffle of the original set of numbers. Since the PN space is very big and efficient shuffle algorithms have O(n) space requirement, we need to define a "reorder degree" or a "batch size" within which we will shuffle the packet numbers.

As an example consider that the starting random PN is 100. Per the current draft the actual PN increments as follows:
    100, 101, 102, 103, 104,    105, 106, 107, 108, 109, ... and so forth

Let's assume a "batch size" of 5. Then using one possible outcome of the shuffles we can generate the following as the cleartext nonces:
|  102, 104, 103, 101, 100, |  107, 105, 109, 108, 106 |   ,... and so forth
The bars | indicate batch boundaries.

Of course since we need the QUIC receiver to get the actual PN from the cleartext value, we need to communicate the offsets in the encrypted portion of the packet, which for this example would be:
|  +2,    +3,   +1,   -2,   -4,    |    -2,   +1,   -2,    0,     +3    |,  ....
Middleboxes will not be able to see the offset values in the clear. QUIC receiver will need to do a simple add of a signed number to get the original PN. This is very cheap operation CPU cost wise.

A QUIC sender implementation can pick any size for the reorder degree, the trade-off is the space complexity and packet space needed to communicate the offsets. A reorder degree within 128 numbers will need at most an extra byte in the encrypted header to communicate the signed offset values. The 128 batch size i.e. a 1 byte offset size should be more than enough entropy to discourage a middle box from "fixing reordering" and in practice we may need less.

One possible algorithm for the shuffle is the Fisher-Yates (Knuth) shuffle as documented here: https://en.wikipedia.org/wiki/Fisher-Yates_shuffle . Please see the "Modern method" section which is in-place. The random number generator doesn't have to be a secure variant.

One advantage of such a scheme is that packet loss can still be inferred by looking at each batch sized set of the nonce (packet numbers). For example if the batch size is 128, then missing numbers in this batch size (or a multiple) will show the extent of packet loss. The other advantage is that a QUIC diagnostic connection can trivially detect a bad middlebox that tries to reorder the nonce in sequence as it will be easily distinguishable from a random network reorder.