Subject: ezflate: proposal to reinstitute deflate header compression

From: <[email-masked]>
Date: Mon, 2 Jun 2014 19:23:05 +0000

No, we haven't been living under a rock.  Yes, we've heard of CRIME.

CRIME exploited the deflate algorithm as described in RFC 1951, not the deflate format. What makes the RFC 1951 algorithm vulnerable to the CRIME attack is that it does character by character matching (normally this is a good thing because it maximizes the number and length of matches!).

The first paragraph of Section 4 of RFC 1951 says that "[implementations] need not follow [the general algorithm presented here] in order to be compliant."

We propose an alternate deflate algorithm called ezflate ("easy flate"); a token-based deflate algorithm.  The key feature of the ezflate algorithm (and primary difference to the RFC 1951 algorithm), is that it does token-by-token matching.

Here is a simple example, to illustrate how it works.  Consider the following HTTP/2 requests (abbreviated):

:method: GET

:path: /

accept-encoding: gzip

:method: GET

:path: /cool.html

accept-encoding: gzip, sdch

The tokens ":method", "GET", ":path", "accept-encoding" and "gzip" are compressed in the second request. The tokens "/cool.html" and "sdch" are not compressed.

Now consider another pair of requests (abbreviated):

:method: GET

:path: /awesome.html

secret: ABCDEFGH

:method: GET

:path: /?guess=ABC

secret: ABCDEFGH

The tokens ":method", "GET", ":path", "secret" and "ABCDEFGH" are compressed in the second request.  But more importantly, the attacker's guess of the secret "ABC" does not trigger a match and is impervious to a CRIME-like attack.  (Of course, just like hpack, ezflate is vulnerable to a brute-force attack of all 8-character combinations.)

The ezflate algorithm is non-http/2 specific so we divided our Internet Drafts into two parts (the ezflate algorithm itself and the http/2 header compression based on ezflate):

http://www.ietf.org/id/draft-morgan-ezflate-00.txt

http://www.ietf.org/id/draft-morgan-http2-header-compression-00.txt

We have implemented ezflate as an additional "compression strategy" called Z_EZFLATE in the zlib library.

The code is very straightforward. We basically only had to implement one new compression function (in addition to the existing deflate_fast & deflate_slow, we added ezflate).  We relied on the rest of the proven zlib infrastructure for windowing, hash chains, Huffman coding, etc.

We used the http2/http_samples [1] har files as test vectors for analysing the compression factor of our ezflate implementation. Here are the data:

pt=plain-text; df=deflate; hp=hpack*; ez=ezflate**

Method  avg-bytes/req (% of pt) avg-bytes/rsp (% of pt)

pt 574 (n/a) 407 (n/a)

df  70 (12%)  62 (15%)

hp  91 (16%)  83 (20%)

ez  99 (17%)  77 (19%)

For the data set, hpack is slightly better on requests and ezflate is slightly better on responses, but the difference is negligible and likely depends on the use cases. (Note that requests to multiple hosts were interleaved as if they were all sent to a single proxy.) So changing to ezflate just based on the compression factor is not compelling...

...BUT, there are other benefits of ezflate beyond the raw compression factor...

+ Interoperability is easy; any inflate library (e.g. zlib) will decompress ezflate streams

+ Built on the proven zlib library (our implementation)

+ Easy to implement a custom compressor i.e. less complexity

+ Custom resource-constrained implementations are possible by trading off compression for resources

+ Furthermore, resource-constrained implementations can use non-compressed header blocks or Huffman-only header blocks

+ Allows interleaving of HEADERS frames with other frame types

+ Streaming

+ Useful for any tokenizable data stream (e.g. html) which contains secret and attacker-controlled data (think BREACH)

*hpack was configured with a table-size=4096, the hpack results come from nghttp2 deflatehd

**ezflate was configured with window-bits=12 (4096 window), mem-level=6 (default), level=6 (default -> level is a non-factor for ezflate)

Regards,

Keith & Chris

[1] https://github.com/http2/http_samples

This email message is intended only for the use of the named recipient. Information contained in this email message and its attachments may be privileged, confidential and protected from disclosure. If you are not the intended recipient, please do not read, copy, use or disclose this communication to others. Also please notify the sender by replying to this message and then delete it from your system.

---

From: Willy Tarreau <[email-masked]>
Date: Mon, 2 Jun 2014 21:45:08 +0200

> + Interoperability is easy; any inflate library (e.g. zlib) will decompress ezflate streams

Which makes me fear that it's as prone to DoS attacks as gzip (eg: send
1 Mbps of headers which are decompressed as 1 Gbps or headers), and as
slow (a 40 Gbps capable server will basically scale down to less than
1 Gbps due to the cost of the compression).

Don't forget that CRIME is not the only weakness of gzip here, it was
the absolute showstopper, but the other issues remain :-/

Regards,
Willy

---

From: Martin Thomson <[email-masked]>
Date: Mon, 2 Jun 2014 13:00:28 -0700

> compression for resources

With a nod to Willy's "other issues":

Does the compressor dictate the size of statement commitment required
by the decompressor?
If not, are you proposing that we somehow use the same sort of
settings-based method for limiting this in HPACK?

---

From: <[email-masked]>
Date: Tue, 3 Jun 2014 07:48:50 +0000

Hi Willy,

> 1 Gbps due to the cost of the compression).

No matter the header scheme, plain-text, hpack, ezflate ... you shouldn't be accepting 1 Gb of headers.  The h2 spec may not limit the size of headers, but any good implmentation will.

> the absolute showstopper, but the other issues remain :-/

What other issues?  Please elaborate.
This email message is intended only for the use of the named recipient. Information contained in this email message and its attachments may be privileged, confidential and protected from disclosure. If you are not the intended recipient, please do not read, copy, use or disclose this communication to others. Also please notify the sender by replying to this message and then delete it from your system.

---

From: Willy Tarreau <[email-masked]>
Date: Tue, 3 Jun 2014 10:18:17 +0200

Hi,

On Tue, Jun 03, 2014 at 07:48:50AM +0000, [email-masked] wrote:
> No matter the header scheme, plain-text, hpack, ezflate ... you shouldn't be
> accepting 1 Gb of headers.

Huh ? 1 Gbps of headers is not much, it's only 125000 requests per second
with 1kB of headers each. A number of products achieve this in plain text
right now with HTTP/1.1. We must certainly not slow down HTTP/2 to the
point where it cannot upgrade existing servers, proxies, load balancers,
etc.

> The h2 spec may not limit the size of headers,
> but any good implmentation will.

I'm not speaking about the size but the parsing speed and emission
speed.

> What other issues?  Please elaborate.

The ones I mentionned above :-)

In short :
  - attack amplification (up to 1000 times the bandwidth with gzip/deflate)
  - processing cost on the send side for servers and intermediaries.

I appreciate that gzip/deflate is a good general purpose compressor which was
well suited for the last 30 years to compress various data and particularly
file archives, but it comes with a heavy weight to compress small strings,
and we cannot blame it for that, it was clearly not its primary purpose when
it was designed. Hpack may or may not have some issues (I have not implemented
it yet so I would not pronounce myself on it), but at least it has the merit
of having been designed for the exact purpose it will be used for. My only
concern with it is how we could disable it when its gains are not considered
worth its costs, or when an issue is faced later and we need to disable it.

Willy

---

From: <[email-masked]>
Date: Tue, 3 Jun 2014 08:21:50 +0000

by the decompressor?

YES. I forgot to mention that thanks for reminding me.

SETTINGS_WINDOW_BITS

default is 12 (4096 window)

---

From: RUELLAN Herve <[email-masked]>
Date: Tue, 3 Jun 2014 08:45:16 +0000

> -----Original Message-----
> From: Willy Tarreau [mailto:[email-masked]]
> Sent: mardi 3 juin 2014 10:18
> To: [email-masked]
> Cc: [email-masked]; [email-masked]
> Subject: Re: ezflate: proposal to reinstitute deflate header compression
>
> ...
> 

HPACK in itself can't be disabled, but you can always send headers as literals and flagging them to forbid indexation further down the path. You can do this for all headers, to go back to an encoding close to HTTP/1.x, or only for some critical headers.
This feature was added recently, after a security analysis of HPACK.

> Willy

Hervé.

---

From: Willy Tarreau <[email-masked]>
Date: Tue, 3 Jun 2014 17:21:20 +0200

On Tue, Jun 03, 2014 at 08:45:16AM +0000, RUELLAN Herve wrote:
> HPACK in itself can't be disabled, but you can always send headers as
> literals and flagging them to forbid indexation further down the path. You
> can do this for all headers, to go back to an encoding close to HTTP/1.x, or
> only for some critical headers.

OK, thank you Hervé for this clarification.

Regards,
Willy

---

From: Greg Wilkins <[email-masked]>
Date: Wed, 4 Jun 2014 10:51:25 +0200

Keith,

what I like about this proposal is that it essentially makes being safe
from CRIME style attacks somebody else's problem.   Ie the transport
protocol should not need to tie itself in knots trying to make up for the
deficiencies of the secure channel of choice on the internet.

Currently I've seen at least 3 security inspired mechanism in h2 that I
don't think belong in the transport protocol.

   - Firstly there is data frame padding, complete with scary text about
   how you must use this feature if you wish to be secure - But don't even
   think of trying to use it unless you are a super security expert.

   - We then have hpack encoding strategies that must pick the right style
   of encoding depending on the security nature of the meta data.  Easy for
   cookies, but not much else.

   - While not in the spec, I have seen a hpack implementation that is
   using a constant time string equals function, so it does not leak timing
   information on inequality failure!

These are all at the discretion of the implementation and thus I do not
understand how they move security forward in any general way and users will
not know if they can trust https2 or not. Will it really only be safe to
use my online banking if I know both ends are using constant time equals
comparisons?   How will the users know that their bank server is generating
safe padding? Will the browser location bar contain a bunch of little icons
for constant time equals, safe padding generation etc.

I do understand that something has to be done to fix the deficiencies of
TLS.  I just don't see why that is the responsibility of the h2 protocol
and the detailed implementations to do so.     Not every (or any) h2
implementation is going to be able to warrant that it does not leak some
kind of information about it's security related content.  Avoiding
compressing cookies is OK, but I just don't know what to do with the other
mechanisms and nor will many many http2 implementers.

I can't really comment much more about this specific proposal, simply
because I'm not just not qualified and do not have the deep security
related knowledge to do so.   For exactly this reason, I think the
transport protocol is not the place to solve these types of problems - we
should use and depend on RFCs that have been developed by a WG of security
experts.

As for using ezflat in h2, should be fine.  Using gzip was a bit of a pain
in SPDY because of serialisation  for the shared state, but we have that
with hpack anyway.  At least it is fragmentable.

cheers

-- 
Greg Wilkins <[email-masked]>
http://eclipse.org/jetty HTTP, SPDY, Websocket server and client that scales
http://www.webtide.com  advice and support for jetty and cometd.

---

From: <[email-masked]>
Date: Thu, 5 Jun 2014 03:37:17 +0000

Hi Greg-

Thanks for the feedback. Changing the subject though to more adequately reflect what you discussed, which IMO is an important point, namely:

Is it the responsibility of h2 to fix security vulnerabilities in TLS?

You make a good argument that the answer is no. The very purpose of protocol layering is separation of concerns. In other words, the security protocol, in this case TLS, should be secure (or patched if it isn't) - the underlying protocol shouldn't have to worry about it.

Nobody should ever be concerned about whether their bank is using the "right" h2 implementation - eg one that uses constant time string comparison functions.

-Keith

On Jun 4, 2014, at 4:52, "[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>> wrote:

Keith,

what I like about this proposal is that it essentially makes being safe from CRIME style attacks somebody else's problem.   Ie the transport protocol should not need to tie itself in knots trying to make up for the deficiencies of the secure channel of choice on the internet.

Currently I've seen at least 3 security inspired mechanism in h2 that I don't think belong in the transport protocol.

  *   Firstly there is data frame padding, complete with scary text about how you must use this feature if you wish to be secure - But don't even think of trying to use it unless you are a super security expert.

  *   We then have hpack encoding strategies that must pick the right style of encoding depending on the security nature of the meta data.  Easy for cookies, but not much else.

  *   While not in the spec, I have seen a hpack implementation that is using a constant time string equals function, so it does not leak timing information on inequality failure!

These are all at the discretion of the implementation and thus I do not understand how they move security forward in any general way and users will not know if they can trust https2 or not. Will it really only be safe to use my online banking if I know both ends are using constant time equals comparisons?   How will the users know that their bank server is generating safe padding? Will the browser location bar contain a bunch of little icons for constant time equals, safe padding generation etc.

I do understand that something has to be done to fix the deficiencies of TLS.  I just don't see why that is the responsibility of the h2 protocol and the detailed implementations to do so.     Not every (or any) h2 implementation is going to be able to warrant that it does not leak some kind of information about it's security related content.  Avoiding compressing cookies is OK, but I just don't know what to do with the other mechanisms and nor will many many http2 implementers.

I can't really comment much more about this specific proposal, simply because I'm not just not qualified and do not have the deep security related knowledge to do so.   For exactly this reason, I think the transport protocol is not the place to solve these types of problems - we should use and depend on RFCs that have been developed by a WG of security experts.

As for using ezflat in h2, should be fine.  Using gzip was a bit of a pain in SPDY because of serialisation  for the shared state, but we have that with hpack anyway.  At least it is fragmentable.

cheers

On 3 June 2014 17:21, Willy Tarreau <[email-masked]<mailto:[email-masked]>> wrote:
On Tue, Jun 03, 2014 at 08:45:16AM +0000, RUELLAN Herve wrote:
> > From: Willy Tarreau [mailto:[email-masked]<mailto:[email-masked]>]
> > To: [email-masked]<mailto:[email-masked]>
> > Cc: [email-masked]<mailto:[email-masked]>; [email-masked]<mailto:[email-masked]>

Regards,
Willy

--
Greg Wilkins <[email-masked]<mailto:[email-masked]>>
http://eclipse.org/jetty HTTP, SPDY, Websocket server and client that scales
http://www.webtide.com  advice and support for jetty and cometd.

---

From: Matthew Kerwin <[email-masked]>
Date: Thu, 5 Jun 2014 14:36:46 +1000

On 5 June 2014 13:37, <[email-masked]> wrote:

> Hi Greg-
>
> Thanks for the feedback. Changing the subject though to more adequately
> reflect what you discussed, which IMO is an important point, namely:
>
> You make a good argument that the answer is no. The very purpose of
> protocol layering is separation of concerns. In other words, the security
> protocol, in this case TLS, should be secure (or patched if it isn't) - the
> underlying protocol shouldn't have to worry about it.
>
> Nobody should ever be concerned about whether their bank is using the
> "right" h2 implementation - eg one that uses constant time string
> comparison functions.
>
>
​I really feel like these CT string functions are a bit of a strawman.
People are allowed to put whatever magic sauce and marketing buzzwords they
like in their implementations; if that helps drive adoption or gain market
share, ​then so be it.

Regarding padding: I don't quite understand the argument against allowing
it in the spec. If the h2 library's API makes frame padding options
available to the application, then the application, which has more chance
of knowing things like the provenance and value of the bytes, can choose to
obfuscate them. If the application doesn't use padding, or does so
improperly, does that count as a security failing of HTTP/2? Is it better
to make everyone never pad at this level?

---

From: Greg Wilkins <[email-masked]>
Date: Thu, 5 Jun 2014 13:02:11 +0200

---

From: Greg Wilkins <[email-masked]>
Date: Thu, 5 Jun 2014 13:09:59 +0200

> to make everyone never pad at this level?

Having the padding in the spec is not that much of an intrusion, but I just
don't see what good it does.   If an application wants to pad it's data for
security reason, then it does not need a transport mechanism for that.
The only reason the transport needs to be aware of padding is if the
transport is expected to do something with it - ie like generate it.   But
as the warnings in the draft clearly make out, generating padding is
apparently non trivial and should only be done by experts with detailed
knowledge of the actual payload.

So if the transport is not going to generate the padding, not handle the
padding, etc. then why does the transport even need to know about the
padding?

To me it is setting false expectation that the implementation of h2 will be
safe from leaking information about their meta data and payloads.

cheers

---

From: Matthew Kerwin <[email-masked]>
Date: Fri, 6 Jun 2014 08:26:36 +1000

On Jun 5, 2014 9:10 PM, "Greg Wilkins" <[email-masked]> wrote:
>
> Having the padding in the spec is not that much of an intrusion, but I
just don't see what good it does.   If an application wants to pad it's
data for security reason, then it does not need a transport mechanism for
that.

If it only wants to pad the data during transport, then the padding is a
transport mechanism. Otherwise you need a higher-level padding mechanism
which both ends understand. Whitespace as a security feature sounds...
interesting...

> The only reason the transport needs to be aware of padding is if the
transport is expected to do something with it - ie like generate it.

Well, yeah. Generate at one end, and strip at the other. Why would my
application code ever want to touch a buffer full of 17000 null bytes?
Especially at the receiving end?

> But as the warnings in the draft clearly make out, generating padding is

Generating is trivial; knowing when to generate isn't.

Because the transport does generate it, but more importantly the transport
strips it at the other end. The receiving application never need know how
much padding was involved -- but if it does want to know, a simple int will
suffice, no point feeding it a huge chunk of allocated memory with no
semantic value whatsoever.

> To me it is setting false expectation that the implementation of h2 will
be safe from leaking information about their meta data and payloads.

Apparently so, but I suspect that comes from our different readings of the
spec. HTTP has lots of features that can help with security, if used
correctly, that are completely optional. It also contains cookies. I think
padding is just one of the former.