Re: Data redundacy and cryptoanalytic attacks

Alfonso De Gregorio <[email protected]> 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.