Subject: Some general thought on CRIME and Compression and Headers

From: James M Snell <[email-masked]>
Date: Fri, 11 Jan 2013 11:45:54 -0800

Thinking through the various issues relating to the CRIME attack.. just
wanted to offer up some additional fodder for consideration..

:brainstorming_mode on

First of all, it is good to consider what the CRIME attack actually is.
Generally, if we have a block of header data that contains a mix of static
sensitive data (such as a session cookie) and attacker-provided dynamic
data, the attacker can repeatedly analyze the size of the compressed block
of data using different dynamic data values until  the sensitive data is
successfully reverse-engineered.

So far, the techniques we have explored to address this problem have been
to alter the compression mechanism (e.g. delta) so that the compression
ratio can't be effectively used to reverse engineer the sensitive data.
This, however, brings along a range of issues, not the least of which is
the fact that delta encoding is not nearly as efficient as gzip.

Thinking about it further, another approach presents itself that is
independent of the compression mechanism but requires more work from
implementers and application developers (and would require a general change
to the way a lot of software currently works)... That approach is to move
away from the use of static session-id cookies.

If, for instance, every message contained a dynamically generated token
derived from a secret session-key and a nonce, then it simply would not
matter if an attacker was able to guess the value by analyzing the
compression ratio... by the time they figured out the value, the value
would no longer be relevant.

So.. rather than...

  Server => Client

  Set-Cookie: session-id=some-static-key

  Client => Server

  Cookie: session-id=some-static-key

It would be...

  Server => Client

  Session-Key: some-private-session-key

  Client => Server

  Session-Key: dynamic-token-derived-from-session-key

Obviously this solution would only work for certain types of sensitive
 information.. and we currently have absolutely no way of knowing exactly
which bits of information in the headers are going to be interesting to an
attacker. But, at the very least, this would address a significant known
attack vector.

My experimental spdy key_nego mechanism [1] could theoretically play a role
here as well... providing the mechanism by which the dynamic session key is
negotiated, avoiding the use of Set-Cookie and compressed-headers entirely.

[1] http://tools.ietf.org/html/draft-snell-httpbis-keynego-00

- James

---

From: Frédéric Kayser <[email-masked]>
Date: Sat, 12 Jan 2013 12:22:39 +0100

Hello,
gzip/deflate streams are made of different types of blocks cf. RFC 1951 http://www.ietf.org/rfc/rfc1951.txt (btype 0 is non compressed - fixed length-, btype 1 uses predefined Huffman tables, and btype 2 embeds Huffman tables specially tailored for the current data). The stream could switch to btype 0 when sensitive data has to be compressed, and afterwards this region could be excluded from LZ matches to avoid reuse, the resulting stream would be perfectly compatible with current Deflate decoders implementations.

Le 11 janv. 2013 à 20:45, James M Snell a écrit :

> So far, the techniques we have explored to address this problem have been to alter the compression mechanism (e.g. delta) so that the compression ratio can't be effectively used to reverse engineer the sensitive data. This, however, brings along a range of issues, not the least of which is the fact that delta encoding is not nearly as efficient as gzip.

---

From: Roberto Peon <[email-masked]>
Date: Sat, 12 Jan 2013 04:10:58 -0800

The hard part of any such schemes is determining what is sensitive,
especially in the face of any future semantic/header changes. So, be
careful :)

SPDY as deployed today uses the fact that we have a good idea today about
what is sensitive, that we'll be throwing it out soon, and it only allows
gzip to compress something IFF it is not sensitive, or, if sensitive, IFF
the entire sensitive atom matches the previous sensitive atom.
This is, in effect, what is being proposed here.

One other thing... The delta encoder which was proposed here does not
strive for the best possible compression. If it did, I wouldn't leave bits
on the floor by doing byte alignment!
Rather, it is meant to be a compromise, giving excellent compression
(especially if/when we adapt to the idea that *change* causes an increase
in bytes on the wire), but also allowing proxies to do minimal redundant
work (of recompression/reencoding) etc.

If we're willing to throw more CPU at the problem (currently delta is 3x
more efficient than gzip in terms of CPU, not even counting proxies) I know
from experimental data we can get better compression ratios :)
-=R

On Sat, Jan 12, 2013 at 3:22 AM, Frédéric Kayser <[email-masked]> wrote:

> Hello,
> gzip/deflate streams are made of different types of blocks cf. RFC 1951
> http://www.ietf.org/rfc/rfc1951.txt (btype 0 is non compressed - fixed
> length-, btype 1 uses predefined Huffman tables, and btype 2 embeds Huffman
> tables specially tailored for the current data). The stream could switch to
> btype 0 when sensitive data has to be compressed, and afterwards this
> region could be excluded from LZ matches to avoid reuse, the resulting
> stream would be perfectly compatible with current Deflate decoders
> implementations.
>

---

From: "Poul-Henning Kamp" <[email-masked]>
Date: Sat, 12 Jan 2013 12:20:09 +0000

--------
In message <[email-masked]>, =?iso-8859-1?Q?Fr=E9d=E9ric_Kayser?= writes:

>length-, btype 1 uses predefined Huffman tables, and btype 2 embeds 
>Huffman tables specially tailored for the current data). The stream 
>could switch to btype 0 when sensitive data has to be compressed, and 
>afterwards this region could be excluded from LZ matches to avoid reuse, 
>the resulting stream would be perfectly compatible with current Deflate 
>decoders implementations.

I spent quite some time hacking code to do interesting things
with gzip blocks (ESI support on gzip'ed objects if you must know).

While technically feasible, I would not recommend requiring
mainstream implementations to deal with "naked" GZIP blocks, in
particular since debugging compressed streams is not even close to
fun for anybody.

-- 
Poul-Henning Kamp       | UNIX since Zilog Zeus 3.20
[email-masked]         | TCP/IP since RFC 956
FreeBSD committer       | BSD since 4.3-tahoe    
Never attribute to malice what can adequately be explained by incompetence.

---

From: Nico Williams <[email-masked]>
Date: Mon, 14 Jan 2013 10:00:01 -0600

See http://tools.ietf.org/html/draft-williams-websec-session-continue-prob-00

There's also a -00 of a protocol to meet the requirements laid out in
the problem statement.  It's got a few bugs, and also the intention is
to discuss the problem statement first (on the WEBSEC WG list) then
actual proposals (plural, we hope).  But roughly the proposals all
will tend to look roughly like "there's a session key and the requests
[and possibly responses] will carry a nonce and a MAC of stuff,
including the nonce, in the headers".

Nico
--

---

From: Martin Thomson <[email-masked]>
Date: Wed, 16 Jan 2013 16:55:08 -0800

> successfully reverse-engineered.

I'm not sure that this is the best characterization of the problem.
CRIME relies on there being state established by previous requests
that can be exposed by altering requests and observing how that
affects the size of requests (or responses).  The specific attack in
question used cookies because they are both easy and high-value.

As Roberto notes, knowing what is and isn't sensitive is
near-impossible.  Of course, using this definition you could say that
it is still possible to use the delta-encoding to mount a similar
attack, except for the fact that it is grossly inefficient to do so
because the space you have to search to interrogate the space is much
larger ... to the point that the attack would be no better than a
straight guessing game.

--Martin