Subject: Too many GREASE codepoints

From: "Martin Thomson" <[email-masked]>
Date: Wed, 18 Nov 2020 10:41:13 +1100

(I've been meaning to write this for a few days, but the IANA review prompted me to sit down and work through it.)

I have come to believe that we are reserving too many codepoints for greasing.

The greasing function we currently use is 27+N*31.  That's about 2^57 values.  148764065110560896 by my estimation.

The waste I can tolerate.  This is a very large number, but it leaves plenty of values free for use.  The problem is that the odds of collision are too low.

This problem was highlighted when draft-iyengar-quic-delayed-ack-02 chose a greased codepoint.  The failure mode there is terrible: occasionally an implementation will generate a greased value that collides with this value.  If an implementation of that draft encounters that collision it will fail.  It will probably fail when trying to parse the transport parameter, but it could instead fail when it receives the frame.  Alternatively, is also plausible that an implementation of the draft could include a greased value with the same codepoint, which would be similarly bad.  Such failures are virtually impossible to reproduce and unless you are lucky enough to have good logging, you might have trouble catching the reason for the error.

The odds that an implementation of that draft would encounter a peer who used a greased codepoint with the same value is minuscule.  There are around 2^57 valid greasing values, so even if every connection ever included greased values, the odds of a given connection containing that value is tiny. (Coincidentally, this is the same as the probability we allow for an attacker to attack the packet protection AEAD.)

I think that we want a higher risk of collision than that.  Then mistakes like this will result in a higher probability of failure when deployed.  Ideally, failures will be discovered in testing.

The reason we have a non-trivial number of reserved codepoints is to avoid having implementations that filter out these reserved values by just enumerating them.  However, for that we don't need so many reserved values.  Even as little as 1000 will create a disincentive to tabulate the values.  That many would add a large 8k table to a simple implementation.

If we were to select 1000 (or 1024) values in a way that is relatively simple to generate from a random number, then that would be better than the current situation.

So I'm going to propose that we define a new function that takes a 10-bit random value and produces a greasing codepoint.  This can be used to produce a greasing codepoint.  I have two requirements:

* It should be a tiny bit more complex to implement a function that tests a value for whether it is reserved.  The current scheme is easy to filter.  (X - 27) % 31 == 0 isn't much code to write.

* The scheme needs to produce values that encode to 1, 2, and 4 bytes in varints with reasonable probability.  An even distribution over 2^62 with 1024 values has a gap of 2^52 between each value, which means that 2 byte and 4 byte values aren't likely to be represented.

The function I've been thinking of looks like this:

def grease(n):
    v = 27
    i = 1
    while n > 0:
        v = (v << i) | (n & 1)
        i = i + 1
        n = n >> 1
    return v

This is bit spreader, taking the bits of the random value and adding progressively more space between each bit.

When passed 0x3ff, the resulting value is the 60-bit binary value: 0b110111010010001000010000010000001000000010000000010000000001.  Smaller values result in different 1 bits being turned off.  If it is passed 0x1ff, it produces the shorter 50-bit value of 0b11011101001000100001000001000000100000001000000001.

The result is two values that encode to 1 byte, 14 values that encode to 2 bytes, 48 values that encode to 4 bytes, with the remaining 960 values encoding to 8 bytes.

Detecting this is fairly easy, but also probably not worth writing out the code to do so.  This could be made considerably harder by flipping more than one bit at a time.  For example, `v = (v << i) ^ ((n & 1) * 19)`.

What do people think?  Is this a change we could tolerate?  Or is my logic faulty here in some way?

---

From: Christian Huitema <[email-masked]>
Date: Tue, 17 Nov 2020 15:52:11 -0800

> This is bit spreader, taking the bits of the random value and adding progressively more space between each bit.
Looking for a nerd feast, are we?
> What do people think?  Is this a change we could tolerate?  Or is my logic faulty here in some way?

I don't know. I observe that most extension designers pick a 12 to 16
bit code that looks cute, and then prepend something like "ff01" to deal
with draft numbers. A nice property would be to make grease collisions
up to 16 bits easy to evaluate, and then ensure that patterns like
"ff121dea" do not collide if the root pattern "1dea" does not.

-- Christian Huitema

---

From: Lucas Pardue <[email-masked]>
Date: Wed, 18 Nov 2020 00:17:39 +0000

I don't know.

This is just a proposal but do you know if the new grease code points would
collide with any existing extensions in QUIC or HTTP/3? Some short term
pain should not preclude a design change but I'd be more confident knowing
either way.

Having written some extension I-D, the current process of code point
generation is simple but tedious. The process I came to was to extract the
quiche implementation grease code into a standalone application, run it a
couple of times to find something not ugly (but not vanity) and then add 1
to it. That "buys me some land" that I can use for successive
Internet-Draft revisions, each new one simply adds 1 again. Even then I had
some comments that my long codepoint was a bit annoying and so I relented
to shortening the code even further by lopping off N top bits. I took care
to check for grease overlap again but that's a step easily missed.

I'm not advocating my process but it highlights some definciencies in the
UX of random codepoint selection. There's some game theory here wrt to
boundary conditions. Starting on work with a random value
lower-than-but-too close to a grease point risks some discontinuity if your
aim is to use successive codepoints. It's tempting to clamp to the other
side of the boundary (or natural divisions within each grease point gap) in
the name of safety.

I wonder if we could address some of these problems with assistive
technologies, like hosting a JavaScript generator on quicwg.org that does
some collision avoidance based on registries.

Cheers
Lucas

On Tue, Nov 17, 2020 at 11:53 PM Christian Huitema <[email-masked]>
wrote:

> > (I've been meaning to write this for a few days, but the IANA review
> prompted me to sit down and work through it.)
> >
> > The greasing function we currently use is 27+N*31.  That's about 2^57
> values.  148764065110560896 by my estimation.
> >
> > The waste I can tolerate.  This is a very large number, but it leaves
> plenty of values free for use.  The problem is that the odds of collision
> are too low.
> >
> > This problem was highlighted when draft-iyengar-quic-delayed-ack-02
> chose a greased codepoint.  The failure mode there is terrible:
> occasionally an implementation will generate a greased value that collides
> with this value.  If an implementation of that draft encounters that
> collision it will fail.  It will probably fail when trying to parse the
> transport parameter, but it could instead fail when it receives the frame.
> Alternatively, is also plausible that an implementation of the draft could
> include a greased value with the same codepoint, which would be similarly
> bad.  Such failures are virtually impossible to reproduce and unless you
> are lucky enough to have good logging, you might have trouble catching the
> reason for the error.
> >
> > The odds that an implementation of that draft would encounter a peer who
> used a greased codepoint with the same value is minuscule.  There are
> around 2^57 valid greasing values, so even if every connection ever
> included greased values, the odds of a given connection containing that
> value is tiny. (Coincidentally, this is the same as the probability we
> allow for an attacker to attack the packet protection AEAD.)
> >
> > I think that we want a higher risk of collision than that.  Then
> mistakes like this will result in a higher probability of failure when
> deployed.  Ideally, failures will be discovered in testing.
> >
> > The reason we have a non-trivial number of reserved codepoints is to
> avoid having implementations that filter out these reserved values by just
> enumerating them.  However, for that we don't need so many reserved
> values.  Even as little as 1000 will create a disincentive to tabulate the
> values.  That many would add a large 8k table to a simple implementation.
> >
> > If we were to select 1000 (or 1024) values in a way that is relatively
> simple to generate from a random number, then that would be better than the
> current situation.
> >
> > So I'm going to propose that we define a new function that takes a
> 10-bit random value and produces a greasing codepoint.  This can be used to
> produce a greasing codepoint.  I have two requirements:
> >
> > * It should be a tiny bit more complex to implement a function that
> tests a value for whether it is reserved.  The current scheme is easy to
> filter.  (X - 27) % 31 == 0 isn't much code to write.
> >
> > * The scheme needs to produce values that encode to 1, 2, and 4 bytes in
> varints with reasonable probability.  An even distribution over 2^62 with
> 1024 values has a gap of 2^52 between each value, which means that 2 byte
> and 4 byte values aren't likely to be represented.
> >
> > This is bit spreader, taking the bits of the random value and adding
> progressively more space between each bit.
> > When passed 0x3ff, the resulting value is the 60-bit binary value:
> 0b110111010010001000010000010000001000000010000000010000000001.  Smaller
> values result in different 1 bits being turned off.  If it is passed 0x1ff,
> it produces the shorter 50-bit value of
> 0b11011101001000100001000001000000100000001000000001.
> >
> > The result is two values that encode to 1 byte, 14 values that encode to
> 2 bytes, 48 values that encode to 4 bytes, with the remaining 960 values
> encoding to 8 bytes.
> >
> > Detecting this is fairly easy, but also probably not worth writing out
> the code to do so.  This could be made considerably harder by flipping more
> than one bit at a time.  For example, `v = (v << i) ^ ((n & 1) * 19)`.
> >

---

From: Nick Harper <[email-masked]>
Date: Tue, 17 Nov 2020 16:37:44 -0800

> "ff121dea" do not collide if the root pattern "1dea" does not.
It sounds like the problem that Martin has discovered here is that draft
authors aren't evaluating the formula for grease codepoints when selecting
a codepoint to use. If draft authors were perfect in selecting codepoints,
this problem wouldn't exist.

Greasing is intended to solve the problem of an implementation rejecting
unknown values from its peer. So long as the implementation doesn't add
code to check "is this codepoint a grease codepoint", it doesn't matter how
many codepoints we reserve for grease or how simple or complicated the
algorithm is for generating those codepoints.

This proposal does two things: it makes the algorithm for determining
whether a codepoint is a grease codepoint more complicated, and it reduces
the number of grease codepoints. I think that doing the former is
counterproductive towards solving the problem of drafts accidentally using
grease codepoints, though the latter may counteract that problem. By making
the algorithm more complicated, I think draft authors will be less likely
to check if their selected codepoint collides with a grease codepoint, and
more likely to hope that their chosen number doesn't collide. By reducing
the number of grease codepoints, the strategy of hoping for avoiding a
collision works better, but in any case, there's still the chance that a
draft might pick a codepoint that collides with grease.

A similar problem to the one Martin raises is that two drafts could pick
colliding codepoints. We can't expect grease to detect this and inform the
authors of one of the drafts that they need to change their codepoint. We
shouldn't expect grease to do the same thing when instead a draft has a
codepoint that collides with grease.

In regards to the improbability of reproducing a failure due to a collision
with a grease codepoint, there's an easy answer that doesn't involve
changing the spec. An implementation doesn't need to choose a value
uniformly from the whole space; it could choose to subset the space and
pick randomly from that space. An implementation can also choose a single
value and use that repeatedly for some period of time (e.g. choose a value
at startup).

A radical solution to the problem of codepoints in drafts colliding with
grease codepoints is to reserve no codepoints for grease. This doesn't mean
that we don't grease at all. Instead, it means that implementers will need
to periodically check the IANA registries and exclude from their generated
grease values anything that collides, and implementations should only
grease if they can be kept up to date (and otherwise stop greasing if they
haven't received a timely update). Each implementer can then choose how
large or small of a space they want to grease.

---

From: Kazuho Oku <[email-masked]>
Date: Wed, 18 Nov 2020 09:38:18 +0900

2020年11月18日(水) 8:41 Martin Thomson <[email-masked]>:

> This problem was highlighted when draft-iyengar-quic-delayed-ack-02 chose
> a greased codepoint.  The failure mode there is terrible: occasionally an
> implementation will generate a greased value that collides with this
> value.  If an implementation of that draft encounters that collision it
> will fail.  It will probably fail when trying to parse the transport
> parameter, but it could instead fail when it receives the frame.
> I think that we want a higher risk of collision than that.  Then mistakes
> like this will result in a higher probability of failure when deployed.
> Ideally, failures will be discovered in testing.
>
> The reason we have a non-trivial number of reserved codepoints is to avoid
> having implementations that filter out these reserved values by just
> So I'm going to propose that we define a new function that takes a 10-bit
> random value and produces a greasing codepoint.  This can be used to
> * It should be a tiny bit more complex to implement a function that tests
> a value for whether it is reserved.  The current scheme is easy to filter.
> (X - 27) % 31 == 0 isn't much code to write.
>
> The result is two values that encode to 1 byte, 14 values that encode to 2
> bytes, 48 values that encode to 4 bytes, with the remaining 960 values
> encoding to 8 bytes.
>

This is an interesting proposal, though I am not sure how much it helps.

The argument for the proposed scheme is that the chance of collision
becomes negligible. However, the proposal tries to have higher probability
for small numbers.

If we are to reduce the chance of collision, I think we should simply use
something like (X + INT32_MAX - 4) % INT32_MAX == 0 or something, and also
encourage greasing endpoints to use verbose notations for varints (e.g.,
use 0xc000000000000001 to represent 1). I think that the latter rule would
enforce receivers to decode varints before processing the input, and then,
we do not need to have higher probability for small numbers.

That said, I am not sure if we have to change the greasing scheme at this
point. When we noticed that the ack-delay extension was colliding with the
greasing ID, I created the PR below, that detects such misuse at compile
time:

    https://github.com/h2o/quicly/pull/416

It might just be sufficient if other endpoints implement this type of
detection scheme as well.

> Detecting this is fairly easy, but also probably not worth writing out the
> code to do so.  This could be made considerably harder by flipping more

-- 
Kazuho Oku

---

From: Nick Harper <[email-masked]>
Date: Tue, 17 Nov 2020 16:43:01 -0800

> detection scheme as well.

Google's implementation does something similar, though at compile time:
https://source.chromium.org/chromium/chromium/src/+/master:net/third_party/quiche/src/quic/core/crypto/transport_parameters.cc;l=1039;drc=f50df03b5c021e63d80ecf09ea452fa9976071ea;bpv=1;bpt=1
.

---

From: Lucas Pardue <[email-masked]>
Date: Wed, 18 Nov 2020 00:45:09 +0000

> detection scheme as well.
Or add the failure condition to the I-D tools :D

---

From: Ian Swett <[email-masked]>
Date: Tue, 17 Nov 2020 20:05:43 -0500

I'm ok with changing greasing codepoints, but I'd prefer a simpler option
if we're going to do that like 27 + N*31*31?  Using any codepoints in the 1
or 2 byte encodings seems a bit wasteful given how valuable they are, but
after that, I can't imagine anyone cares about burning a few codepoints.

---

From: Willy Tarreau <[email-masked]>
Date: Wed, 18 Nov 2020 07:09:34 +0100

Hi Martin,

> This is bit spreader, taking the bits of the random value and adding progressively more space between each bit.

What about:

      (35 + 35 * (i % 18) / 18) << (i / 18) - 35

for i in 0..1023

It returns progressive values from 0 to 2^62-35 following an exponential
curve, thus all encodings will be evenly spread. While it relies on a
56-bit shift, it doesn't require more than 10 bits operations at a time,
but needs unsigned arithmetics. We can keep only the 6 higher bits set
with all the remaining ones to zero and avoid unsigned overflow by
simplifying it like this:

      (34 + 35 * (i % 18) / 18) << (i / 18)

It only varies the upper bits. It also has the benefit of being easy to
validate by checking that the value is exactly one of these 18 values
followed by any number of zeroes: 34,35,37,39,41,43,45,47,49,51,53,
55,57,59,61,63,65,67 (i.e. (value >> fls(value)) equals one of these).

Just my two cents,
Willy

---

From: Lucas Pardue <[email-masked]>
Date: Wed, 25 Nov 2020 00:02:04 +0000

Folks,

The proposed change is design.

Martin created https://github.com/quicwg/base-drafts/issues/4387, I
encourage the WG to express their support or pushback on the ticket as to
whether we take it on as a design issue.

Cheers
Lucas
On behalf of the QUIC WG Chairs