Subject: Choosing a header compression algorithm

From: Mark Nottingham <[email-masked]>
Date: Thu, 21 Mar 2013 18:11:26 +1100

Previously, we've talked about starting with just a delta-encoding approach for our first implementation draft. In Orlando, we focused primarily on two proposals:

* Delta2
  Draft: http://tools.ietf.org/html/draft-rpeon-httpbis-header-compression-03
  Python Implementation: https://github.com/http2/compression-test/tree/master/compressor/delta2

* HeaderDiff
  Draft: http://tools.ietf.org/html/draft-ruellan-headerdiff-00
  Python Implementation: https://github.com/http2/compression-test/tree/master/compressor/headerdiff

As I understand it, Herve et al want to work on making HeaderDiff more resistant to CRIME, and hopefully we'll see the results of that in the very near future. 

In the meantime, I'd like everyone to become familiar with both drafts and the characteristics of their implementations, so that we can have an informed discussion of them.

I'd like to see a few things happen while we do this:

1) We need to do apples-to-apples comparison of these compressors to see how they behave under a range of constraints (especially, memory).

2) I'd like us to verify that they are respecting those constraints, and that they're implemented in an equivalent way (this is likely to be manual).

3) It would be very good to have a test suite that verifies that they correctly reconstitute the semantically significant parts of the headers; in particular, large/unusual values, ordering where appropriate, etc. Our current header corpus undoubtedly has holes in this regard.

If you make any progress along these lines (dare I ask for volunteers?), pleas share with the list.

Looking at our issues list, this is one of the major items preventing us from getting to a first implementation draft, so I'd like to chose a way forward soon -- especially since we're choosing a starting point, and the approach we take can evolve or, if necessary, be replaced.

Regards,

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

---

From: RUELLAN Herve <[email-masked]>
Date: Thu, 21 Mar 2013 11:35:14 +0000

To help everyone better understand the two proposals, I tried to make a comparison of the different mechanisms they use.

* Buffers:
Delta has a static pre-filled (name, value) buffer and a dynamic (name, value) buffer. The size of the dynamic buffer can be limited.
HeaderDiff has a pre-filled name buffer (which is extendable to include new header names) and a dynamic (name, value) buffer. The size of the dynamic buffer can be limited.

* Buffer management for additions:
Delta: the encoder decides whether a new entry is added to the buffer or not.
HeaderDiff: the encoder decides whether a new entry is added to the buffer or not.

* Buffer management for removals:
Delta: the buffer uses a LRU mechanisms to find which entry is removed from the buffer to fulfill the size limitation when a new entry is added to the buffer.
HeaderDiff: the removals of entries from the buffer are at encoder discretion, as long as size limitation are fulfilled (the algorithm used in the implementation is loosely based on LRU).

* Buffer management synchronization between Encoder and Decoder:
Delta: the same algorithm is used on both sides.
HeaderDiff: all buffer updates are transmitted on the wire.

* Default for a new header set:
Delta: the default for a new header set is the previous header set. A header can be removed from the set by encoding it as an index. Delta supports up to 256 different header sets.
HeaderDiff: the default for a new header set is the empty set.

* Encoding possibilities:
Delta supports the following encoding possibilities:
- (Name, Value) index;
- (Name, Value) index list;
- Name index and literal Value;
- Literal Name and literal Value.
HeaderDiff supports the following encoding possibilities:
- (Name, Value) index;
- Name index and literal Value;
- Literal Name and literal Value;
- delta-encoding: (Name, Value) index, with a shared prefix and a new suffix for the Value.

* Encoding choice representation:
Delta uses opcodes, that are encoded as the opcode identifier (1 byte) and the number of encoded headers (1 byte).
HeaderDiff uses a few bits (2-4) in the encoding of each header.
Both proposals are byte-aligned at the header level.

* String encoding:
Delta uses a static Huffman encoding.
HeaderDiff uses a raw literal encoding.
Both proposals could easily support several types of encoding: raw literal, static Huffman, typed codecs...

I hoped I capture correctly the differences and similarities between the two proposals. 
Roberto, if you see any misunderstanding of Delta, you're welcome to correct it.

I'm going to details the reasons of our design choices in further e-mails.

Regards,

Hervé.

> -----Original Message-----
> From: Mark Nottingham [mailto:[email-masked]]
> Sent: jeudi 21 mars 2013 08:11
> To: [email-masked] Group
> Subject: Choosing a header compression algorithm
> 
> Previously, we've talked about starting with just a delta-encoding approach
> for our first implementation draft. In Orlando, we focused primarily on two
> proposals:
> 
> * Delta2
> As I understand it, Herve et al want to work on making HeaderDiff more
> resistant to CRIME, and hopefully we'll see the results of that in the very near
> future.
> 
> In the meantime, I'd like everyone to become familiar with both drafts and
> the characteristics of their implementations, so that we can have an
> informed discussion of them.
> 
> 1) We need to do apples-to-apples comparison of these compressors to see
> how they behave under a range of constraints (especially, memory).
> 
> 2) I'd like us to verify that they are respecting those constraints, and that
> they're implemented in an equivalent way (this is likely to be manual).
> 
> 3) It would be very good to have a test suite that verifies that they correctly
> reconstitute the semantically significant parts of the headers; in particular,
> large/unusual values, ordering where appropriate, etc. Our current header
> corpus undoubtedly has holes in this regard.
> 
> Looking at our issues list, this is one of the major items preventing us from
> getting to a first implementation draft, so I'd like to chose a way forward
> soon -- especially since we're choosing a starting point, and the approach we
> take can evolve or, if necessary, be replaced.
> 
> Regards,
> 
> --

---

From: Stephen Farrell <[email-masked]>
Date: Thu, 21 Mar 2013 15:40:46 +0000

Hiya,

I've a question. It might be silly or maybe just one to
punt on for later, but just in case...

If HTTP/2.0 does header compression, and if some form of
header authentication (e.g. a DKIM-like thing, as recently
proposed for iSchedule) were to be standardised, should
the authentication cover the compressed or uncompressed
headers?

The former would seem to be bad when considering APIs,
but the latter might mean that canonicalisation needs to
be considered when picking a compression alg.

The kind of canonicalisation requirement might be that
you need to ensure one can define a reasonable c14n
function such that c14n(X)=c14n(uncompress(compress(X)).

Mark's item 3 below triggered this, I guess one could
argue that it might be a requirement for compression
that it not break higher level canonicalisation which
isn't quite the same as being able to reconstitute the
semantics. (For example, with timestamps that specify
a zero TZ offset, or list ordering maybe.)

Ta,
S.

PS: Apologies if this is all obvious when one reads
the algorithm descriptions, which I've not;-)

---

From: James M Snell <[email-masked]>
Date: Thu, 21 Mar 2013 12:50:35 -0700

On Mar 21, 2013 8:42 AM, "Stephen Farrell" <[email-masked]>
wrote:
[snip]
> function such that c14n(X)=c14n(uncompress(compress(X)).

I think this is going to be the best we can do really. There is no way the
compression algorithms discussed thus far can preserve c14n. At best,
you'll have to reapply c14n after decompression and reconstitution of the
header set.

- james

> > Previously, we've talked about starting with just a delta-encoding
approach for our first implementation draft. In Orlando, we focused
primarily on two proposals:
> >   Draft:
http://tools.ietf.org/html/draft-rpeon-httpbis-header-compression-03
> >   Python Implementation:
https://github.com/http2/compression-test/tree/master/compressor/delta2
> >   Python Implementation:
https://github.com/http2/compression-test/tree/master/compressor/headerdiff
> > As I understand it, Herve et al want to work on making HeaderDiff more
resistant to CRIME, and hopefully we'll see the results of that in the very
near future.
> >
> > In the meantime, I'd like everyone to become familiar with both drafts
and the characteristics of their implementations, so that we can have an
informed discussion of them.
> > 1) We need to do apples-to-apples comparison of these compressors to
see how they behave under a range of constraints (especially, memory).
> >
> > 2) I'd like us to verify that they are respecting those constraints,
and that they're implemented in an equivalent way (this is likely to be
manual).
> >
> > 3) It would be very good to have a test suite that verifies that they
correctly reconstitute the semantically significant parts of the headers;
in particular, large/unusual values, ordering where appropriate, etc. Our
current header corpus undoubtedly has holes in this regard.
> > Looking at our issues list, this is one of the major items preventing
us from getting to a first implementation draft, so I'd like to chose a way
forward soon -- especially since we're choosing a starting point, and the
approach we take can evolve or, if necessary, be replaced.

---

From: Roberto Peon <[email-masked]>
Date: Thu, 21 Mar 2013 17:06:56 -0400

That is basically correct, assuming we're talking about delta2.
-=R

On Thu, Mar 21, 2013 at 7:35 AM, RUELLAN Herve
<[email-masked]>wrote:

> To help everyone better understand the two proposals, I tried to make a
> comparison of the different mechanisms they use.
>
> * Buffers:
> Delta has a static pre-filled (name, value) buffer and a dynamic (name,
> value) buffer. The size of the dynamic buffer can be limited.
> HeaderDiff has a pre-filled name buffer (which is extendable to include
> new header names) and a dynamic (name, value) buffer. The size of the
> dynamic buffer can be limited.
>
> Delta: the buffer uses a LRU mechanisms to find which entry is removed
> from the buffer to fulfill the size limitation when a new entry is added to
> the buffer.
> HeaderDiff: the removals of entries from the buffer are at encoder
> discretion, as long as size limitation are fulfilled (the algorithm used in
> the implementation is loosely based on LRU).
>
> Delta: the default for a new header set is the previous header set. A
> header can be removed from the set by encoding it as an index. Delta
> supports up to 256 different header sets.
> approach
> and
> correctly
> > If you make any progress along these lines (dare I ask for volunteers?),
> pleas
> > share with the list.
> >

---

From: Mark Nottingham <[email-masked]>
Date: Fri, 22 Mar 2013 17:32:06 +1100

> 1) We need to do apples-to-apples comparison of these compressors to see how they behave under a range of constraints (especially, memory).

To this point, a few runs across the header corpus that I collected (http_samples/mnot/*.har), using the current implementations (again, we need to verify these are honouring these limits correctly, and I believe headerdiff is going to be updated):

16384 Byte Buffer
----------------------

* TOTAL: 5948 req messages
                                        size  time | ratio min   max   std
                         http1     3,460,925  0.22 | 1.00  1.00  1.00  0.00
  delta2 (max_byte_size=16384)       630,668 15.89 | 0.18  0.03  0.76  0.11
     headerdiff (buffer=16384)     1,699,918  9.65 | 0.49  0.03  0.90  0.21

* TOTAL: 5948 res messages
                                        size  time | ratio min   max   std
                         http1     2,186,162  0.26 | 1.00  1.00  1.00  0.00
  delta2 (max_byte_size=16384)       575,345 24.39 | 0.26  0.02  1.06  0.12
     headerdiff (buffer=16384)       877,106 24.76 | 0.40  0.04  0.93  0.14

[ Note that the efficiency actually goes *down* on headerdiff for requests when the buffer is larger here; Herve, any idea what's happening there? ]

8192 Byte Buffer
----------------------

* TOTAL: 5948 req messages
                                       size  time | ratio min   max   std
                        http1     3,460,925  0.24 | 1.00  1.00  1.00  0.00
  delta2 (max_byte_size=8192)       646,431 15.78 | 0.19  0.03  0.76  0.12
     headerdiff (buffer=8192)     1,378,622  6.95 | 0.40  0.03  0.92  0.20

* TOTAL: 5948 res messages
                                       size  time | ratio min   max   std
                        http1     2,186,162  0.43 | 1.00  1.00  1.00  0.00
  delta2 (max_byte_size=8192)       592,260 20.28 | 0.27  0.02  1.06  0.12
     headerdiff (buffer=8192)       914,362 15.55 | 0.42  0.05  0.93  0.14

4096 Byte Buffer
----------------------

* TOTAL: 5948 req messages
                                       size  time | ratio min   max   std
                        http1     3,460,925  0.18 | 1.00  1.00  1.00  0.00
  delta2 (max_byte_size=4096)       665,642 13.35 | 0.19  0.03  0.77  0.12
     headerdiff (buffer=4096)     1,406,429  3.92 | 0.41  0.03  0.88  0.18

* TOTAL: 5948 res messages
                                       size  time | ratio min   max   std
                        http1     2,186,162  0.21 | 1.00  1.00  1.00  0.00
  delta2 (max_byte_size=4096)       610,764 15.48 | 0.28  0.02  1.06  0.13
     headerdiff (buffer=4096)     1,009,185  7.58 | 0.46  0.05  0.93  0.13

2048 Byte Buffer
----------------------

* TOTAL: 5948 req messages
                                       size  time | ratio min   max   std
                        http1     3,460,925  0.18 | 1.00  1.00  1.00  0.00
  delta2 (max_byte_size=2048)       692,579 11.66 | 0.20  0.03  0.77  0.12
     headerdiff (buffer=2048)     1,632,783  2.94 | 0.47  0.03  0.90  0.19

* TOTAL: 5948 res messages
                                       size  time | ratio min   max   std
                        http1     2,186,162  0.20 | 1.00  1.00  1.00  0.00
  delta2 (max_byte_size=2048)       633,785 12.47 | 0.29  0.02  1.22  0.13
     headerdiff (buffer=2048)     1,088,829  4.75 | 0.50  0.05  0.93  0.13

1024 Byte Buffer
----------------------

* TOTAL: 5948 req messages
                                       size  time | ratio min   max   std
                        http1     3,460,925  0.22 | 1.00  1.00  1.00  0.00
  delta2 (max_byte_size=1024)       752,380 11.92 | 0.22  0.03  0.84  0.13
     headerdiff (buffer=1024)     1,700,325  1.82 | 0.49  0.03  0.91  0.19

* TOTAL: 5948 res messages
                                       size  time | ratio min   max   std
                        http1     2,186,162  0.23 | 1.00  1.00  1.00  0.00
  delta2 (max_byte_size=1024)       671,975 11.42 | 0.31  0.02  1.22  0.13
     headerdiff (buffer=1024)     1,118,599  3.53 | 0.51  0.05  0.93  0.13

512 Byte Buffer
---------------------

* TOTAL: 5948 req messages
                                      size  time | ratio min   max   std
                       http1     3,460,925  0.17 | 1.00  1.00  1.00  0.00
  delta2 (max_byte_size=512)     1,058,090 14.23 | 0.31  0.04  0.83  0.15
     headerdiff (buffer=512)     2,120,833  1.43 | 0.61  0.03  0.93  0.16

* TOTAL: 5948 res messages
                                      size  time | ratio min   max   std
                       http1     2,186,162  0.14 | 1.00  1.00  1.00  0.00
  delta2 (max_byte_size=512)       721,525 12.22 | 0.33  0.03  1.22  0.13
     headerdiff (buffer=512)     1,199,608  2.09 | 0.55  0.05  0.93  0.12

256 Byte Buffer
---------------------

* TOTAL: 5948 req messages
                                      size  time | ratio min   max   std
                       http1     3,460,925  0.18 | 1.00  1.00  1.00  0.00
  delta2 (max_byte_size=256)     1,517,520 18.62 | 0.44  0.04  0.84  0.19
     headerdiff (buffer=256)     2,444,376  1.32 | 0.71  0.08  0.95  0.13

* TOTAL: 5948 res messages
                                      size  time | ratio min   max   std
                       http1     2,186,162  0.23 | 1.00  1.00  1.00  0.00
  delta2 (max_byte_size=256)       856,632 13.21 | 0.39  0.04  1.22  0.14
     headerdiff (buffer=256)     1,201,814  1.65 | 0.55  0.05  0.93  0.12

32 Byte Buffer
-------------------

* TOTAL: 5948 req messages
                                     size  time | ratio min   max   std
                      http1     3,460,925  0.20 | 1.00  1.00  1.00  0.00
  delta2 (max_byte_size=32)     2,357,457 28.18 | 0.68  0.51  0.84  0.05
     headerdiff (buffer=32)     2,791,039  1.16 | 0.81  0.58  0.96  0.08

* TOTAL: 5948 res messages
                                     size  time | ratio min   max   std
                      http1     2,186,162  0.21 | 1.00  1.00  1.00  0.00
  delta2 (max_byte_size=32)     1,197,019 17.92 | 0.55  0.16  0.89  0.07
     headerdiff (buffer=32)     1,434,721  1.32 | 0.66  0.19  0.95  0.07

[ smaller buffer sizes caused errors in delta2 (at least) ]

---

From: Roberto Peon <[email-masked]>
Date: Fri, 22 Mar 2013 02:43:59 -0400

I need to check in the newest version of the code which fixes that...
-=R

On Fri, Mar 22, 2013 at 2:32 AM, Mark Nottingham <[email-masked]> wrote:

> To this point, a few runs across the header corpus that I collected
> (http_samples/mnot/*.har), using the current implementations (again, we
> need to verify these are honouring these limits correctly, and I believe
> headerdiff is going to be updated):
>
> 16384 Byte Buffer
> ----------------------
>
> [ Note that the efficiency actually goes *down* on headerdiff for requests
> when the buffer is larger here; Herve, any idea what's happening there? ]
>
> 8192 Byte Buffer
> ----------------------
>

---

From: RUELLAN Herve <[email-masked]>
Date: Fri, 22 Mar 2013 13:01:46 +0000

The results for HeaderDiff were not at all those I excepted.

I traced the difference to the number of compressor instances used to compress the sample files. The framework uses only one instance for all the files, while internally I used one instance for each file.

I noticed that the delta2 compressor seems to use one compression context for each host. I think this is the correct behavior to obtain realistic results. I will therefore update the HeaderDiff codec to create one compression context per host.

Hervé. 

> Sent: vendredi 22 mars 2013 07:32
> Subject: Re: Choosing a header compression algorithm
> 
>

---

From: Roberto Peon <[email-masked]>
Date: Fri, 22 Mar 2013 13:45:43 -0400

Correct, delta2 uses a header group per host, however, the real benefits of
this don't show up with the current streamifier, which removes the
intermingling of requests to different hosts (which is a bit unrealistic,
but does makes the graphs easier to parse visually).
This can end up really mattering to the compression in the cases where
there is some ping-ponging between different host headers.

-=R

On Fri, Mar 22, 2013 at 9:01 AM, RUELLAN Herve
<[email-masked]>wrote:

> I traced the difference to the number of compressor instances used to
> compress the sample files. The framework uses only one instance for all the
> files, while internally I used one instance for each file.
>
> I noticed that the delta2 compressor seems to use one compression context
> for each host. I think this is the correct behavior to obtain realistic
> results. I will therefore update the HeaderDiff codec to create one
> compression context per host.
>
> Hervé.
>

---

From: RUELLAN Herve <[email-masked]>
Date: Fri, 22 Mar 2013 18:04:25 +0000

I think it would be good to move this from the compressors to the streamifier. In addition, it would be interesting to look at a more realistic streamifier that could for example unshard hosts (expecting that HTTP/2.0 will remove the sharding currently done by server developers).

Hervé.

From: Roberto Peon [mailto:[email-masked]]
Sent: vendredi 22 mars 2013 18:46
To: RUELLAN Herve
Cc: Mark Nottingham; [email-masked] Group
Subject: Re: Choosing a header compression algorithm

Correct, delta2 uses a header group per host, however, the real benefits of this don't show up with the current streamifier, which removes the intermingling of requests to different hosts (which is a bit unrealistic, but does makes the graphs easier to parse visually).
This can end up really mattering to the compression in the cases where there is some ping-ponging between different host headers.

-=R

On Fri, Mar 22, 2013 at 9:01 AM, RUELLAN Herve <[email-masked]<mailto:[email-masked]>> wrote:
The results for HeaderDiff were not at all those I excepted.

Hervé.

> From: Mark Nottingham [mailto:[email-masked]<mailto:[email-masked]>]
> To: [email-masked]<mailto:[email-masked]> Group
> On 21/03/2013, at 6:11 PM, Mark Nottingham <[email-masked]<mailto:[email-masked]>> wrote:
>

---

From: Martin Thomson <[email-masked]>
Date: Fri, 22 Mar 2013 13:12:36 -0700

On 22 March 2013 10:45, Roberto Peon <[email-masked]> wrote:
> This can end up really mattering to the compression in the cases where there
> is some ping-ponging between different host headers.

Isn't this only a concern/advantage for the hop between a client and a
client-side proxy?  Requests toward different hosts are going to be on
their own connections in all other situations.  Origin servers are
unlikely to see any benefits from improved compression between hosts.

The question of reuse of a connection for different authorities is
still unresolved.  I know that  this is on some people's minds, but we
haven't seen any proposals, nor do I think we're ready to go there
just yet.

---

From: Roberto Peon <[email-masked]>
Date: Fri, 22 Mar 2013 20:24:40 -0400

Ya, connection management and compression are linked.

Sharing of connections when both the cert and the DNS resolution match is
something that is done today for SPDY and which does reduce latency
(generally by at least 2 RTT but often effectively more due to slow start,
etc. ) as well as reducing connection counts, server load, etc.

In SPDY4, we'll be experimenting with policy w.r.t. connection sharing, as
what exists today is both too much or too little, depending on what one
wants, but the latency (etc.) savings are likely to be compelling.

The proxy case is another where this matters, as you point out, but that
isn't where the biggest win has been so far since there has been
significant experience with that mode of operation yet (unless Amazon
speaks up!). It is an interesting case though.

-=R
On Mar 22, 2013 1:12 PM, "Martin Thomson" <[email-masked]> wrote:

> there

---

From: Mark Nottingham <[email-masked]>
Date: Mon, 25 Mar 2013 16:33:56 +1100

After Herve's most recent pull request, this:

> 4096 Byte Buffer

becomes:

* TOTAL: 5948 req messages
                                       size  time | ratio min   max   std
                        http1     3,460,925  0.24 | 1.00  1.00  1.00  0.00
  delta2 (max_byte_size=4096)       665,642 12.21 | 0.19  0.03  0.77  0.12
     headerdiff (buffer=4096)       944,716  1.23 | 0.27  0.01  0.96  0.23

* TOTAL: 5948 res messages
                                       size  time | ratio min   max   std
                        http1     2,186,162  0.25 | 1.00  1.00  1.00  0.00
  delta2 (max_byte_size=4096)       610,764 13.41 | 0.28  0.02  1.06  0.13
     headerdiff (buffer=4096)       584,188  4.45 | 0.27  0.02  0.92  0.18

with the invocation:

> ./compare_compressors.py -c delta2=max_byte_size=4096 -c headerdiff=buffer=4096 ../http_samples/mnot/*.har

Herve, before I re-run everything*, what other flags are appropriate (esp. considering the discussion around CRIME)?

Cheers,

* Yes, we should discuss the streamifier first, too.

---

From: Mark Nottingham <[email-masked]>
Date: Mon, 25 Mar 2013 16:55:36 +1100

> I think it would be good to move this from the compressors to the streamifier. In addition, it would be interesting to look at a more realistic streamifier that could for example unshard hosts (exp…

Right now, it combines all requests to the same TLD (according to the Public Suffix List) into a single "connection." Do you have a suggestion for how to do it better?

I've just pushed a quick and dirty fix to use a new instance of each compressor for each connection; the results are pretty even between headerdiff and delta2, with a small increase in each:

* TOTAL: 5948 req messages
                                       size  time | ratio min   max   std
                        http1     3,460,925  0.18 | 1.00  1.00  1.00  0.00
  delta2 (max_byte_size=4096)       707,901 11.87 | 0.20  0.03  0.83  0.15
     headerdiff (buffer=4096)       960,106  1.65 | 0.28  0.01  0.96  0.23

* TOTAL: 5948 res messages
                                       size  time | ratio min   max   std
                        http1     2,186,162  0.28 | 1.00  1.00  1.00  0.00
  delta2 (max_byte_size=4096)       622,837 12.86 | 0.28  0.02  1.22  0.13
     headerdiff (buffer=4096)       596,290  3.65 | 0.27  0.02  0.92  0.18

Cheers,

---

From: RUELLAN Herve <[email-masked]>
Date: Mon, 25 Mar 2013 17:21:30 +0000

> Sent: lundi 25 mars 2013 06:56
> To: RUELLAN Herve
> Cc: Roberto Peon; [email-masked] Group
> > I think it would be good to move this from the compressors to the
> streamifier. In addition, it would be interesting to look at a more realistic
> streamifier that could for example unshard hosts (expecting that HTTP/2.0
> will remove the sharding currently done by server developers).
> 
> Right now, it combines all requests to the same TLD (according to the Public
> Suffix List) into a single "connection." Do you have a suggestion for how to do
> it better?

I think this should provide some "realistic" results as a starting point. Depending on what we want to measure, we may want to refine this a bit.

Hervé.

> I've just pushed a quick and dirty fix to use a new instance of each
> compressor for each connection; the results are pretty even between
> headerdiff and delta2, with a small increase in each:
>

---

From: Roberto Peon <[email-masked]>
Date: Mon, 25 Mar 2013 11:38:44 -0700

There are two obvious strategies here: What we do now, and using what SPDY
does today (share connections if the certs match and DNS resolution of the
new hostname overlaps with those of the current connection).

-=R

On Mon, Mar 25, 2013 at 10:21 AM, RUELLAN Herve
<[email-masked]>wrote:

> I think this should provide some "realistic" results as a starting point.
> Depending on what we want to measure, we may want to refine this a bit.
>
> Hervé.
>

---

From: Roberto Peon <[email-masked]>
Date: Mon, 25 Mar 2013 17:22:45 -0700

Herve--

We need an option which disables prefix matching on the HeaderDiff
compressor. The strategies I see in the code still allow many headers to be
attacked (if they include commas).
I believe that it is still possible to probe interesting data out of
various fields of the URL, for example, or even cookies, assuming they
aren't B64 encoded.

-=R

On Mon, Mar 25, 2013 at 11:38 AM, Roberto Peon <[email-masked]> wrote:

> On Mon, Mar 25, 2013 at 10:21 AM, RUELLAN Herve <
> [email-masked]> wrote:
>

---

From: RUELLAN Herve <[email-masked]>
Date: Tue, 26 Mar 2013 09:11:44 +0000

Roberto,

Prefix matching can be disabled by using the "delta=false" option.

There are two new strategies for prefix matching. The first one is limiting which shared prefixes are used. The last character of a shared prefix must belong to a predefined set of characters. An example of predefined set of characters is "/?=, " (with a space as the last character). For example, for the following URLs:
http://www.example.com/path/first/myfile
http://www.example.com/path/final/otherfile
With the default strategy for prefix matching, the shared prefix would be:
http://www.example.com/path/fi
With the constraints upon the end of the shared prefix, the shared prefix is:
http://www.example.com/path/
This prevents CRIME-like attacks from guessing a value character by character. Therefore we think that using this new strategy, prefix matching is not vulnerable to CRIME-like attacks. In fact, using this strategy, we are enabling some kind of fine-grained indexing of values, where well defined parts of a value can be referred to.

The second strategy is to limit the number of times a given header value can be used as a reference for prefix matching. This limitation can be very low: limiting this usage as a reference to 2 times is already sufficient to get most of the performances of prefix matching. We think that with this strategy, prefix matching is mostly protected from CRIME-like attack.

The first strategy can be selected using the "delta_type='/?= \coma'" option (possibly changing the prefix ending characters).
The second strategy can be selected using the "delta_type=2" option (or with another value).

I'm planning update the HeaderDiff codec to using the first strategy by default.

Hervé. 

From: Roberto Peon [mailto:[email-masked]] 
Sent: mardi 26 mars 2013 01:23
To: RUELLAN Herve; [email-masked]
Cc: Mark Nottingham; [email-masked] Group
Subject: Re: Choosing a header compression algorithm

Herve--

We need an option which disables prefix matching on the HeaderDiff compressor. The strategies I see in the code still allow many headers to be attacked (if they include commas).
I believe that it is still possible to probe interesting data out of various fields of the URL, for example, or even cookies, assuming they aren't B64 encoded.

-=R

On Mon, Mar 25, 2013 at 11:38 AM, Roberto Peon <[email-masked]> wrote:
There are two obvious strategies here: What we do now, and using what SPDY does today (share connections if the certs match and DNS resolution of the new hostname overlaps with those of the current connection).

-=R

Hervé.

---

From: Roberto Peon <[email-masked]>
Date: Tue, 26 Mar 2013 11:10:35 -0700

Awesome! I missed the =none part when looking at the code!

I think we have a difference of opinion about whether or not the two
variations on prefix matching are safe.
I don't think they are. :)

I can clear the compression context (in a variety of ways, one obvious way
being to force a connection shutdown, another being to cause the
compression context to be cleared by sending tons new data) and then I can
cause prefix matches to occur in the "limit" strategy case, allowing the
attacker to verify hypotheses about which characters are in whatever fields.

In the pre-defined-terminal-character case, we can still attack various
fields successfully, so long as they terminate in the characters you've
specified. There is no guarantee that important data is delimited by these
fields (though I agree it often is), and so I don't think we can state that
it is providing a long-term security benefit without restricting the use of
these characters in all header fields.

Splitting cookies into the crumbs is safe, since we know that is a feature
of that specific field, and doing similar atom-based matching on other
fields where we have a guarantee on the delimiter is likely safe, but
prefix matching as you have it (with either strategy) can still be attacked.

-=R

On Tue, Mar 26, 2013 at 2:11 AM, RUELLAN Herve
<[email-masked]>wrote:

> There are two new strategies for prefix matching. The first one is
> limiting which shared prefixes are used. The last character of a shared
> prefix must belong to a predefined set of characters. An example of
> predefined set of characters is "/?=, " (with a space as the last
> character). For example, for the following URLs:
> This prevents CRIME-like attacks from guessing a value character by
> character. Therefore we think that using this new strategy, prefix matching
> is not vulnerable to CRIME-like attacks. In fact, using this strategy, we
> are enabling some kind of fine-grained indexing of values, where well
> defined parts of a value can be referred to.
>
> The second strategy is to limit the number of times a given header value
> can be used as a reference for prefix matching. This limitation can be very
> low: limiting this usage as a reference to 2 times is already sufficient to
> get most of the performances of prefix matching. We think that with this
> strategy, prefix matching is mostly protected from CRIME-like attack.
>
> The first strategy can be selected using the "delta_type='/?= \coma'"
> option (possibly changing the prefix ending characters).

---

From: Roberto Peon <[email-masked]>
Date: Wed, 27 Mar 2013 17:14:54 -0700

I've checked in some changes to delta2 which expands and documents various
options for delta2 in the README.md.

After running a number of variations of delta2, The following defaults look
good for small buffer sizes:

delta2=max_entries=256, small_index=1

small_index basically says use a uint8 instead of a uint16 for representing
indices, and is the kind of thing that could be messaged somewhere (opcode,
flag, whatever).

The best headerdiff option which I believe is safe against CRIME in the
future is:
  headerdiff=delta_type=false,huffman

I removed prefix matching from delta some months ago (~6 I think?) after
cogitating on it for a while and then speaking with security folks.. I just
couldn't come up with a way I could prove was safe, unlike the
atom-matching, which one can prove is no worse than a brute-force attack.

I've appended runs with these values@4k buffer size for delta2 and
headerdiff below.
-=R

* TOTAL: 5949 req messages

                           http1     3,460,925  0.13 | 1.00  1.00  1.00
 0.00
  delta2 (max_byte_size=4096, max_entries=256, small_index=1, hg_adjust=0,
implicit_hg_add=0, refcnt_vals=0)       664,683  4.16 | 0.19  0.02  0.83
 0.15
                                                         headerdiff
(buffer=4096, delta_type=false, huffman)       759,783  2.03 | 0.22  0.01
 0.78  0.18

                           http1     2,186,162  0.12 | 1.00  1.00  1.00
 0.00
  delta2 (max_byte_size=4096, max_entries=256, small_index=1, hg_adjust=0,
implicit_hg_add=0, refcnt_vals=0)       585,475  5.32 | 0.27  0.02  1.28
 0.13
                                                         headerdiff
(buffer=4096, delta_type=false, huffman)       543,047  3.29 | 0.25  0.02
 0.73  0.14

---

From: Roberto Peon <[email-masked]>
Date: Wed, 27 Mar 2013 17:21:19 -0700

Arg. Sorry, the best provably safe option for HeaderDiff is:

*headerdiff (buffer=4096, delta=false, huffman)*

* TOTAL: 5949 req messages
                                                          size  time |
ratio min   max   std
                                           http1     3,460,925  0.22 | 1.00
 1.00  1.00  0.00
           headerdiff (buffer=4096, delta=false)     1,250,042  0.64 | 0.36
 0.01  0.96  0.22
  headerdiff (buffer=4096, delta=false, huffman)       936,003  2.05 | 0.27
 0.01  0.79  0.16

* TOTAL: 5948 res messages
                                                          size  time |
ratio min   max   std
                                           http1     2,186,162  0.08 | 1.00
 1.00  1.00  0.00
           headerdiff (buffer=4096, delta=false)       768,387  2.16 | 0.35
 0.02  0.92  0.18
  headerdiff (buffer=4096, delta=false, huffman)       581,046  3.22 | 0.27
 0.02  0.73  0.14

On Wed, Mar 27, 2013 at 5:14 PM, Roberto Peon <[email-masked]> wrote:

> After running a number of variations of delta2, The following defaults
> look good for small buffer sizes:
>
> small_index basically says use a uint8 instead of a uint16 for
> representing indices, and is the kind of thing that could be messaged
> somewhere (opcode, flag, whatever).
>

---

From: James M Snell <[email-masked]>
Date: Wed, 27 Mar 2013 17:29:12 -0700

> delta2=max_entries=256, small_index=1

Oh excellent. I had hit on this as well. To be honest, I'm not sure
max_entry > 256 would ever really make much practical sense.

- James

> http1     3,460,925  0.13 | 1.00  1.00  1.00  0.00
> http1     2,186,162  0.12 | 1.00  1.00  1.00  0.00

---

From: Roberto Peon <[email-masked]>
Date: Wed, 27 Mar 2013 17:46:28 -0700

For larger buffer sizes, it can make a fair difference, but it is an easy
thing to change, for sure.
-=R

On Wed, Mar 27, 2013 at 5:29 PM, James M Snell <[email-masked]> wrote:

> representing

---

From: RUELLAN Herve <[email-masked]>
Date: Thu, 28 Mar 2013 16:56:29 +0000

> Sent: mardi 26 mars 2013 19:11
> To: RUELLAN Herve
> Cc: [email-masked]; Mark Nottingham; [email-masked] Group

>From my point of view, the initial version of prefix matching is some kind of lightweight Deflate, and as so is not safe (even though it's probably safer than Deflate).
The limited prefix matching is some kind of indexing where you allow matching a whole value or some well-defined subparts of it. The limitations implied by the algorithm prevent from guessing a subpart character by character. Therefore I think this is safe.

> attacker to verify hypotheses about which characters are in whatever fields.

The sole information an attacker can get is whether he has guessed a whole subpart or not. The definition of subparts is fixed, therefore he can't take advantage of changing subparts to easily guess a value.

For example, for the targeted URL:
 	http://www.example.com/path/first/myfile

The URL:
 	http://www.example.com/path/final/otherfile
Will only leak the information that the match is: "http://www.example.com/path/".

The CRIME attack tactics is once " http://www.example.com/path/" is known to guess the next character. However, with limited prefix encoding any value with one more character will use the same shared prefix.

> In the pre-defined-terminal-character case, we can still attack various fields
> successfully, so long as they terminate in the characters you've specified.
> There is no guarantee that important data is delimited by these fields
> (though I agree it often is), and so I don't think we can state that it is
> providing a long-term security benefit without restricting the use of these
> characters in all header fields.

The pre-defined set of characters for the prefix end effectively split header values into atomic parts. An atomic part can only be attacked as a whole and so is robust to CRIME-like attack.

If your important data, "token" is included in a value as follows, with "/" being the only character in the pre-defined set of characters:
.../secret=token/...
The atomic part is "secret=token" and no partial match is allowed against it.

> 
> Splitting cookies into the crumbs is safe, since we know that is a feature of
> that specific field, and doing similar atom-based matching on other fields
> where we have a guarantee on the delimiter is likely safe, but prefix
> matching as you have it (with either strategy) can still be attacked.
> 
> -=R

Limited delta is a specific kind of atom-based matching. It is therefore no more vulnerable to attacks than other forms of atom-based matching.

Hervé.

> <[email-masked]> wrote:
> 
> 
> 	Roberto,
> 
> limiting which shared prefixes are used. The last character of a shared prefix
> must belong to a predefined set of characters. An example of predefined set
> of characters is "/?=, " (with a space as the last character). For example, for
> the following URLs:
> character. Therefore we think that using this new strategy, prefix matching is
> not vulnerable to CRIME-like attacks. In fact, using this strategy, we are
> enabling some kind of fine-grained indexing of values, where well defined
> parts of a value can be referred to.
> 
> 	The second strategy is to limit the number of times a given header
> value can be used as a reference for prefix matching. This limitation can be
> very low: limiting this usage as a reference to 2 times is already sufficient to
> 	I believe that it is still possible to probe interesting data out of various
> fields of the URL, for example, or even cookies, assuming they aren't B64
> encoded.
> 
> 	-=R
> 
> 	There are two obvious strategies here: What we do now, and using
> what SPDY does today (share connections if the certs match and DNS
> resolution of the new hostname overlaps with those of the current
> connection).
> 
> 	-=R
> 
> <[email-masked]> wrote:
> 	> On 23/03/2013, at 5:04 AM, RUELLAN Herve

---

From: RUELLAN Herve <[email-masked]>
Date: Thu, 28 Mar 2013 17:00:08 +0000

> Sent: jeudi 28 mars 2013 01:15
> To: RUELLAN Herve
> I've checked in some changes to delta2 which expands and documents
> various options for delta2 in the README.md.
> 
> The best headerdiff option which I believe is safe against CRIME in the future
> is:
>   headerdiff=delta_type=false,Huffman

I think that for headerdiff, the best option which is safe against CRIME is:
headerdiff=delta_type='/&= \coma',Huffman

> couldn't come up with a way I could prove was safe, unlike the atom-
> matching, which one can prove is no worse than a brute-force attack.

The limited prefix matching defined above also need a brute-force attack to be broken.

Hervé.

>   delta2 (max_byte_size=4096, max_entries=256, small_index=1,
> hg_adjust=0, implicit_hg_add=0, refcnt_vals=0)       664,683  4.16 | 0.19  0.02
> 0.83  0.15
>                                                          headerdiff (buffer=4096, delta_type=false,
> huffman)       759,783  2.03 | 0.22  0.01  0.78  0.18
> 
> 
>   delta2 (max_byte_size=4096, max_entries=256, small_index=1,
> hg_adjust=0, implicit_hg_add=0, refcnt_vals=0)       585,475  5.32 | 0.27  0.02
> 1.28  0.13
>                                                          headerdiff (buffer=4096, delta_type=false,
> huffman)       543,047  3.29 | 0.25  0.02  0.73  0.14
> 
> 
> 
>

---

From: Roberto Peon <[email-masked]>
Date: Thu, 28 Mar 2013 15:16:53 -0400

The net effect of the character-delimited prefix match you propose is that
an attacker must only brute force each subsequence which matches [^/&=,
]*([^/&=, ]|$) ,

Running the numbers, that is:

k^s * m

where:

k = possible characters
s = subsequence length or characters not ending in [^/&= ,] or end-of-line
m = number of subsequences

instead of full atom matching, which is (is a good special case of above
where m is always 1 and s is always n):

k^n

where:

k = possible characters
n = length of field

In other words, full atom matching is *exponentially* more difficult (a
desirable trait)!

In the example above, assuming 27 commonly used characters per entry, I'm
very likely to completely discover that data in:

in:

27^4 + 27^5 + 27^6 tries

Note that it is likely that an attacker would be able to do substantially
better than above if they know the letter frequency (very likely) or have
similar data:
In the case of a whole atom match, I'd discover the data in:

27^(17) tries

So, full atom matching is ~ 5 quadrillion (5,353,441,417,462,320) times
more difficult... that is a lot.

When I originally considered prefix matching in the past, this was the math
that I did, and I decided that I was not confident that compressor
implementors would ensure that their encoder prevents prefix matching when
the subsequence lengths are too small (and thus easily attacked). The same
consideration applies to dynamic huffman coding. It *CAN* be safe, but it
requires complexity and computation, and I think there is significant risk
that implementors may knowing or unknowingly sacrifice security. It is
actually more safe to ignore delimiters and allow for a match of a prefix
so long as it is greater than a certain length. At least in that case there
is guarantee of the number of times that it must be brute forced...

Full-atom matching is simply much more difficult to get wrong from a
security perspective, and it results in pretty decent compression...

-=R

On Thu, Mar 28, 2013 at 1:00 PM, RUELLAN Herve
<[email-masked]>wrote:

> future
> (buffer=4096, delta_type=false,
> (buffer=4096, delta_type=false,

---

From: Roberto Peon <[email-masked]>
Date: Thu, 28 Mar 2013 15:19:16 -0400

Oops, the math is a bit wrong:
k^s * m
it is k^s * m * e
where e == number of possible terminals, but it really doesn't make any
significant difference in the expected outcome given that the attacker is
likely to know which terminals to use much of the time.
-=R

On Thu, Mar 28, 2013 at 3:16 PM, Roberto Peon <[email-masked]> wrote:

> When I originally considered prefix matching in the past, this was the
> math that I did, and I decided that I was not confident that compressor
> On Thu, Mar 28, 2013 at 1:00 PM, RUELLAN Herve <[email-masked]
> > wrote:
>

---

From: RUELLAN Herve <[email-masked]>
Date: Fri, 29 Mar 2013 15:26:39 +0000

> Sent: jeudi 28 mars 2013 20:17
> To: RUELLAN Herve
> The net effect of the character-delimited prefix match you propose is that an
> attacker must only brute force each subsequence which matches [^/&=,
> ]*([^/&=, ]|$) ,
> 
> instead of full atom matching, which is (is a good special case of above where
> m is always 1 and s is always n):
> 
> 	k^n
> 
> 
> where:
> 
> 
> 	k = possible characters
> 	n = length of field
> 
> 
> 

This is roughly 400 million tries. And this figure is obtained using several assumptions that may not hold:
- The number of possible characters is only 27.
- The length of each chunk is known.

> Note that it is likely that an attacker would be able to do substantially better
> than above if they know the letter frequency (very likely) or have similar
> data:
> So, full atom matching is ~ 5 quadrillion (5,353,441,417,462,320) times more
> difficult... that is a lot.

True full atom matching is much harder, but limited prefix matching is already very hard.

We must also keep in mind that each try correspond to a request that the attacker for the client to do. Such a huge number of requests should be detected somewhere, just in order to prevent DoS attacks.

> implementors would ensure that their encoder prevents prefix matching
> when the subsequence lengths are too small (and thus easily attacked). The
> same consideration applies to dynamic huffman coding. It *CAN* be safe,
> but it requires complexity and computation, and I think there is significant
> risk that implementors may knowing or unknowingly sacrifice security. It is
> actually more safe to ignore delimiters and allow for a match of a prefix so
> long as it is greater than a certain length. At least in that case there is
> guarantee of the number of times that it must be brute forced...
> 
> Full-atom matching is simply much more difficult to get wrong from a security
> perspective, and it results in pretty decent compression...

I think that prefix matching with constrained ending is fairly secure: it compels an attacker to used brute force to break it. In addition, it provides very interesting results regarding compression.

Hervé.

---

From: Roberto Peon <[email-masked]>
Date: Fri, 29 Mar 2013 11:39:13 -0700

Herve--

With the way you've implemented prefix matching, there are no guarantees on
security whatsoever.
In order to provide a guarantee of at least a minimum amount of effort on
the part of the attacker, you MUST provide guarantees on the minimum
subsequence sizes, as this relates directly to the amount of tries...
As an example,
  foo.com/a/b/c
will be exceptionally easy to figure out, as each subsequence will be
guessed in a very small amount of time.

There are many caveats and gotchas in this space, and I feel uncomfortable
that you're making assertions about safety unless you've got some security
folks looking at it critically.
I've done that for the delta compressor, and I suggest you do the same. If
it turns out that we do get consensus from security folks that some kind of
prefix matching is safe, I'm happy to add it back into delta. Until then, I
don't want to go down the rabbit hole!
-=R

On Fri, Mar 29, 2013 at 8:26 AM, RUELLAN Herve
<[email-masked]>wrote:

> We must also keep in mind that each try correspond to a request that the
> attacker for the client to do. Such a huge number of requests should be
> detected somewhere, just in order to prevent DoS attacks.
>
> math
> security
> I think that prefix matching with constrained ending is fairly secure: it
> compels an attacker to used brute force to break it. In addition, it
> provides very interesting results regarding compression.

---

From: James M Snell <[email-masked]>
Date: Fri, 29 Mar 2013 14:09:56 -0700

+1 ... I have explored this a bit on this end also (and discussed it
with some security folks) and definitely align with Roberto's point of
view. At this point, any prefix matching proposal needs to be backed
with clear evidence as to it's safety.

On Fri, Mar 29, 2013 at 11:39 AM, Roberto Peon <[email-masked]> wrote:
> On Fri, Mar 29, 2013 at 8:26 AM, RUELLAN Herve <[email-masked]>
> wrote:
>>
>>
>>
>> >       s = subsequence length or characters not ending in [^/&= ,] or
>> > end-
>> > of-line