Subject: Re: comments about draft-ietf-httpbis-header-compression

From: Jyrki Alakuijala <[email-masked]>
Date: Thu, 1 Jan 2015 16:35:45 +0100

If the goal is to just make an algorithm that can work with a static
entropy code with a static dictionary and no LZ77 outside the static
dictionary, the current format (deflate) needs no changes. Deflate supports
all these concepts. You only need a new encoder -- although zlib with
setting a dictionary and running it with quality == 1 is a pretty close
match already, only the static entropy coding is missing then.

Was HPACK ever benchmarked against using deflate in such configuration?
Would you accept help in setting up such an experiment?

Note, that with a static dictionary I mean that we would generate a single
deflate dynamic dictionary from a header corpus and always encode all data
with that -- I don't refer to the static Huffman mode in deflate.

On Wed, Dec 31, 2014 at 7:52 PM, Dave Garrett <[email-masked]>
wrote:

> The goal of HPACK was never to produce ideal compression, just competent
> compression not vulnerable to known issues. Some people do want to attempt
> to
> use/create a far more efficient codec here, but it's now accepted to be
> outside of
> the initial scope. What could be very well received is an HTTP/2 extension
> to
> allow negotiation of alternate header compression methods. This would allow
> actual experimentation in an effort to find the most ideal route(s).
>
>
> Dave
>

---

From: Mark Nottingham <[email-masked]>
Date: Sat, 3 Jan 2015 12:25:07 -0500

See:
  https://github.com/http2/compression-test

This is what we used to help make the initial selection; I don’t believe that the compressor there has been updated to exactly match the spec; e.g., it doesn’t do huffman (Herve?).

Cheers,

> On 1 Jan 2015, at 10:35 am, Jyrki Alakuijala <[email-masked]> wrote:
> 
> If the goal is to just make an algorithm that can work with a static entropy code with a static dictionary and no LZ77 outside the static dictionary, the current format (deflate) needs no changes. Deflate supports all these concepts. You only need a new encoder -- although zlib with setting a dictionary and running it with quality == 1 is a pretty close match already, only the static entropy coding is missing then.
> 
> Was HPACK ever benchmarked against using deflate in such configuration? Would you accept help in setting up such an experiment?
> 
> Note, that with a static dictionary I mean that we would generate a single deflate dynamic dictionary from a header corpus and always encode all data with that -- I don't refer to the static Huffman mode in deflate.
> 
> 
> On Wed, Dec 31, 2014 at 7:52 PM, Dave Garrett <[email-masked]> wrote:
> compression not vulnerable to known issues. Some people do want to attempt to
> use/create a far more efficient codec here, but it's now accepted to be outside of
> the initial scope. What could be very well received is an HTTP/2 extension to

--
Mark Nottingham   http://www.mnot.net/

---

From: Roberto Peon <[email-masked]>
Date: Sat, 3 Jan 2015 09:46:14 -0800

The intent was to make a compressor that was difficult to get wrong from a
security perspective, whose implementation was reasonably easy for good
programmers, and which did good-enough compression.

Your statement about zlib being 'as safe' misses the mark. zlib has more
capabilities, which include things which are known to be unsafe. More
capabilities most usually means less safe. Adding bits in the manner you
suggested doesn't work-- it requires the attacker to do more requests to
determine if what it did was right and this is linear, not exponential.
Even if that wasn't true, you're adding bits (and a fair number of them),
which defeats the purpose of compression.

Non-static entropy coding also leads to non-exponential searches of the
input space if the attacker is allowed to influence the entropy coding.
That is why HPACK doesn't do non-static entropy coding. It uses a canonical
huffman format so that it would be possible to do "non static", though I
envisioned that this would only happen before request bits were sent, e.g.
in the ALPN token.

HPACK offers a means of not doing entropy coding, so if it gets out of
date, either the dictionary gets rev'd (e.g. at startup as described
above), or one chooses to not use it. This is described in section 5.2.

-=R

On Sat, Jan 3, 2015 at 9:25 AM, Mark Nottingham <[email-masked]> wrote:

> This is what we used to help make the initial selection; I don’t believe
> that the compressor there has been updated to exactly match the spec; e.g.,
> it doesn’t do huffman (Herve?).
>
> Cheers,
>
>
> > Note, that with a static dictionary I mean that we would generate a
> single deflate dynamic dictionary from a header corpus and always encode
> all data with that -- I don't refer to the static Huffman mode in deflate.
> >
> >

---

From: Roberto Peon <[email-masked]>
Date: Sat, 3 Jan 2015 09:46:38 -0800

And by 'easy' I mean likely to interoperate.

---

From: Jyrki Alakuijala <[email-masked]>
Date: Mon, 5 Jan 2015 02:20:08 +0100

> programmers, and which did good-enough compression.

A safe (in the sense of CRIME) implementation of deflate can be done in
less than 1000 lines of code, possibly 500 lines. It is much easier to
write than a full zlib implementation. Most likely also easier than HPACK
encoder + decoder.

> capabilities, which include things which are known to be unsafe.
>

Yes. This is why I am promoting a new implementation of the encoder.

> More capabilities most usually means less safe.
>

This is also my concern. The more code you add into the browser, the more
attack surface there is. The deflate decoder is likely relatively safe, and
the same deflate decoder could be used in the future together with a safe
encoder. If you add a new decoder for HPACK into the browser, you will be
increasing the attack surface.

> Adding bits in the manner you suggested doesn't work-- it requires the
> attacker to do more requests to determine if what it did was right and this
> is linear, not exponential.
>

Why not? My intuition is the opposite. Has anyone done the statistics on
this? If there is randomization of the payload size, one will need to do
statistically sufficient testing of all options. In practice this means
that the attacker has to guess about half of the random payload size before
he can make progress. If we add 0-128 bits of random payload by hashing the
other content, the attacker has to do more than 2**64 attempts to get one
byte out. It is definitely going to be exponential with the number of bits.
The attacker can only make progress when he guesses the correct bytes, but
if the length is modulated by a complex hashing function of the data, the
length no longer tells anything unless the change is more than the
variation from the hashing.

> which defeats the purpose of compression.

Yes, but that would be adding bits to a good compression result, instead of
giving up with compression in the first place. If adding bits works (like
it very likely does), then we could use algorithms like brotli for this.

> envisioned that this would only happen before request bits were sent, e.g.

A specialized deflate encoder for this purpose can use a static code that
is the best fit for the website. The code being static can be a property of
the encoder -- it does not have to be static in the format itself.

> above), or one chooses to not use it. This is described in section 5.2.

Deflate supports these, too. You can define either static entropy code, or
even an uncompressed code.

---

From: Ryan Hamilton <[email-masked]>
Date: Sun, 4 Jan 2015 19:46:26 -0800

This seems like an interesting intellectual discussion. Since HTTP/2 is in
Last Call, it seems like there would need to be a major problem with HPACK
to reopen the header compression algorithm. I'm not seeing anything like
that in this thread.

On Sun, Jan 4, 2015 at 5:20 PM, Jyrki Alakuijala <[email-masked]> wrote:

>> The intent was to make a compressor that was difficult to get wrong from
>> a security perspective, whose implementation was reasonably easy for good
> Yes, but that would be adding bits to a good compression result, instead
> of giving up with compression in the first place. If adding bits works
> (like it very likely does), then we could use algorithms like brotli for
> this.
>

---

From: Martin Thomson <[email-masked]>
Date: Sun, 4 Jan 2015 20:10:32 -0800

> to reopen the header compression algorithm. I'm not seeing anything like

I think that is a fair summary.  There are, in any process like this,
alternatives that are equally valid in the long term, and it could be
that what Jryki is arguing for here is one such alternative.  In this
space, it's definitely not a lack of alternatives that was ever the
problem.  But this particular alternative hasn't been thoroughly
analyzed, and it definitely isn't clear that it is superior either
(Roberto's criteria being those we would judge by, compression
efficiency is definitely low in the priority order).

As Ryan observes, even something superior would be insufficient;
HTTP/2 is done, the only thing that would change that fact is if there
were a demonstrable flaw. I'd add that a change would only occur if
that flaw didn't have a good workaround.

---

From: Willy Tarreau <[email-masked]>
Date: Mon, 5 Jan 2015 08:27:30 +0100

> write than a full zlib implementation. Most likely also easier than HPACK

I think you forgot two important points : zlib is generic and most efficient
when compressing large data sets because it was invented to compress files.
Here we're achieving very good compression ratios on very small sets (a few
tens of bytes to a few hundreds of bytes of input data). In all cases, a
dedicated compressor will be better than a generic compressor when you know
the specific characteristics of your data set (which is the case here). Also,
deflate is slow and not efficiently implemented in software. It uses bit-
aligned data and pattern search which are really inefficient. And storing
the deflate context uses a huge amount of memory. What this would end up with
is people trying to reimplement their own version of the algorithm to try to
save whatever resource they can, leading to significantly more security
issues.

HPACK is simple to implement, simple to understand, byte-aligned and specific
to a single purpose. And even if it were less efficient than any generic
algorithm you would propose, it would always be possible to write a more
efficient one dedicated to this task.

Willy

---

From: Frédéric Kayser <[email-masked]>
Date: Mon, 5 Jan 2015 23:52:28 +0100 (CET)

Hello,
to me the major drawback of HPACK is not really technical, I don't really bother if it could be 20% faster or shrink data even further using topnotch ANS/FSE compression instead of using a compression scheme even older than my parents, it's a bit more philosophical: the length of the Huffman codes* are biased towards a subset of ASCII to the point it becomes pointless to try to compress something that is not plain English and this is a major spit in the face of international users, just put two or three code points that are outside of ASCII and blamo! you take such a huge penalty that you can forget about using compression and go straight to the uncompressed way. This is the 21st century Unicode as taken all over the Web, nowadays IRIs can be written in Japanese, Arabic, Russian or Greek, but deep inside HTTP/2 ASCII and percent-encoded strings still rule (revising RFC 3987 would be welcome a some point). Refrain from using your mother lingo in HTTP/2 headers, it's not open to the wide world of tomorrow since it's based on stats from yesterday.

*30 bits long codes is ridiculous and makes code slower for 32-bits CPU capping them to 16 or 15 bits would have no impact on overall compression (since hitting such large codes would still make it pointless to use). I still don't get why the Huffman part tries to be a universal encoder since in practice it can only really compress a small subset of ASCII and anything else and especially UTF-8 quickly expands, I'd rather see some kind of VLE clearly geared toward this subset (would be more effective) and not trying to be universal at all. This way if the string is only made of code points from the subset and will compress pretty well, otherwise record it uncompressed (don't even try to encode it).

My two cents

---

From: Matthew Kerwin <[email-masked]>
Date: Tue, 6 Jan 2015 09:20:06 +1000

On 6 January 2015 at 08:52, Frédéric Kayser <[email-masked]> wrote:

> Hello,
> to me the major drawback of HPACK is not really technical, I don't really
> bother if it could be 20% faster or shrink data even further using topnotch
> ANS/FSE compression instead of using a compression scheme even older than
> my parents, it's a bit more philosophical: the length of the Huffman codes*
> are biased towards a subset of ASCII to the point it becomes pointless to
> try to compress something that is not plain English and this is a major
> spit in the face of international users, just put two or three code points
> that are outside of ASCII and blamo! you take such a huge penalty that you
> can forget about using compression and go straight to the uncompressed way.
> This is the 21st century Unicode as taken all over the Web, nowadays IRIs
> can be written in Japanese, Arabic, Russian or Greek, but deep inside
> HTTP/2 ASCII and percent-encoded strings still rule (revising RFC 3987
> would be welcome a some point). Refrain from using your mother lingo in
> HTTP/2 headers, it's not open to the wide world of tomorrow since it's
> based on stats from yesterday.
>
> *30 bits long codes is ridiculous and makes code slower for 32-bits CPU
> capping them to 16 or 15 bits would have no impact on overall compression
> (since hitting such large codes would still make it pointless to use). I
> still don't get why the Huffman part tries to be a universal encoder since
> in practice it can only really compress a small subset of ASCII and
> anything else and especially UTF-8 quickly expands, I'd rather see some
> kind of VLE clearly geared toward this subset (would be more effective) and
> not trying to be universal at all. This way if the string is only made of
> code points from the subset and will compress pretty well, otherwise record
> it uncompressed (don't even try to encode it).
>
> My two cents
>
>
I'm pretty sure HPACK was targeted towards a corpus of real world HTTP
data. Since we're not rewriting HTTP semantics (just the way bits are put
on the wire), and since most HTTP headers use (/require) plain ASCII
values, what do we gain by targeting values that aren't in use (/allowed)?

Case in point: whether or not IRIs are a thing, the :path pseudo-header is
explicitly drawn from the *URI*, which is percent-encoded ASCII.

That said, if one day we do rewrite the semantics, and allow UTF-8
everywhere, then by all means compression (among many other things) will
have to be readdressed.

-- 
  Matthew Kerwin
  http://matthew.kerwin.net.au/

---

From: Willy Tarreau <[email-masked]>
Date: Tue, 6 Jan 2015 00:39:14 +0100

Hello Frédéric,

On Mon, Jan 05, 2015 at 11:52:28PM +0100, Frédéric Kayser wrote:
> ANS/FSE compression instead of using a compression scheme even older than my
> parents, it's a bit more philosophical: the length of the Huffman codes* are
> biased towards a subset of ASCII to the point it becomes pointless to try to
> compress something that is not plain English and this is a major spit in the
> face of international users, just put two or three code points that are
> outside of ASCII and blamo! you take such a huge penalty that you can forget
> about using compression and go straight to the uncompressed way. This is the
> 21st century Unicode as taken all over the Web, nowadays IRIs can be written
> in Japanese, Arabic, Russian or Greek, but deep inside HTTP/2 ASCII and
> percent-encoded strings still rule (revising RFC 3987 would be welcome a some
> point). Refrain from using your mother lingo in HTTP/2 headers, it's not open
> to the wide world of tomorrow since it's based on stats from yesterday.

Well, I'd object three things here :
  - most of the header field values are plain ASCII strings or even numbers or
    tokens, so most of them are not subject to i18n ;

  - for header fields containing i18n, you can decide *not* to compress their
    values. It would indeed be foolish to expand their size for no reason when
    you can send them as-is.

  - most of the compression obtained in HPACK comes from its ability to reuse
    header field names and name-value pairs. That's what allows you to compress
    hundreds of bytes into a few bytes, while huffman probably adds a few tens
    of extra percent to the compression ratio.

My personal feeling is that huffman will be useful to compress tokens,
user-agents, maybe cookies since base64 chars are shorter than one byte
here, and time will tell what is relevant to compress or not. I would not
be surprized if some implementations perform a quick test to see what
version is smaller. That's easy, just sum up the huffman bit lengths
for each byte in a value and decide if it's shorter or larger than the
raw version.

So in the end I'm absolutely not worried about huffman causing
inefficiencies in non US-ASCII regions, and to be honnest I even think
that my first implementation may not even implement the huffman encoding
at all (decoding is mandatory though).

My two cents as well :-)

Cheers,
Willy

---

From: Mike Bishop <[email-masked]>
Date: Mon, 5 Jan 2015 23:46:24 +0000

The other point to remember here is that the “compression” attempts to avoid sending literals where possible.  *When a literal must be sent*, it can optionally be Huffman-encoded.  You’re correct that literals which are primarily non-ASCII probably won’t benefit from the Huffman-encoding, but they still benefit from avoiding the literal in the first place.

And Matthew is correct that the code point distribution in the Huffman table is drawn from real-world header usage, which demonstrates a bias toward ASCII.

From: [email-masked] [mailto:[email-masked]] On Behalf Of Matthew Kerwin
Sent: Monday, January 5, 2015 3:20 PM
To: Frédéric Kayser
Cc: [email-masked]
Subject: Re: comments about draft-ietf-httpbis-header-compression

On 6 January 2015 at 08:52, Frédéric Kayser <[email-masked]<mailto:[email-masked]>> wrote:
Hello,
to me the major drawback of HPACK is not really technical, I don't really bother if it could be 20% faster or shrink data even further using topnotch ANS/FSE compression instead of using a compression scheme even older than my parents, it's a bit more philosophical: the length of the Huffman codes* are biased towards a subset of ASCII to the point it becomes pointless to try to compress something that is not plain English and this is a major spit in the face of international users, just put two or three code points that are outside of ASCII and blamo! you take such a huge penalty that you can forget about using compression and go straight to the uncompressed way. This is the 21st century Unicode as taken all over the Web, nowadays IRIs can be written in Japanese, Arabic, Russian or Greek, but deep inside HTTP/2 ASCII and percent-encoded strings still rule (revising RFC 3987 would be welcome a some point). Refrain from using your mother lingo in HTTP/2 headers, it's not open to the wide world of tomorrow since it's based on stats from yesterday.

My two cents

I'm pretty sure HPACK was targeted towards a corpus of real world HTTP data. Since we're not rewriting HTTP semantics (just the way bits are put on the wire), and since most HTTP headers use (/require) plain ASCII values, what do we gain by targeting values that aren't in use (/allowed)?

Case in point: whether or not IRIs are a thing, the :path pseudo-header is explicitly drawn from the *URI*, which is percent-encoded ASCII.

That said, if one day we do rewrite the semantics, and allow UTF-8 everywhere, then by all means compression (among many other things) will have to be readdressed.

---

From: Michael Sweet <[email-masked]>
Date: Mon, 05 Jan 2015 20:33:12 -0500

That would be a valid complaint if HTTP fields could safely carry Unicode/UTF-8 text values, but they can't.  See the mailing list archives for long discussions on the topic...

> On Jan 5, 2015, at 5:52 PM, Frédéric Kayser <[email-masked]> wrote:
> 
> Hello,

_________________________________________________________
Michael Sweet, Senior Printing System Engineer, PWG Chair

---

From: RUELLAN Herve <[email-masked]>
Date: Tue, 6 Jan 2015 09:17:28 +0000

Yes, the http2 compressor in the compression test is much out-of-date :-(

Hervé.

> -----Original Message-----
> From: Mark Nottingham [mailto:[email-masked]]
> Sent: samedi 3 janvier 2015 18:25
> To: Jyrki Alakuijala
> Cc: Dave Garrett; [email-masked]
> This is what we used to help make the initial selection; I don’t believe that the
> compressor there has been updated to exactly match the spec; e.g., it doesn’t
> do huffman (Herve?).
> 
> Cheers,
> 
> 
> > If the goal is to just make an algorithm that can work with a static entropy
> code with a static dictionary and no LZ77 outside the static dictionary, the
> current format (deflate) needs no changes. Deflate supports all these concepts.
> You only need a new encoder -- although zlib with setting a dictionary and
> running it with quality == 1 is a pretty close match already, only the static
> entropy coding is missing then.
> >

---

From: Dave Garrett <[email-masked]>
Date: Wed, 31 Dec 2014 18:53:15 +0000

Dave