Subject: Greasing more of QUIC

From: Martin Thomson <[email-masked]>
Date: Thu, 7 Dec 2017 16:03:54 +1100

I've sort of promised a few times, to a few people, that I'd write up
the state of play regarding greasing.  I just did that and it got
somewhat lengthy.  So I decided that I'd put the words in a draft.
Sorry.  That's what you get when publishing drafts gets easier...

https://datatracker.ietf.org/doc/html/draft-thomson-quic-grease

Based on this, I'm a little more enthusiastic about protecting packet
numbers, mainly for the secondary benefits that come with it.  But
I'll let others reach their own conclusions about that.

---

From: Jana Iyengar <[email-masked]>
Date: Wed, 6 Dec 2017 23:38:33 -0800

Martin,

Thanks for writing this up! One main thought as I read the draft.

I suspect the mechanisms here are a bit heavyweight for the greasing model
I had in mind. The model I had in mind was that a middlebox that cared to
read the spec would be able to interpret the packet types, but it couldn't
from simply looking on the wire. I don't think we want to use a
per-connection key, as load balancers will want to know the packet type and
won't have the connection keys. Visibility for middleboxes is the reason we
didn't encrypt the packet types in the first place.

If you wanted to do a PRP based on this weaker model you'd end up using a
known key per version, documented in the draft. Of course, the problem here
is that you don't grease any values since the same permutation is used for
a given version, and the permuted packet types remain fixed for the version.

You could combine the version-specific key with something from the packet,
perhaps the packet number (not the entire 64-bit number, only the visible
part on the wire, for stateless middlebox operation), to permute the packet
type, giving you more useful greasing.

Alternatively, for this model of greasing I have in mind, all you need is
to cover the entire space of possible types, not encrypt the packet type. A
simple method would be, for instance, to use the result of (packet number %
packet type). This has the unfortunate property that the packet type will
basically start at a random point in its space but increment by one during
the bulk of the connection, since most packets will use a single packet
type (short header with 2-byte packet number). We can fix that somewhat by
adding a random additive, also documented per version, after the mod
operation: (packet number % packet type + random additive). This has the
property that for consequent packets with the same packet type but
increasing packet number, the resulting packet type will start at a random
value per connection (since initial packet number is random) , and will
increase by a fixed value for any given version.

This is just me thinking off the top of my head, but that's roughly what I
had in mind. It obviously assumes a weaker form of greasing than the ones
in your draft is desirable.

Thoughts?
- jana

---

From: "Brian Trammell (IETF)" <[email-masked]>
Date: Thu, 7 Dec 2017 10:11:39 +0100

hi Martin,

> On 7 Dec 2017, at 06:03, Martin Thomson <[email-masked]> wrote:
> 

First, I'll note that draft focuses on runtime adaptations: how can we scramble the wire image to resist analysis by vendors who will implement the results of that analysis in ways that might break future QUIC versions by dropping packets? This is only part of the space of mitigations available to us. There are also design- and deployment-time adaptations: exercising the version negotiation mechanism, for instance, by making the V2 header beyond the invariants gratuitously incompatible with the V1 header and deploying it very, very soon after V1.

When you said "this got lengthy", what I was hoping I'd see here, and didn't, is an explicit statement of the threat model the greasing we apply is meant to counter. "Ossification", yes, great, but in order to be able to evaluate the tradeoffs (especially between XOR and FFX), we need to get a bit more specific about what that means.

I can think of a couple of axes along which we can classify these models:

(1) Adversary intent: what is the middlebox trying to do? Block QUIC? Whitelist QUIC traffic to block non-QUIC UDP garbage? Track QUIC flow state to whitelist QUIC traffic on a per-flow basis? Classify QUIC traffic by version? Classify QUIC traffic by overlying application layer protocol? Infer end-user activity through the analysis of QUIC traffic? Break QUIC in subtle ways for evil fun? We should be clear about what we're trying to keep from happening *with greasing* (as opposed to with packet protection).

(2) Adversary information: Does the middlebox's creator participate in the standardization process? Does it passively consume the final or intermediate products of the standardization process? Does it statically or dynamically analyze the behavior of open-source implementations of the protocol in a controlled envionment? Does it statically or dynamizally analyze traffic captured from experimentation with open- and closed-source deployments of the protocol on the open Internet? The method by which the adversary figures out what the protocol does

(3) I'm trying to come up with a non-pejorative way to say this but I can't, so, adversary competence: Much of the trouble we've run into with TCP is with lazy or simply bad implementation of well-meaning intent ("we never see options so eh, why write that code?"), or with poor design based on a fundamental misunderstanding of the problem space ("this 2G network sucks, but it was expensive, so it must be TCP's fault; let's screw around with ACK timing, which worked in our experiments with $STACK_X, which is fine because clearly nobody will ever run anything other than $STACK_X on this network"). In general the assumption that laziness is a virtue holds -- designed systems in state-intensive environments tend to try to minimize their state requirements at the expense of correctness, and in any case, it makes economic sense to minimize the effort and expense in designing and implementing said systems, so corner cases will lead to cut corners. But it is very hard to model the laziness of other people, so this is the fuzziest and most guess-prone axis of the three.

Greasing is of most utility, IMO, when it is used to prevent lazy, somewhat-competent middlebox creators with access to but little interest in reading the specs from expanding the set of invariants beyond those which we prescribe, whether intentionally or unintentionally (indeed, a non-lazy adversary working to intentionally expand the set of invariants would just send a pull request on the invariants doc. :) ).

Doing something to protect the ability to expand/change the location and semantics of the packet type switching mechanism and the packet number space and encoding in future versions seems like it's worth doing. Attempting to make these mechanisms resistant to analysis, though, doesn't seem like it has a benefit commensurate with effort and proneness to error.

> I'll let others reach their own conclusions about that.

I'm also a *little* more enthusiastic, depending again on what the threat model is, and whether we want the packet numbers to be decodable at all along the path by devices which do understand the protocol (i.e. for one- and two-point loss measurement, as well as to reject bad spin bit samples, on which see https://tools.ietf.org/html/draft-trammell-quic-spin-00#section-3.3).

Cheers,

Brian

---

From: Martin Thomson <[email-masked]>
Date: Fri, 8 Dec 2017 10:51:47 +1100

On Thu, Dec 7, 2017 at 6:38 PM, Jana Iyengar <[email-masked]> wrote:
> I suspect the mechanisms here are a bit heavyweight for the greasing model I
> had in mind.

Not really, see below.  I included a more heavyweight option to show
the range of options that I think we have in front of us.

> The model I had in mind was that a middlebox that cared to read
> the spec would be able to interpret the packet types, but it couldn't from
> simply looking on the wire. I don't think we want to use a per-connection
> key, as load balancers will want to know the packet type and won't have the
> connection keys. Visibility for middleboxes is the reason we didn't encrypt
> the packet types in the first place.

I want to challenge this last point.  I don't think that we've
established a good reason for middleboxes to have visibility into the
short header types, and anything that we do for the long header can
probably only be based on the spec in exactly the way you describe -
we never use anything other than a fixed key to protect packets with
long headers.

I'm personally more interested in packet numbers than packet types though.

> is that you don't grease any values since the same permutation is used for a
> given version, and the permuted packet types remain fixed for the version.

One property I'm looking for us to guarantee is that no value goes
unused, even if the actual underlying value is the same.  That means
per-connection permutations.

> type, giving you more useful greasing.

That's effectively what this does.  The draft (I'm beginning to regret
doing that now) mentions using connection ID, as input to the key.  I
should have added both packet number and even the ciphertext.  You
will observe that XOR is very close to what you describe if you take
packet number as input to the key derivation (XOR and additional
modulo N are very similar).  If you took connection ID and packet
number in the following form, you get almost exactly what you
describe.

E(x) = m ^ connection_id ^ packet_number

> had in mind. It obviously assumes a weaker form of greasing than the ones in
> your draft is desirable.

That is a reasonable position.  Types will never really benefit much
from anything more complex.  For packet number, I wanted something
stronger to support the ideas in the final section.

---

From: Martin Thomson <[email-masked]>
Date: Fri, 8 Dec 2017 11:31:06 +1100

> First, I'll note that draft focuses on runtime adaptations: how can we scramble the wire image to resist analysis by vendors who will implement the results of that analysis in ways that might break…

Right.  And I still think that's a better general defense.

> (1) Adversary intent: what is the middlebox trying to do?

I don't think that intent matters here.  One of the things I've
learned from TLS that attempting to discern intent is like trying to
comprehend Lovecraft's Deep Ones.  It's a short trip from there to an
asylum.

Your next two points I consider to be points on a spectrum.  The
biggest problem is the one you alluded to above.  The middlebox is
deployed and is inflexible.  It can be perfectly capable,
understanding everything there is to understand about the protocol
short of getting session keys, but that doesn't mean that changing
anything is possible.  Even if the upgrade pace of the middlebox is
rapid - and our experience with TLS suggests the opposite - nothing
safeguards flexibility better than being flexible.

As I said, I think that the best we can do within any single version
of the protocol is to force middleboxes into stateful inspection if
they intend to look at version-dependent traits.  This is confounded
by the fact that even if a middlebox does stateful inspection, they
won't necessarily see the version due to the possibility of connection
migration.  That said, as long as the number of packets required to
prime stateful inspection exceeds or equals the number of packets that
are required to correctly recover the version, this could be
successful.  Ideally, learning version is a prerequisite for recovery.

> Greasing is of most utility, IMO, when it is used to prevent lazy, somewhat-competent middlebox creators with access to but little interest in reading the specs from expanding the set of invariants…

That is more proactive than I'd look for.  There's no business
motivation for worrying about protocols that aren't deployed.
Middlebox vendors definitely aren't stupid or lazy (notable exceptions
aside).  They implement what they need to, and read the specs as
necessary.  But what's deployed matters.  That's where we get into
trouble.  The middlebox that has an "allow HTTPS" policy learns to
examine flows more closely when people start using TLS over port 443
for other protocols to circumvent that policy.  When they look too
closely or too incautiously (see for example
https://arxiv.org/pdf/1607.01639.pdf), we experience bizarre
breakages.

The point here is to increase the cost of the sort of casual,
stateless inspection that can be destructive to the point that
stateful inspection is more viable.  Either that or encourage the use
of techniques other than looking at packets.

> Doing something to protect the ability to expand/change the location and semantics of the packet type switching mechanism and the packet number space and encoding in future versions seems like it's…

The only analysis I'm looking to guard against is correlation across
migrations.  Using an unpredictable key has that advantage.  (It also
removes a bunch of really ugly properties from the current
mitigation.)

---

From: <[email-masked]>
Date: Wed, 13 Dec 2017 17:09:08 +0100

Hello Brian,

On -10/01/-28163 20:59, Brian Trammell (IETF) wrote:
>
> [...] what I was hoping I'd see here, and didn't, is an explicit statement of the threat model the greasing we apply
> is meant to counter.

Thanks for focusing on this. I'd like to take this opportunity to chime in with a network operator's perspective on 
these matters.

As it turns out, the generic term "middlebox", which seems to be rather loaded in this context, somehow hides another 
important use case for us: a passive middle observer meant for troubleshooting.

While I agree that all active middleboxes may somehow wreck things in creative though unwilling ways, a passive middle 
observer can do no harm. But the point is that this middle observer is not only harmless, but necessary for the smooth 
operation of the network, which benefits the whole chain: its purpose is simply to locate, as effectively as possible, 
the offending link or piece of equipment, once some problem has been detected end-to-end.

To do so, the most efficient method is dichotomy, which allows to home in on the problem in logN steps for a path of N 
segments, where each steps means (1) installing the middle observer at a chosen point on the path and (2) deciding 
whether the problem happens upstream or downstream from that point.

Clearly step (2) assumes that the measurements done by the middle observer give the upstream/downstream information.
This means that the observable of interest (RTT, loss or reordering) should be available for both upstream and 
downstream segments. This somehow constrains the class of methods that can be designed to support the use case. In this 
respect, the spin bit is satisfactory (since it gives both upstream and downstream RTT estimates), while proposed 
alternatives like packet number echo aren't (since they only yield end-to-end RTTs).

Now, while pondering options like a random key shared by the endpoints, please keep in mind the use case of dichotomic 
troubleshooting, where typically none of the endpoints is under control. You may still impose stateful operation on the 
middle observer though. But don't just kill it.

-Alex

_________________________________________________________________________________________________________________________

Ce message et ses pieces jointes peuvent contenir des informations confidentielles ou privilegiees et ne doivent donc
pas etre diffuses, exploites ou copies sans autorisation. Si vous avez recu ce message par erreur, veuillez le signaler
a l'expediteur et le detruire ainsi que les pieces jointes. Les messages electroniques etant susceptibles d'alteration,
Orange decline toute responsabilite si ce message a ete altere, deforme ou falsifie. Merci.

This message and its attachments may contain confidential or privileged information that may be protected by law;
they should not be distributed, used or copied without authorisation.
If you have received this email in error, please notify the sender and delete this message and its attachments.
As emails may be altered, Orange is not liable for messages that have been modified, changed or falsified.
Thank you.

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Wed, 13 Dec 2017 12:15:09 -0500

A passive middle box observer can do harm if the deployment is large scale
and mission critical. If it mis-interprets new QUIC version it may report
network damage which may cause operators to explicitly block new QUIC
versions as opposed to deal with upgrading passive, but mission critical,
middleware.

Kind Regards,
Mikkel Fahnøe Jørgensen

On 13 December 2017 at 17.09.15, [email-masked] (
[email-masked]) wrote:

Hello Brian,

On -10/01/-28163 20:59, Brian Trammell (IETF) wrote:
>
> [...] what I was hoping I'd see here, and didn't, is an explicit
statement of the threat model the greasing we apply
> is meant to counter.

Thanks for focusing on this. I'd like to take this opportunity to chime in
with a network operator's perspective on
these matters.

As it turns out, the generic term "middlebox", which seems to be rather
loaded in this context, somehow hides another
important use case for us: a passive middle observer meant for
troubleshooting.

While I agree that all active middleboxes may somehow wreck things in
creative though unwilling ways, a passive middle
observer can do no harm. But the point is that this middle observer is not
only harmless, but necessary for the smooth
operation of the network, which benefits the whole chain: its purpose is
simply to locate, as effectively as possible,
the offending link or piece of equipment, once some problem has been
detected end-to-end.

To do so, the most efficient method is dichotomy, which allows to home in
on the problem in logN steps for a path of N
segments, where each steps means (1) installing the middle observer at a
chosen point on the path and (2) deciding
whether the problem happens upstream or downstream from that point.

Clearly step (2) assumes that the measurements done by the middle observer
give the upstream/downstream information.
This means that the observable of interest (RTT, loss or reordering) should
be available for both upstream and
downstream segments. This somehow constrains the class of methods that can
be designed to support the use case. In this
respect, the spin bit is satisfactory (since it gives both upstream and
downstream RTT estimates), while proposed
alternatives like packet number echo aren't (since they only yield
end-to-end RTTs).

Now, while pondering options like a random key shared by the endpoints,
please keep in mind the use case of dichotomic
troubleshooting, where typically none of the endpoints is under control.
You may still impose stateful operation on the
middle observer though. But don't just kill it.

-Alex

Ce message et ses pieces jointes peuvent contenir des informations
confidentielles ou privilegiees et ne doivent donc
pas etre diffuses, exploites ou copies sans autorisation. Si vous avez recu
ce message par erreur, veuillez le signaler
a l'expediteur et le detruire ainsi que les pieces jointes. Les messages
electroniques etant susceptibles d'alteration,
Orange decline toute responsabilite si ce message a ete altere, deforme ou
falsifie. Merci.

This message and its attachments may contain confidential or privileged
information that may be protected by law;
they should not be distributed, used or copied without authorisation.
If you have received this email in error, please notify the sender and
delete this message and its attachments.
As emails may be altered, Orange is not liable for messages that have been
modified, changed or falsified.
Thank you.

---

From: <[email-masked]>
Date: Wed, 13 Dec 2017 19:25:30 +0100

I'm talking about middle observers which we do use every day to maintain real-life networks. We deploy them 
intentionally, after being notified of issues by other means, and make human decisions on their observations. No "short 
loop" with automated, too fast reactions.

My point is that this use case is an important one to support. The theoretical possibility of misuse of its enablers has 
no bearing on the cost of *not* supporting it. Which is huge.

-Alex

On 13/12/2017 18:15, Mikkel Fahnøe Jørgensen wrote:
> A passive middle box observer can do harm if the deployment is large scale and mission critical. If it mis-interprets
> new QUIC version it may report network damage which may cause operators to explicitly block new QUIC versions as opposed
> to deal with upgrading passive, but mission critical, middleware.
>
> Kind Regards,
> Mikkel Fahnøe Jørgensen
>
>
> On 13 December 2017 at 17.09.15, [email-masked] <mailto:[email-masked]>
> ([email-masked] <mailto:[email-masked]>) wrote:
>
>> Hello Brian,
>>