Compression side channel

[Sandy Harris]

John Kelsey wrote:

> The basic result: Lossless compression algorithms leak data about their
> input in the size of their output.  ... However, compressors like Zip
> deflate and Unix compress maintain state, which is changed as new bytes
> of text are processed.  This state basically is used to make future
> texts compress better if they're more like recent texts.
> 
> This leads to some really powerful attacks, at least in the
> chosen-plaintext model.  We have something like
> 
>         E(X) = encrypt(compress(X))
> 
> where the encryption preserves length (e.g., RC4 encryption).  Suppose
> someone is sending a secret S in these messages, and the attacker gets
> to choose some prefix or suffix to send, e.g.
> 
> X[0] = S+suffix[0]
> X[1] = S+suffix[1]
> ...
> 
> Well, if the attacker can watch how these compress, he can learn a *lot*
> about these secret strings.

Once you've pointed it out, it seems obvious, but at least to me it wasn't
until you did. Methinks that indicates a good piece of work on your part.

Does using non-adaptive compression save the day?

You can compress English/ASCII text better than 10% by just looking at
pairs of characters and, whenever the 2nd one is ' ', throw it away and 
set the top bit of the first one. 

Or pick 256 common strings - 'ing', 'the', etc - and encode them as bytes
128-255 while using 0-127 for ASCII. This should give fair compression.

Or use 16-bit words where those with top bit 1 encode 2^15 common English
words and anything not on the list just falls back to ASCII storage using
16-bit words with top bit 0. I designed a system like that once. For
English text it gave compression comparable to the common algorithms.
Send off-list mail if you want the details.

Of course the problem with non-adaptive compression is that you have to
know when you design it what the inputs will look like when you run it.
The above schemes would fail miserably on anything but English text.



---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com