Encryption and Compression

I've read that encryption produces random data and compression works by removing patterns in data and as a consequence, encrypted data has high entropy. I'm a bit confused, though.

The reason I'm confused is that I thought that all encryption was supposed to do is make it as difficult as brute forcing the key to go from the cipher text to the plain text. It seems to me like there could be an AES key that would produce an all 0 ciphertext given a certain plaintext.

So, long as you couldn't use the all 0 ciphertext to figure out the plain text without brute forcing the key, it wouldn't break any of the goals of encryption.

Is it really that encryption is supposed to produce uncorrelated data to the plaintext, as though every bit was random, and this just happens on large plaintexts, for the most part, to produce high entropy ciphertexts?

• Note that "high entropy" is not necessarily the same thing as "random-looking". Compare xkcd: Random Number, which, though tongue-in-cheek, makes a valid point, in that randomness (or entropy) is a property of the method of generation, not a property of the result, and thus cannot be determined by looking only at the result. The entropy of `password` could be 26^8 ~ 2^37.6, same as that of `bpgpaxdh` or `gsioaugi`; that's just not very likely.
– user
May 13, 2017 at 21:19

There's no contradiction here as long as you consider the issue in probabilistic terms. For example:

The reason I'm confused is that I thought that all encryption was supposed to do is make it as difficult as brute forcing the key to go from the cipher text to the plain text. It seems to me like there could be an AES key that would produce an all 0 ciphertext given a certain plaintext.

Yes, it's certainly possible that some combination of key and plaintext might produce all-zero ciphertext. But since keys are meant to be selected at random, if such a combination even exists the chance that it would occur in practice is just astronomically unlikely.

One of the key security notions for ciphers is indistinguishability under chosen-plaintext attack ("IND-CPA"), which says (roughly) that an adversary cannot efficiently tell ciphertexts apart from uniform random bits, even if they choose the plaintexts to be encrypted. More precisely, any algorithm that succeeds at distinguishing the cipher must be prohibitively expensive (e.g., brute-forcing a 128-bit key).

This means that we can draw good conclusions about the compressibility of ciphertexts just by reasoning about the compressibility of uniform random bit strings. And it comes down to this: for a fixed compression algorithm, if you pick an n-bit string at random, the chance that the algorithm will compress the string you picked to a length of m bits (m < n) goes down exponentially with m. If you could write an efficient (non-brute force) algorithm that achieved better success than this at compressing ciphertexts, then the cipher's security would be suspect.

Compression and encryption both produce high-entropy outputs, but by different means and for different reasons.

Compression removes redundancy (low entropy), thus raising the average entropy. Consider a sequence like `111111111`; little entropy as each byte is the same. Now, pseudo-RLE it to `1x9;`; it's now half the length, and each stored byte is different. By removing the same, you're left with more differences; makes sense.

Encryption doesn't usually change the output size; increasing it if anything. That's why you want to compress before you encrypt: higher-entropy (usually less-guessable) plaintext and fewer bytes to encrypt. To increase output entropy, encryption mixes the entropy in the key with the entropy in the plaintext. The goal is to max out the output's distribution so that closely-related inputs still have varied and uniform output distribution.

It's because "abc" outputs wildly different than "abd" that attackers can't tell how close a particular guess is: they must nail the key exactly or it won't work at all. Contrast this with a tumbler deadbolt where the attacker knows he's just "1 pin away" and it's worth a little more effort. Without feedback attackers must resort to brute-force, and because that brute-force currently is hard/expensive/slow, the attacker is both disincentivized and mathematically impeded.

• The entropy of a length of compressed data is the same as that of the corresponding uncompressed data, if (and only if) the compression algorithm is lossless. Entropy is about degree of uncertainty about the information content, and has nothing to do with how that uncertainty is expressed or stored. As an extreme example, the entropy of the 256 bit SHA-256 hash ca978112ca1bbdcafac231b39a23dc4da786eff8147c4e72b9807785afee48bb is about 4.7 bits, if you know that the input is a single lowercase US ASCII letter; that entropy is just spread out over 256 bits instead of 5 bits.
– user
May 13, 2017 at 21:15
• @MichaelKjörling: i speak of entropy density; bits per byte, like `ent` reports... May 13, 2017 at 21:23