Subject: Re: Dictionary Compression for HTTP (at Facebook)

From: Ryan Sleevi <[email-masked]>
Date: Sat, 1 Sep 2018 15:31:46 -0400

On Sat, Sep 1, 2018 at 1:23 AM Jyrki Alakuijala <[email-masked]> wrote:

> On Fri, Aug 31, 2018 at 4:58 PM, Ryan Sleevi <[email-masked]> wrote:
>>
>> Of course, this is all after the security concerns are mitigated ;)
>>
>
> We involved Thai Duong in the security analysis and we have a limited
> scope solution that allows much of the benefits without these security
> concerns. One main mitigation there is to never compress data mixed from
> public and private sources.
>

Yes. That’s been well understood and well discussed as the bare minimum -
but that requires servers understanding what constitutes public and private
sources, or the interaction between data that may need to remain private
through timing leaks.

I don’t think it’s fair to say without the security concerns - there’s a
considerably high bar to demonstrate that, both in theory and in practice.
A compression scheme that requires serves dramatically rework their serving
infrastructure in order to tag such is, generally speaking, an insecure
solution. The adoption of a given method is highly correlated to its lack
of footguns, and tagged annotations of public v private are a giant footgun
for server operators and not worth the risk to users, or the implicit trust
that servers and server operators can and will get it right.

---

From: Kenji Baheux <[email-masked]>
Date: Mon, 3 Sep 2018 11:52:52 +0900

Is the assumption that Servers / Server operators, unless vertically
integrated (e.g. FB and other big players), will probably get it wrong
because they lack the application knowledge to dissociate public vs.
private sources?

One option that was discussed in a side chat at IETF 101 was to expose this
to JS (Fetch / Streams / ...) where the knowledge about public vs. private
exists. But that implies a different, and most likely harder, adoption
story.

The scale benefits of Servers / Server Operator is definitely appealing.
So, I'm wondering if we have exhausted all the reasonable options. Is there
nothing that would at least cover a significant subset of the use cases?

Some naive questions / thoughts:

   - Would it still be valuable to enable shared dictionary compression by
   Servers for responses that are completely free of private data?
   - Can a Server / Server operator infer that response isn't tainted by
   private sources, i.e. only contains "public" data? From the absence of
   specific (existing) headers?
   - If not, what if Servers had to assume "mixed" unless the response was
   augmented with a new(?) header. I imagine that a server configuration
   scheme / header would be simpler in terms of adoption than requiring web
   developers to do all the work in JS land.

On Sun, Sep 2, 2018 at 4:57 AM Ryan Sleevi <[email-masked]> wrote:

>
>
> On Sat, Sep 1, 2018 at 1:23 AM Jyrki Alakuijala <[email-masked]
> <jyrki@google..com>> wrote:
>

---

From: Benjamin Kaduk <[email-masked]>
Date: Sat, 1 Sep 2018 23:05:13 -0500

On Fri, Aug 24, 2018 at 10:24:23AM +0000, Felix Handte wrote:
> Jyrki,
> 
> Glad to hear it! We're excited too!
> 
> We look forward to playing with Brotli's new capabilities when they're available.
> 
> Yes, Zstd can accept unformatted buffers as dictionaries, which it uses as you describe. Additionally though, Zstd describes a format for structured dictionaries[1], which includes metadata in addition to an LZ77 prefix.

One topic that came up during IESG review of draft-kucherawy-dispatch-zstd was
whether/when third-party or standard dictionaries would become available and how
dictionary IDs would be assigned for those cases (since at present, IIUC, the
dictionary IDs would need to be pre-negotiated between the two parties).  No
IANA registry was created at that time, but with a 4-byte dictionary identifier space
to work with, it seems like there might be space to create a registry for dictionary
IDs (including private use space, of course), and just publishing well-known
dictionaries.

-Ben

> [1] https://github.com/facebook/zstd/blob/dev/doc/zstd_compression_format.md#dictionary-format <https://github.com/facebook/zstd/blob/dev/doc/zstd_compression_format.md#dictionary-format>
> [2] https://tools.ietf.org/html/draft-vandevenne-shared-brotli-format-01#section-9 <https://tools.ietf.org/html/draft-vandevenne-shared-brotli-format-01#section-9>
>

---

From: Ryan Sleevi <[email-masked]>
Date: Tue, 4 Sep 2018 12:52:57 -0400

On Sun, Sep 2, 2018 at 10:52 PM Kenji Baheux <[email-masked]>
wrote:

> One option that was discussed in a side chat at IETF 101 was to expose
> this to JS (Fetch / Streams / ...) where the knowledge about public vs.
> private exists. But that implies a different, and most likely harder,
> adoption story.
>

I don't think JS provides a resolution for those issues - rather, it allows
for experimentation without needing to fundamentally introduce those to all
layers of the stack. This is already true of what servers are doing today -
e.g. the incremental delivery of updated assets through the combination of
Service Workers/LocalStorage + differential encoding schemes for static
resources.

The problem is when you try to generically apply this to all resources, at
a protocol layer (HTTP), because now you're fully detached from the
application semantics involved in having a single HTTP resource combining
these types of data, which seems to be an argument for use cases made by a
number of these proposals.

>    - Would it still be valuable to enable shared dictionary compression
>    by Servers for responses that are completely free of private data?
>
> No, I don't think there's a reasonable solution that somehow involves
multiple HTTP clients agreeing on what constitutes a 'safe' server of only
public data, nor do I think the goals and incentive structures are aligned
for a declarative expression.

>    - If not, what if Servers had to assume "mixed" unless the response
>    was augmented with a new(?) header. I imagine that a server configuration
> I think this potentially misinterprets the set of concerns raised. I think
the optimization for servers is misaligned with the security needs. Servers
will necessarily prefer to do the 'faster' things, and the incentives for
security are seen as costs/complexity, yet the benefits aren't realized by
the servers, but the users and clients accessing those resources.

---

From: Felix Handte <[email-masked]>
Date: Wed, 5 Sep 2018 13:01:23 -0700

On 09/01/2018 09:05 PM, Benjamin Kaduk wrote:> One topic that came up 
during IESG review of draft-kucherawy-dispatch-zstd was
> IDs (including private use space, of course), and just publishing well-known

Yes, we continue to think about whether and how to produce a standard 
set of dictionaries for public consumption. Zstandard reserves 
dictionary IDs 1-32767 for that purpose.

Dictionaries become more effective when they are targeted towards / 
trained on a narrower set of content. A solution that lets site 
operators build and use their dictionaries will enable sufficiently 
motivated parties to achieve the best possible compression. Zstandard 
provides tooling for that purpose, allowing users to easily train and 
use their own dictionaries.

OTOH, distributing and storing dictionaries is not without cost, and so 
a great number of highly targeted dictionaries introduces its own 
inefficiencies. So even in a world with custom dictionaries, we think 
that a standard set of dictionaries probably has utility. Site operators 
who don't expect enough repeat traffic to amortize the cost of 
distributing a custom dictionary, or who don't want to expend the effort 
of building custom dictionaries, could simply use them. And a standard 
set of dictionaries would certainly enable shipping "batteries-included" 
plugins to HTTP servers, lowering the barrier to use.

Building a standard set of dictionaries is not trivial, though. We 
recently performed experiments training a set of dictionaries on a 
dataset from the HTTP Archive[1]. We found that performance degrades 
significantly over time. A dictionary trained on 2016 traffic and 
applied to 2018 traffic performs worse than a 2018 dictionary does on 
2018 traffic (anywhere from one to five percent compression ratio loss 
per year).

So ideally, even in the context of a standard set of dictionaries, we 
would find a way to update or introduce new dictionaries as time goes on.

- Felix

[1] https://httparchive.org/

---

From: Yoav Weiss <[email-masked]>
Date: Fri, 7 Sep 2018 13:51:16 +0200

On Mon, Sep 3, 2018 at 4:56 AM Kenji Baheux <[email-masked]>
wrote:

> To expand on that, when I was thinking about attack scenarios and
mitigations for HTTP compression dictionaries
<https://tools.ietf.org/html/draft-vkrasnov-h2-compression-dictionaries-03#section-4.1>,
one possible mitigation was for browsers to only allow it for responses for
non-credentialed requests, as well as limiting compression context sharing
to same-origin.

Any thoughts on the effectiveness of that as a mitigation?

>    -

---

From: Felix Handte <[email-masked]>
Date: Fri, 21 Sep 2018 21:31:20 +0000

Very well, I will attempt to grab the bull by the horns, then. Let's 
talk security.

I guess my first question is this: What is the acceptance criterion for 
proposals in this space with respect to security? From my survey of 
previous conversations on this topic, it has sounded like the bar that 
proposals are being held to is that they are expected not to have any 
vulnerabilities. This is of course a reasonable expectation in general. 
However, compression as it exists in HTTP is well known to have security 
flaws (primarily, BREACH and its extensions). Given that flawed status 
quo, in order to clear that bar, a new proposal would not only have to 
avoid introducing new vulnerabilities, it would have to solve existing ones.

If we are going to make a serious attempt to fix BREACH et al., let's do 
so. Otherwise, let's hold compression work to a practical bar, which is 
to avoid introducing new security issues and to avoid making existing 
ones worse.

If we accept that criterion, my question becomes whether there are known 
issues that would prevent the use of dictionary compression? Many people 
have invoked the idea of security concerns to explain their hesitancy to 
pursue solutions in this space. Despite the frequency with which they're 
brought up, I haven't seen any specific allegations that describe a 
vulnerability introduced by dictionary-based compression. Are there 
known attacks that are made possible or improved by the use of dictionaries?

Obviously the above question is hugely dependent on how dictionaries are 
sourced. Since that's an open question, my sense is that it's probably 
best to look at the narrowest possible scope first and then work our way 
out from there. So I'm particularly curious whether there are known 
issues even when you leave out the challenges of dictionary creation / 
distribution / etc., when you just use statically-defined dictionaries.

In particular, BREACH and friends describe the dangers of mixing private 
data and attacker-controlled data in the same compression window. 
Dictionary-based compression mixes a presumably public dictionary with 
private data. Is that sufficient to enable attacks? Or if you have 
dictionary + private data + attacker data, is that easier to attack than 
in the absence of a dictionary?

I'll follow up with my own impressions of the security concerns and 
possible mitigations soon.

- Felix

On 08/31/2018 07:58 AM, Ryan Sleevi wrote:
> 
> 
> On Fri, Aug 24, 2018 at 6:24 AM Felix Handte <[email-masked] 
> <mailto:[email-masked]>> wrote:
> 
>     For our own part, we find ourselves drawn towards a solution that
>     makes a lot of the same choices as SDCH. That is, one that treats
>     dictionaries as explicit resources that can be dynamically
>     advertised by an origin, fetched and cached by a client, and then
>     negotiated to be used in requests/responses between the two. The
>     ability to treat a previous, cached response as a base on which to
>     apply a "diff" (negotiated by ETag?) is also attractive to us.
> 
> 
> I would strongly advise against such solutions, as they are a 
> significant part of why SDCH support was removed from browsers.
> 
> I think, to the set of concerns you need to consider in any such 
> solution (which, in my mind, demonstrating the security concerns can be 
> mitigated is paramount of those), you need to define not only the 
> interaction in the 'simple' HTTP sense of Request/Response pairs, but 
> also in the complexity of those interactions as they apply to browsers, 
> for which concerns like same-origin versus cross-origin apply, the 
> re-ordering of requests, and the potential of multiple requests 
> proceeding simultaneously (which H/2 also has to countenance). This also 
> further interacts with models of cache storage and in-memory 
> representation - challenges such as "What happens if a dictionary 
> expires midway during the processing of a response" were fairly fatal, 
> as were the issues around TOCTOU - that is, advertising a dictionary 
> from a request, making a request with said dictionary, and finding it 
> was evicted from the cache prior to the response.
> 
> Models such as the approach by vkrasnov h2-compression-dictionaries are 
> substantially superior in these respects, because it more closely models 
> and defines these interactions, through the association with and scoping 
> to a single H/2 resource.
> 
> It might be that your concern is not the dominant HTTP case of browsers, 
> in which case, it may be fine to ignore these. But I think, from the 
> experiences implementing and maintaining SDCH, models that approximate 
> that space (of resourced dictionaries, advertisements, etc) are likely 
> to be too great an implementation cost, and too great a cognitive cost 
> to the predictability of the platform, to see any meaningful adoption.
>

---

From: Patrick McManus <[email-masked]>
Date: Fri, 21 Sep 2018 18:55:26 -0400

Hi Felix,

> proposals in this space with respect to security? From my survey of

you are not going to be able to pre-negotiate working group acceptance
criteria. The criteria is what it always is - rough consensus on a draft
from the working group and the approval of the IESG.

But to help with more background, the past concern that has been there
hasn't been sufficient/proactive analysis of the various proposals - and
given that the mixture of compression of encryption is known to be a
problem (as you mention) a bar of "no known problems" hasn't been enough to
get anywhere near rough consensus. I believe people wanted to see a
proactive analysis of what the concerns of a particular proposal are. At
that point we can debate whether they are reasonable or not for their
anticipated gains.

make sense? You're certainly going in a reasonable direction considering
the interactions of dictionaries, what attackers control, and the ways in
which public and private data are mixed. Of course confidentiality can
apply to 'public data' as well and its not clear how/if folks would want to
handle that.

---

From: Ryan Sleevi <[email-masked]>
Date: Fri, 21 Sep 2018 23:50:31 -0400

> apply to 'public data' as well and its not clear how/if folks would want to

Exactly this. To expand on this a bit more, there are other technical
considerations, such as:
- Are the dictionaries dynamically constructed based on the resources?
Meaning that, unlike gzip-et-al at an HTTP layer, and more like the
now-disabled TLS compression, there's inter-resource implications to the
security model. Does loading A then B reveal different information than
loading B then A? How should that be modeled?
- If dictionaries are static, how are the dictionaries determined? Are they
baked into the specification, or can they be self-declared?
- If the site self-declares/creates its own dictionaries, how will clients
receive these dictionaries? What are the protocol interactions there as it
relates to both 'classic' HTTP cases (for example, a libcurl utility or a
simple proxy) and more complicated cases, like browsers, which have their
own set of loading behaviours?
- Are these things addressable at the HTTP protocol layer, or do they
require being integrated into the application-layer fabric (like a Web
browser)? How will that interact with functionality like CORS and CORB, to
prevent cross-origin leakages?

Felix, you can see different approaches to the 'add dictionary compression'
have explored some of the design space above and chosen different things,
but as Patrick mentioned, there hasn't been a real sit down on the analysis
as to what the implications are of these decisions, their merits, and their
risks. I think Vlad's work is perhaps the closest one to feeling right
based on 'gut', but even in past IETF discussions, the uncertainty and
difficulty reasoning about that gut instinct has meant that a compression
scheme represents a large intellectual investment and time commitment.

To further build on why the status-quo may not be a reasonable bar, given
the profoundly negative interactions compression can have on the
confidentiality of the data being compressed, a parallel might be drawn to
TLS clients supporting 3DES or AES-CBC. These are ciphers or constructions
with known weaknesses and sharp edges, and require extreme care to get
right - but they are (or, at this point, were) widely deployed. Just
because they were widely deployed, however, wouldn't justify making those
same design decisions for new ciphersuites - as the TLS WG demonstrated
through TLS 1.3.

Deprecating HTTP compression support in browsers is, arguably, the right
thing to do. The number of organizations that can and have integrated
thorough analysis about the relation between 'public' and 'private' data
likely ranges in the handfuls, given how it keeps biting people. Yet its
widespread use means that, for practical purposes, we're in a rock and a
hard-place. Introducing new schemes in this space would have the
(personally) undesirable effect of encouraging more folks to adopt
compression, which would see even greater losses to confidentiality. Of
course, the high-order bit is getting the adoption of better
confidentiality protections in the first place - the adoption of TLS
instead of unencrypted HTTP and the adoption of TLS 1.3 are both more
pressing and relevant to keeping a vibrant and healthy Web ecosystem.

Understandably, I'm also biased towards the browser case, which deserves
acknowledging because it may be that the WG does adopt new compression
schemes as a work activity for intra-CDN activity or 'enterprise' or custom
bespoke applications. However, since most folks seem to be most keen on
HTTP compression due to the ability to save bytes to clients using web
browsers, it sets a higher bar than the status quo in order to be
compelling.

Hope that further expands on these concerns.