[Users] The role of compression in cryptosystems

Sandy Harris sandy at storm.ca
Tue May 29 10:38:13 EDT 2001

John Denker wrote:
> In a discussion of the role of compression in IPsec,
> at 06:54 PM 5/28/01 -0400, Henry Spencer wrote:
>  >
> >The CPU load is quite substantial, and although I don't have recent
> >timings, I wouldn't recommend compression unless you have a slow line.
> Hmmmm.  My recommendation would be to shift the burden of proof:  I would
> leave compression turned on unless there is a good reason to turn it off.

I agree.
> 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.

Yes, though there is a caveat. If the compression adds a header, that may
give the cryptanalyst known plaintext to work with, even in situations where
he wouldn't have known plaintext of actual messages, or it may save him the
trouble and risk of some other attack required to get plaintext.

The tradeoff is that, against any risks the header introduces, you get several
advantages. The message is shorter so the analyst gets less ciphertext to
attack, compressed text has higher entropy per block which makes the cipher
stronger in information theory terms (longer unicity distance) and (related
but not quite the same) there are no obvious characteristics, such as being
ASCII text with top bit of each byte 0, to help an attacker recognise valid
plaintext after trial decryption.
> 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/

Compressed text with a predictable header would not be secure against that
machine. It needs only one or two blocks of known plaintext.

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

More information about the cryptography mailing list