The role of compression in cryptosystems

[Matt Blaze]

...
> This recommendation is based on the following general principle:
> 
>          Any cipher applied to well-compressed data is much
>          harder to cryptanalyze than the same cipher applied to
>          uncompressed plaintext.
> 
> As an illustration, a block of well-compressed text encrypted by single-DES 
> would be secure against EFF's DES cracker (whereas a block of uncompressed 
> text is not).  http://www.eff.org/descracker/
> 
> This principle is based on information theory, specifically the idea of 
> unicity distance.  Note that these days the security of a typical crypto 
> scheme is explained in terms of _complexity theory_ (the assertion that 
> cryptanalysis is computationally infeasible), whereas information theory is 
> a completely different kettle of fish.
> 
> And while we're on the subject:  the module that compresses the data should 
> add a goodly percentage of random cryptologic nulls (no, I don't mean ASCII 
> NULs).  The decompressor of course removes them.
> 
> 
> To decide whether or not this principle is important, we can consider three 
> cases:
>   a) In the case where the cipher is really weak and the adversary has lots 
> of ciphertext to work with, pre-encipherment precautions (such as 
> compressing + adding nulls) won't save the day.  No compressor is perfect, 
> so the unicity distance is never infinite.
>   b) There is a vast middle ground where such precautions can increase the 
> adversary's workload by a large factor (thousands) while increasing the 
> good guy's workload by only slightly.
>   c) In the case where the cipher is really strong, further strengthening 
> is just lily-gilding.
> 
...

While I agree in principle that plaintext with a high information content
probably makes it harder to mount a ciphertext-only attack against most
(non-randomized, at least) secret-key cryptosystems, I'm not at all
convinced that the security benefits outweigh even very small costs
in practice.

I've found that a great many complete communications systems (including the
application layer) make it fairly easy, somewhere in the protocol stack,
for an attacker to introduce chosen plaintext or use an endpoint
as a chosen-ciphertext oracle, and I've never met a real system that
doesn't make it easy to learn or guess known plaintext.

Adding a compression layer just doesn't help under such conditions.  In
fact, it may even hurt, when the risks that come with added engineering
complexity are considered.  The bottom line is that if you don't have a
cipher that can withstand all those seemingly silly attack models about
which cryptologists worry so much, you've got problems in theory.  And in
practice, you've got even worse problems.

-matt






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