# How does compression before encryption leak info about the input?

Apparently current best practices recommend that you do not compress before you encrypt.

For example in this blog entry (*):

http://sockpuppet.org/blog/2013/07/22/applied-practical-cryptography/

It is written:

Developers shouldn’t compress plaintext before encrypting.

Or in this question here on crypto.se:

Is compressing data prior to encryption necessary to reduce plaintext redundancy?

several people answer that compressing before encryption is actually harmful.

What I really don't understand is that apparently the explanation is that the compression algorithms used leak information about the size of the plaintext input!?

But in which way does not using compression before encryption not leak info about the length of the input too?

What additional infos are leaked by compression algorithms that wouldn't be leaked by not doing compression?

If padding is used on plaintext encrypted without compression, couldn't paddding be used too before encrypting compressed data (or data to be compressed)?

Also: is it really a given that the attacks you make possible by using compression before encryption are more of a problem than the attacks made possible by not compressing before encrypting? (the latter being the reason for which, during more than two decades, it was always advised to compress before encryption).

-
(*) (where there is hardly a paragraph which doesn't criticize Bruce Schneier's Applied Cryptography) – Cedric Martin Mar 20 '14 at 23:45
Compressing before encryption leaks the length of the compressed plaintext (roughly, the estimated entropy of the plaintext) instead of the length of the actual plaintext. $\:$ Length-padding would just reduce the relevant length leakage in either case. $\:$ I'm pretty sure that's not "really a given". $\;\;\;\;$ – Ricky Demer Mar 20 '14 at 23:53
I wonder if the vulnerability from known entropy attacks is really higher than the enhanced security from more entropy dense cleartext. Provided there is padding, I can't imagine how known entropy leaks more than a bit or two of information. – Jeff-Inventor ChromeOS Aug 23 '14 at 6:29

The problem is not with compression and encryption, it is with the protocol that is being used, and the type of data being compressed (or not) prior to encryption.

The most damning leaks are on protocols that were either designed to be compressed without encryption, or encrypted without compression.

The best example I have is VOIP systems that use a variable bitrate compression prior to encryption. Since the gaps between words and even syllables are highly compressed, and the words and syllables themselves are compressed at different rates depending on their content, traffic pattern analysis can be used to accurately detect spoken words and phrases. Public research only began within the last decade, but NSA designed encrypted voice protocols used constant bitrate compression and i/o clocking, meaning the technique was either known or they expected it to be exploited.

An excellent presentation of the subject here, as well as a more detailed initial report from 2008.

When a protocol is properly designed with compression and encryption in mind, it is much more difficult to gain information. For example, an SMS message where the entire message space is encrypted using AES-GCM, and the text is first compressed, allowing potentially more than 160 characters to be included in a single message. Some of the SMS must be used for nonce/auth tag, so the more message it can fit the better. This is of course an additional encryption I am talking about and not part of the SMS protocol. Multiple sequential SMS messages reveal information about the message size (being larger than the limit), and compression can prevent that if done correctly.

Padding any compressed plaintext to a multiple of some given number (say 128 bytes) prior to encryption makes certain attacks less effective, especially if the majority of plaintexts are small (like text messages). The methods used to pad the data are also important, as there are attacks that exploit padding used in various protocols.

-
I think "it is much less difficult to gain information" should be "it is much more difficult to gain information"? – Matt Nordhoff Mar 22 '14 at 13:34
indeed you are correct – Richie Frame Aug 22 '14 at 19:05

Read about the CRIME and BREACH attacks. They are the classic example where compression before encryption can leak information about the input. The length of the compressed data leaks information about the contents of the data itself.

See also http://security.stackexchange.com/q/19911/971 and http://security.stackexchange.com/q/20406/971 and http://security.stackexchange.com/q/39925/971 for detailed discussion of those attacks over on IT Security.SE.

-
CRIME and BREACH need chosen plaintext, and the blog criticizes compression "If attackers control plaintext". That is often (not always) true on the web, but there are cases where it isn't, e.g. compress then encrypt a backup of my company's HR database. And I believe all known attacks are for (lossless) text compression which matches (sub)strings like deflate/gzip, and other kinds of compression may be harder: I'm pretty sure adding an "evil" chunk to a JPEG image won't leak the "good" part. – dave_thompson_085 Aug 23 '14 at 14:20
"I'm pretty sure adding an "evil" chunk to a JPEG image won't leak the "good" part." - I don't know how you could possibly know that. Anyway, I believe my answer answers that question that was asked. – D.W. Aug 24 '14 at 2:58
I am not an image expert, but from what I've read from time to time and confirmed by wikipedia, JPEG compresses each 8x8 pixel block independently and is not affected by 'distant' info. For example if I construct and serve an image consisting of one of my dogs plus a picture chosen by (possibly) an adversary, JPEG should give no information on whether they have guessed the correct dog, or even color or breed. (On the internet nobody knows which dog you are?) ... – dave_thompson_085 Aug 27 '14 at 6:40
... As I read the question it was "is compress before encrypt always or nearly always bad". You say correctly it is sometimes bad -- and certainly something to be careful of. But I think it is useful to say it isn't always bad. – dave_thompson_085 Aug 27 '14 at 6:42