Is compressing data prior to encryption necessary to reduce plaintext redundancy?

Question

As explained in William Stallings' Book, in PGP encryption is done after compression, since it reduces redundancy.

I couldn't relate encryption strength with redundancy. Could anyone explain more on that?

Answer 1

Technically, if you use a cryptographically secure encryption algorithm with a fresh random key in a confidentiality mode such as (full block) CFB, you don't have to worry about the redundancy of the plain text, since the cipher + mode combination is supposed to be secure even if significant parts of the plain text are known to the adversary.

If the cipher + mode combination is partially broken or not completely secure for the way it is used, however, you might make certain attacks marginally harder by compressing the plain text before encryption. This might e.g. apply to very large plain texts you encrypt using either of the block ciphers with a 64 bit block. With a 64 bit block, the probability is approximately 0.5 that you will get at least one CFB mode state collision in a 4GB cipher text. If the plain text block happens to also be equal when that happens, the cipher text of the respective next block will also be equal, etc.

Answer 2

There is at least one way in which compression can weaken security; it has to do with the fact that essentially all methods of encrypting arbitrarily long message will inevitably leak information about the length of the input. The only way to avoid this leak is to pad all messages to a constant length before encrypting them — but if the messages are compressed, the compression will change their length in a way that will depend on their content, which may allow an attacker to obtain information about the content based on the length of the ciphertext.

For a practical example of such an attack, see e.g. "Uncovering Spoken Phrases in Encrypted Voice over IP Conversations" by Wright et al. (2010).

Answer 3

Compressing the data increases the security a number of ways. It reduces an attacker's ability to affect the decrypted output by flipping ciphertext bits. It removes regular patterns in plaintext (it might create other regular patterns, but they aren't directly the plaintext).

There are a number of attacks on OpenPGP that are thwarted by compression. Most of these are actually attacks on CFB mode, but still. The Schneier-Katz attack in particular is not effective against compressed data because it removes the attacker's freedom in manipulating the plaintext by manipulating the ciphertext.

Jon

Answer 4

Correct me if I'm wrong, but isn't compression working because there exists some pattern in the data? Such a pattern will not exists after encryption since, ideally, the output "looks random". So, if both encryption and compression is wanted, they have to be done in the order described in the book?