Why is ciphertext from low entropy plaintext not compressible? This comes following a discussion with a colleague.


My plaintext file plain consists of a about 100,000 lines of "all work and
no play...". It's size is: 2.2 MB.
Compressed it is: 5.4kB
I encrypt the original:

openssl aes-128-cbc -in plain -out plain.ENC


plain.ENC is marginally bigger than the original, which I would expect.
I compress the encrypted copy: gzip plain.ENC. But I observe that the
compressed copy is now marginally larger than plain.ENC.


Assuming the entropy of the original file is on the order of ~1000-10000 bits, why is the corresponding ciphertext incompressable? My intuitive notion of the entropy of a string is the minimal number of bits required to produce that string. If the string is the 3 MB long cipher text, it was generated with a 1000-bit entropy string encrypted with an AES implementation (probably no more than a few thousand bits), as well as a few-hundred bit key. Intuitively, to me, the entropy of the cipher text should be no more than the sum of the entropies of the strings and procedures that generate it.

So, my question is: Is my intuitive notion completely wrong? If we extended the low-entropy file to be orders of magnitude larger, would we begin to observe compressibility in the ciphertext?
Well, your definition of entropy is known as Kolmogorov complexity, and it's not so much that it is incorrect, as it is that it is inapplicable to what gzip does.

For example, the value $\pi$ can also be generated by a short program; however, if you attempt to compress a 2.2Mbyte sample of the binary expansion, you'll also find that gzip will also not be able to compress it.

What we can tell from that is that gzip doesn't actually do a good job of estimating the Kolmogorov complexity.  Now, this is not actually a major criticism of gzip; it is actually impossible to write a program that computes it (!).

Instead of attempting to wrestle with Kolmogorov complexity, what gzip (and every other compression algorithm out there) relies on to compress the data is heuristics. That is, it has a model of redundancies that appear in real plaintexts (such as repeated substrings), and is able to take advantage of those redundancies to shorten the length.  Now, if that model corresponds to the text it is given, gzip can compress quite well; if the model doesn't correspond (and both the encrypted text and the binary expansion of $\pi$ fall in this camp), it can't compress at all.

And, no, encrypting more data would not make the result any more compressible.