Subject: Data redundacy and cryptoanalytic attacks

From: Alfonso De Gregorio <[email-masked]>
Date: Fri, 28 Sep 2001 17:05:03 +0200

Hi Terry, hi Peter,

I've read with interest both your drafts.

However, reducing data redundancy does not necessarily means reducing
opportunities for perform cryptanalytic attacks.

At Crypto, John Kelsey gave a rump session talk on a his research
on how compression and encryption might interact to reduce security.

Chosen-plaintext and plaintext-only attacks became possible 
at least when lossless compression algorithm leak data about
their input in the size of their output. 

Some tests have been carried out with encryption algorithms
that preserves length (e.g. RC4). 
This kind of attacks dose not affect necessarily also other
encryption algorithms; however, this research certainly show
how this field has not been studied sufficiently.
In my opinion, data encryption should be not considered in all
cases a good practice to avoid cryptanalytic attacks unless
further research will be made on the subject
(for more informations see also, "Compression side channel" on
[email-masked]).

(BTW: Terry, the new version of Peter's draft is available at ID 
archive).

regards,
alfonso

---

From: [email-masked] (Peter Gutmann)
Date: Sat, 29 Sep 2001 04:07:38 +1200 (NZST)

Alfonso De Gregorio <[email-masked]> writes:

>Chosen-plaintext and plaintext-only attacks became possible at least when
>lossless compression algorithm leak data about their input in the size of
>their output.

It's a very specialised chosen-plaintext attack (if you can seed the compressor
with data which matches the target data, it'll compress differently than an
unseeded compressor... this isn't necessarily as easy as it sounds, although
the explanation is long and boring and doesn't really apply to things like
zlib).  Since zlib uses a blocked semi-adaptive Huffman coder (the terminology
may have changed somewhat since I wrote my thesis in about 1859) the data is
preceded by a compressed canonical Huffman tree which will have a constant size
if the seed data matches the target data.  By iteratively feeding in different
seed data, you can check whether you've guessed the plaintext or not (finding
an exact match may be tricky since zlib will use Huffman codes as you get
close, but an LZ77 (offset, length) pair when you get an exact match, so you
may find a whole pile of values which give approximately the same compressed
size).

It's a cool attack, but I don't think I'll be losing any sleep over it
(although for due diligence purposes I've included a comment on it in the RFC
draft).

Peter.