Using compression to test encryption

Question

Is the uncompressibility of encrypted data a necessary property for a good cryptographic algorithm?

To make a crude experiment, I encrypted an 8K file with all 'A' and then compressed both the encrypted and the unencrypted file.

The compressed unencrypted file went down to less than 200 bytes while the conpressed encrypted file became larger than the encrypted file.

I think that while this result says nothing about the goodness of the encryption, the opposite result (i.e. if the encrypted file would shrink after compression) would have revelead a weakness of the encrypting algorithm.

Am I correct or am I missing something about the relation between encryption and compression?

Answer 1

Yes, a ciphertext of a bulk encryption algorithm normally should not be compressible to less than the plaintext size¹ (at least, if the compression function does not know the encryption key), other than in some corner cases which will occur only with negligible probability (like you hitting the one plaintext which will encrypt to the all-zero-string).

¹_{Of course, if the encryption algorithm applies some encoding after encrypting which makes the ciphertext larger, like PGP's ASCII-armor, Base64 or Hexadecimal encoding, you can compress this resulting encoded ciphertext, but not to less than the original plaintext size. Similar things could occur with some asymmetrical encryption algorithms, which have slightly biased output, when (mis)used for bulk encryption - don't do this.}

If the compressor knows the algorithm and key, it can simply decrypt the ciphertext and then compress the plaintext, of course.

With bad modes of operation, such as ECB mode, some repetitions in the plain text will also show through in the cipher text (see this famous example in Wikipeda), which then might show by compressibility of the ciphertext (the ECB image is bigger than the plain"text" one, but still smaller than the CBC one).

On the other hand, non-compressibility of ciphertext with generic compression algorithms is given by every not totally trivial encryption algorithm, even if they have to be categorized as broken by every aspect.