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

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 2

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 3

Short answer: “No”. The latest research shows that compression actually harms security.

"Reducing redundancy" is an outdated concept from the late 20th century. The intuition was that if our ciphers turned out to be weak, we might avoid a practical loss of confidentiality by giving attackers less information to work with.

For example, in the following illustration from Wikipedia, the image is encrypted using ECB mode, but because ECB mode is weak and the image is uncompressed, we can still clearly see the image of the penguin:

That intuition turned out to be wrong. Our ciphers are actually pretty good, and today, much encryption is carried out on messages generated by automated systems (rather than emails written by humans). In those situations, compression frequently leaks enough information (via the length of the ciphertext) to completely compromise the encryption.

In the context of HTTP, this is now known as a BREACH vulnerability.

Answer 4

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