9
$\begingroup$

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).

Improve this question
$\endgroup$
3
  • $\begingroup$ (*) (where there is hardly a paragraph which doesn't criticize Bruce Schneier's Applied Cryptography) $\endgroup$
    – Cedric Martin
    Commented Mar 20, 2014 at 23:45
  • 2
    $\begingroup$ 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". $\;\;\;\;$ $\endgroup$
    – user991
    Commented Mar 20, 2014 at 23:53
  • $\begingroup$ 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. $\endgroup$
    – Jeff-Inventor ChromeOS
    Commented Aug 23, 2014 at 6:29

2 Answers 2

Reset to default
8
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I think "it is much less difficult to gain information" should be "it is much more difficult to gain information"? $\endgroup$
    – Matt Nordhoff
    Commented Mar 22, 2014 at 13:34
  • $\begingroup$ indeed you are correct $\endgroup$
    – Richie Frame
    Commented Aug 22, 2014 at 19:05
4
$\begingroup$

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 https://security.stackexchange.com/q/19911/971 and https://security.stackexchange.com/q/20406/971 and https://security.stackexchange.com/q/39925/971 for detailed discussion of those attacks over on IT Security.SE.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – dave_thompson_085
    Commented Aug 23, 2014 at 14:20
  • $\begingroup$ "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. $\endgroup$
    – D.W.
    Commented Aug 24, 2014 at 2:58
  • $\begingroup$ 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?) ... $\endgroup$
    – dave_thompson_085
    Commented Aug 27, 2014 at 6:40
  • $\begingroup$ ... 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. $\endgroup$
    – dave_thompson_085
    Commented Aug 27, 2014 at 6:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.