Subject: bohe implementation for compression tests

From: James M Snell <[email-masked]>
Date: Thu, 10 Jan 2013 11:08:41 -0800

I have an initial bohe implementation for the compression tests... it's
very preliminary and uses the same gzip compression as the current spdy3.
I'm going to be playing around with the delta compression mechanism as well
and see how much of an impact that has. Initial results are very promising
but I haven't done much debugging yet. Just wanted folks to know that this
work was underway...

https://github.com/jasnell/compression-test/tree/master/compressor/bohe

Some test runs....

./compare_compressors.py -c bohe -c spdy3 -c delta
../http_samples/mnot/amazon.com.har
732 req messages processed
             compressed | ratio min   max   std
req  bohe        26,122 | 0.13  0.04  0.70  0.08
req delta        33,955 | 0.17  0.02  0.71  0.09
req http1       195,386 | 1.00  1.00  1.00  0.00
req spdy3        27,238 | 0.14  0.04  0.71  0.08

732 res messages processed
             compressed | ratio min   max   std
res  bohe        39,628 | 0.25  0.04  0.66  0.07
res delta        44,499 | 0.28  0.02  0.65  0.09
res http1       159,968 | 1.00  1.00  1.00  0.00
res spdy3        41,325 | 0.26  0.04  0.67  0.08

./compare_compressors.py -c bohe -c spdy3 -c delta
../http_samples/mnot/craigslist.org.har
66 req messages processed
             compressed | ratio min   max   std
req  bohe         1,948 | 0.15  0.06  0.73  0.11
req delta         2,036 | 0.16  0.07  0.71  0.11
req http1        12,894 | 1.00  1.00  1.00  0.00
req spdy3         2,016 | 0.16  0.07  0.75  0.11

66 res messages processed
             compressed | ratio min   max   std
res  bohe         1,786 | 0.18  0.07  0.77  0.13
res delta         2,858 | 0.28  0.08  0.69  0.12
res http1        10,147 | 1.00  1.00  1.00  0.00
res spdy3         1,869 | 0.18  0.09  0.78  0.13

./compare_compressors.py -c bohe -c spdy3 -c delta
../http_samples/mnot/flickr.com.har
438 req messages processed
             compressed | ratio min   max   std
req  bohe        11,988 | 0.10  0.02  0.69  0.07
req delta        26,372 | 0.22  0.01  0.71  0.14
req http1       121,854 | 1.00  1.00  1.00  0.00
req spdy3        12,550 | 0.10  0.02  0.71  0.07

438 res messages processed
             compressed | ratio min   max   std
res  bohe        13,073 | 0.09  0.05  0.66  0.06
res delta        25,236 | 0.18  0.02  0.70  0.11
res http1       140,457 | 1.00  1.00  1.00  0.00
res spdy3        14,142 | 0.10  0.05  0.66  0.06

./compare_compressors.py -c bohe -c spdy3 -c delta
../http_samples/mnot/facebook.com.har
234 req messages processed
             compressed | ratio min   max   std
req  bohe         6,091 | 0.15  0.06  0.78  0.07
req delta         7,800 | 0.19  0.02  0.70  0.07
req http1        41,980 | 1.00  1.00  1.00  0.00
req spdy3         6,301 | 0.15  0.06  0.77  0.07

234 res messages processed
             compressed | ratio min   max   std
res  bohe         9,458 | 0.23  0.07  0.68  0.07
res delta        12,045 | 0.30  0.13  0.60  0.08
res http1        40,252 | 1.00  1.00  1.00  0.00
res spdy3         9,788 | 0.24  0.07  0.69  0.07

---

From: Roberto Peon <[email-masked]>
Date: Thu, 10 Jan 2013 14:23:28 -0800

Very cool!

When I wrote the original form of the test framework, I used gzip'd "raw"
HTTP as a benchmark, but only that since any stream-based compressor is
unsafe in the presence of CRIME and similar attacks.

Also, the way the encoding works for the delta-compressor if we added an
ephemereal "clone" statement, it'd have roughly the same semantics as BOHE,
where the 'default dictionary' defines the pre-agreed-upon codes.
Would you like me to add opcode type and add an option to delta so you can
play with that too?

-=R

---

From: James M Snell <[email-masked]>
Date: Thu, 10 Jan 2013 14:35:36 -0800

I need to dig through the delta code a bit more so I can fully understand
what's going on there before I weigh in on that. I'm also going to play
with a couple of other ideas in the process. It will likely be mid next
week before I get around to playing with delta too much so I'll let you
know then.

---

From: James M Snell <[email-masked]>
Date: Fri, 11 Jan 2013 10:43:48 -0800

Just continuing my investigation of various header compression strategies
around the BOHE mechanism. In my personal github fork, I have just checked
in two bohe variations, one that implements selective-compression, the
other implements isolated-compression..

https://github.com/jasnell/compression-test/tree/master/compressor/bohe2
https://github.com/jasnell/compression-test/tree/master/compressor/bohe3

With bohe2 (selective-compression), a header block can consist of a
compressed set of headers and an uncompressed set of headers. Specific
headers such as Cookie, Set-Cookie, etc can be marked as "Do Not Compress".
These are dropped into the frame as-is and thus avoid the CRIME issue
completely. The rest of the headers are compressed using gzip using the
existing spdy3 dictionary. Obviously this is not ideal because Cookie data
then is passed around without any compression at all, making it far less
efficient than any of the other options on the table.

In bohe3 (isolated-compression), a header block can consist of two separate
compressed blocks generated using two separate stream compressor instances.
Selected headers (like Cookie) can be included in the secondary isolated
block which would never contain general user-provided header data.

**These are only experiments right now and are not intended as serious
proposals for the spec**. Isolated-compression (bohe3) does show promise
however. If we can successfully isolate potentially sensitive headers into
their own compression context generated independently of any general
user-supplied data, we can effectively short-circuit the CRIME attack by
making it impossible for an attacker to compare values based on the
compression ratio... and since it still uses gzip compression, we achieve a
generally better compression ratio overall than we get with the proposed
delta encoding. For now, tho, just consider this all just to be fodder for
discussion. There are still MANY issues with these experimental approaches
and I still need to go through delta in more detail to see if there is a
way bohe and delta can be used effectively together.

Just for example...

james-snells-macbook-pro:compression-test james$ ./compare_compressors.py
-c bohe3 -c bohe2 -c bohe -c delta -t
/Users/james/git/http_samples/mnot/amazon.com.har
732 req messages processed
             compressed | ratio min   max   std
req  bohe        26,035 | 0.13  0.03  0.68  0.08
req bohe2        44,195 | 0.23  0.07  0.71  0.13
req bohe3        30,944 | 0.16  0.05  0.74  0.08
req delta        33,955 | 0.17  0.02  0.71  0.09
req http1       195,386 | 1.00  1.00  1.00  0.00

732 res messages processed
             compressed | ratio min   max   std
res  bohe        39,525 | 0.25  0.04  0.67  0.07
res bohe2        47,157 | 0.29  0.12  0.71  0.08
res bohe3        44,843 | 0.28  0.06  0.70  0.07
res delta        44,499 | 0.28  0.02  0.65  0.09
res http1       159,968 | 1.00  1.00  1.00  0.00

- James

---

From: James M Snell <[email-masked]>
Date: Mon, 14 Jan 2013 17:29:54 -0800

Just continuing the investigation on various compression strategies. I
spent part of the day going through delta to make sure I understand it and
how it compares with bohe... I'll have some additional thoughts (and
concerns) with regards to that later on... The other half of the day has
been spent with various other bohe variations. Late in the after I hit upon
a particularly interesting variation... I've checked it in here:
https://github.com/jasnell/compression-test/tree/master/compressor/bohe4

This variation encodes headers and randomly assigns them to one of two
separate buckets. Those are then randomly ordered and compressed using two
separate compressor instances within the header block...

# +-------------+--------------------------+
# | num_headers |   block 1 len (4 bytes)  |
# +-------------+--------------------------+
# |        compressed header block 1       |
# +----------------------------+-----------+
# |  block 2 len (4 bytes)     |           |
# +----------------------------+           |
# |        compressed header block 2       |
# +----------------------------+-----------+

Because of the randomization, there is no way of determining in advance
which block any individual piece of data will land... making it much harder
for an attacker to use the compression ratio to reverse engineer any
particular value... every time the information is sent, it can be in a
different location. You can take the exact same request and encode it
multiple times and end up with a different message size every time (up to a
given limit, of course).

Some numbers from various test runs... note how bohe4 produces variable
compression ratios given identical input.

./compare_compressors.py -c bohe -c bohe4 -c delta -t
/Users/james/git/http_samples/mnot/wikipedia.org.har
408 req messages processed
             compressed | ratio min   max   std
req  bohe        10,784 | 0.13  0.05  0.65  0.07
req bohe4        13,496 | 0.16  0.05  0.69  0.08
req delta        16,725 | 0.20  0.04  0.72  0.09
req http1        84,388 | 1.00  1.00  1.00  0.00

408 res messages processed
             compressed | ratio min   max   std
res  bohe        19,882 | 0.25  0.06  0.58  0.10
res bohe4        20,610 | 0.26  0.09  0.63  0.09
res delta        24,523 | 0.30  0.04  0.60  0.12
res http1        80,613 | 1.00  1.00  1.00  0.00

./compare_compressors.py -c bohe -c bohe4 -c delta -t
/Users/james/git/http_samples/mnot/wikipedia.org.har
408 req messages processed
             compressed | ratio min   max   std
req  bohe        10,784 | 0.13  0.05  0.65  0.07
req bohe4        13,820 | 0.16  0.07  0.67  0.08
req delta        16,725 | 0.20  0.04  0.72  0.09
req http1        84,388 | 1.00  1.00  1.00  0.00

408 res messages processed
             compressed | ratio min   max   std
res  bohe        19,882 | 0.25  0.06  0.58  0.10
res bohe4        21,644 | 0.27  0.09  0.61  0.09
res delta        24,523 | 0.30  0.04  0.60  0.12
res http1        80,613 | 1.00  1.00  1.00  0.00

Again, this is just intended as fodder for discussion right now. I'll have
some comments specifically on delta encoding tomorrow sometime.

- James

---

From: Roberto Peon <[email-masked]>
Date: Mon, 14 Jan 2013 19:01:18 -0800

An attacker would run its experiment some increased number of times and
still get information about what is in the context, assuming i am
understanding it correctly. :/

-=R
On Jan 14, 2013 5:33 PM, "James M Snell" <[email-masked]> wrote:

- James

---

From: James M Snell <[email-masked]>
Date: Mon, 14 Jan 2013 19:07:42 -0800

The randomization is not intended to make reverse engineering impossible,
just a large degree more difficult (and potentially more impractical). Used
in combination with other strategies -- such as moving away from the use of
unauthenticated session ids in cookies -- it could prove effective enough
to get the job done.

---

From: Roberto Peon <[email-masked]>
Date: Mon, 14 Jan 2013 21:34:20 -0800

I'm trying to express, I guess, that as the number of buckets goes up, the
compression becomes correspondingly less effective, and it has a limited
(eventually constant) security benefit after enough requests.

I believe this ends up being a binomial distribution thus, for k buckets
and k requests I believe that we end with a probability of hitting a bucket
that does not have the sensitive data of only 1/e (increasing security by
roughly 36%) while decreasing compression effectiveness by strictly worse
than 54% (i.e. 1-1/e at the limit).

The attackers are better math geeks than I am. This may explain my wariness
to play with any kind of stream compressor and make assertions about safety
:)
-=R

On Mon, Jan 14, 2013 at 7:07 PM, James M Snell <[email-masked]> wrote:

>> Again, this is just intended as fodder for discussion right now. I'll
>> have some comments specifically on delta encoding tomorrow sometime.
>>
>> - James
>>
>>
>> On Thu, Jan 10, 2013 at 11:08 AM, James M Snell <[email-masked]>wrote:
>>

---

From: James M Snell <[email-masked]>
Date: Mon, 14 Jan 2013 23:47:09 -0800

Oh yes, I fully understand... like I said, this is not intended to make it
impossible, just harder, and the idea is to throw some variations on the
table so we can get a good comparison of the options. For this particular
variation, there are only two buckets. I tested with three and the
compression efficiency drops off by an order of magnitude. With two buckets
we are able to maintain a compression ratio roughly on par with http1-gzip
and consistently better than delta. But, like you said, it's not a "fix"..
it just makes attacks like CRIME harder to execute by some degree.

On Mon, Jan 14, 2013 at 9:34 PM, Roberto Peon <[email-masked]> wrote:

> The attackers are better math geeks than I am. This may explain my
> wariness to play with any kind of stream compressor and make assertions
> about safety :)
> -=R
>
>

---

From: Martin Thomson <[email-masked]>
Date: Wed, 16 Jan 2013 17:06:19 -0800

James,

Any feel for how bohe compares on CPU cost?  Ideally, the test harness
would provide that information alongside the rest of the data.

On 11 January 2013 10:43, James M Snell <[email-masked]> wrote:
> in two bohe variations, one that implements selective-compression, the other
> implements isolated-compression..
>
> and I still need to go through delta in more detail to see if there is a way
> bohe and delta can be used effectively together.
>
> Just for example...
>
> james-snells-macbook-pro:compression-test james$ ./compare_compressors.py -c
> bohe3 -c bohe2 -c bohe -c delta -t

---

From: Roberto Peon <[email-masked]>
Date: Wed, 16 Jan 2013 17:09:01 -0800

Unfortunately python does not lend itself to CPU consumption comparisons
(thus my writing the compressor in C++ the other day)
-=R

On Wed, Jan 16, 2013 at 5:06 PM, Martin Thomson <[email-masked]>wrote:

> way

---

From: Mark Nottingham <[email-masked]>
Date: Thu, 17 Jan 2013 12:11:39 +1100

Getting there, although you may need a small truck to haul the grain of salt that will accompany it...

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

---

From: Martin Thomson <[email-masked]>
Date: Wed, 16 Jan 2013 17:21:15 -0800

> Getting there, although you may need a small truck to haul the grain of salt that will accompany it...

Even if it just means running the sample set n times using 'time', it
would be nice to get ballpark figures.  Even if the errors are
enormous.  For instance, a python implementation of delta is probably
not that good to compare to an optimized gzip implementation, but it
might still let us know that deltav3 is better than deltav2.

---

From: Roberto Peon <[email-masked]>
Date: Wed, 16 Jan 2013 17:41:42 -0800

The difference is, well huge, and not only linear, though it arguably could
be made to be merely linearly different :)

Which reminds me, pypi has a module that makes huffman encoding/decoding
very cheap (and I'd get to throw away a file).
Any opinions on using/including it? It'd require getting it installed on
machines (on ubuntu, just an apt-get away...)
-=R

---

From: Mark Nottingham <[email-masked]>
Date: Thu, 17 Jan 2013 12:53:55 +1100

pip install foo is fine; just make sure you put it in your compressor's README, and recover from the import failure semi-gracefully.

Cheers,

On 17/01/2013, at 12:41 PM, Roberto Peon <[email-masked]> wrote:

> The difference is, well huge, and not only linear, though it arguably could be made to be merely linearly different :)
> 
> Which reminds me, pypi has a module that makes huffman encoding/decoding very cheap (and I'd get to throw away a file).
> Any opinions on using/including it? It'd require getting it installed on machines (on ubuntu, just an apt-get away...)
> -=R
> 
> 
> On Wed, Jan 16, 2013 at 5:21 PM, Martin Thomson <[email-masked]> wrote:

---

From: Mark Nottingham <[email-masked]>
Date: Fri, 18 Jan 2013 17:52:59 +1100

OK, I've started to record CPU time in my refactor branch:

* TOTAL: 1012 req messages
                  size  time | ratio min   max   std
   http1       830,970  0.05 | 1.00  1.00  1.00  0.00
  simple       320,883  0.05 | 0.39  0.07  0.92  0.24
   spdy3        85,492  0.06 | 0.10  0.03  0.66  0.08

* TOTAL: 1012 res messages
                  size  time | ratio min   max   std
   http1       424,075  0.04 | 1.00  1.00  1.00  0.00
  simple       176,216  0.12 | 0.42  0.11  0.95  0.12
   spdy3        80,706  0.07 | 0.19  0.04  0.68  0.09

https://github.com/http2/compression-test/tree/stream-sep