Encryption and Compression

Question

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?

Answer 1

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.

Answer 2

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.