1
$\begingroup$

I hope this question hasn't been asked before: I searched and couldn't directly find it. It is known that in specific applications, compression followed by encryption leaks information of the length of the compressed message, which, combined with the possibility to inject known plain text in the message, can leak sufficient information as to break the encryption entirely. There are real-world examples where such plain text injection is a possibility, and there, compression+encryption is a bad idea. There are other applications, like VoIP, where data packets have comparable length before compression, but compression will change these lengths in ways that betray sufficient aspects of the data to allow, again, for a leakage of plain text information.

In all these cases, the vector is the variable length of the compressed plain text that is leaked.

This counter-intuitive result is opposite to the old cryptographic idea that "pre-whitening" which is also an effect of compression, is beneficial.

So, my question is: are there cryptographic applications where compression + encryption is beneficial over simply encryption (as old wisdom would have had it), or is compression in several cases dangerous, and at best, sometimes harmless, but never beneficial to encryption ? In other words, is "pre-whitening" still sometimes an advantage, or not ? I'm not talking about the gain in room or bandwidth. I'm talking on the cryptographic side only.

| improve this question | |
$\endgroup$
  • 2
    $\begingroup$ Could you please add some references to your claims? Some seem to be quite conjunctional or maybe even wrong conclusions. For instance, encryption never claims to hide the message length, and for no serious encryption scheme would the message length allow an easier break. Also, our encryption schemes don't care about plain text injections (first time, I read this term), since the adversary is allowed to have an encryption oracle anyway at the very least. There are certain scenarios, where compression and encryption don't go well together, but mostly they are just completely different. $\endgroup$ – tylo Dec 5 '17 at 14:01
  • 1
    $\begingroup$ The CRIME exploit blog.qualys.com/ssllabs/2012/09/14/… for instance. The exploit against compressed VoIP infoworld.com/article/2651445/networking/… I considered this known problems... I didn't know there was anything controversial about it. $\endgroup$ – entrop-x Dec 5 '17 at 15:36
  • 2
    $\begingroup$ It's a security/efficiency trade-off. Sometimes the side channel is not meaningfully exploitable, e.g. Tarsnap uses a secret hash function to decide how to split files into chunks before compressing and deduplicating them. So the adversary can't control or even predict where the chunk boundaries will be, unlike with HTTP cookies. That means that the file confirmation attack on Tahoe-LAFS with convergent encryption doesn't work on Tarsnap. $\endgroup$ – Squeamish Ossifrage Dec 5 '17 at 16:19
  • $\begingroup$ @Squeamish: thanks! But are there some advantages to remove redundancy (compress/pre-whiten) before encryption ? Not so much: can we work around its problems ? But is it sometimes useful on the cryptographic/security side ? $\endgroup$ – entrop-x Dec 5 '17 at 19:23
  • 1
    $\begingroup$ @entrop-x: With a sensible encryption scheme, there is no advantage to removing redundancy. There may be some cases where the damage of a broken encryption scheme is marginally mitigated by compression against certain limited threat models, like the Tarsnap AES-CTR nonce reuse bug. But that's not something to base your security on; that's like having a personal flotation device in the North Atlantic after the Titanic hit the iceberg, rather than not having a personal flotation device. $\endgroup$ – Squeamish Ossifrage Dec 5 '17 at 23:54
1
$\begingroup$

Regarding your comment about the CRIME attack, I think I can write an answer:

TLS is one of the common ways for encrypted communication, which gave the CRIME attack a lot of attention. However, I think you drew the wrong conclusions there:

  • First and foremost, not the encryption scheme was broken. The attack broke the protocol. That is a massive difference.
  • It only affected those TLS versions, which used a different algorithm: DEFLATE. And the attack works only with that, not a general compression algorithm.

And now I have to say, that your conclusion is probably going into the wrong direction. It is the wrong conclusion to say that coupling compression and encryption is bad in general. Here are some conclusions I would draw from this:

  • It's very important to design protocols properly. Someone will find the most unlikely weakness.
  • Think of all possibilities - especially when it comes to user input and third-party libraries and programs. When it comes to security, better expect the worst than missing something crucial.
  • The functionality of DEFLATE is quite horrible when you have to consider that linking backwards with short tokens is actually bad. We can only speculate, that it might have been an oversight when it was permitted as compression algorithm.

Regarding the VoIP weakness: Again, that has nothing to do with the security of the encryption schemes itself. It does not break the encryption, but the conidentiality of the communication.

And the reason for that is the combination of timing, the length and number of each individual message etc. All those criteria are not hidden by encrypting the individual messages, and the error here is from the designers, who might not have considered that it's a bad idea if the flow of the messages (length and density of messages over time) actually reflects the content of the messages.

However, that's a sidechannel in this specific scenario. It is not a weakness in general for compression algorithms, but a very specific situation and the information used is actually outside the scope of the encryption (the meta-data).

I considered this known problems... I didn't know there was anything controversial about it.

The examples are not controversial - but the generalization of them is IMO unreasonable. Also, those incidents actually are not an ideal fit for this site but security-SE would be much more fitting.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Well, the practical implication was nevertheless that the combination of a given compression algorithm in some specific use cases, rendered the whole system more vulnerable than if that compression wasn't there. But my question was rather the opposite. One would have thought intuitively that "removing redundancy" and pre-whitening was a good idea ; even Bruce Schneier advised so in his seminal Applied Cryptography. With the above vulnerabilities, the general advice is now the opposite, but my question was: is Schneier's argument (and general intuition) still valid in SOME cases ? $\endgroup$ – entrop-x Dec 5 '17 at 19:21
  • 3
    $\begingroup$ Applied Cryptography, alas, is a relic of a bygone era, full of voodoo and nonsense and enormous gaps of necessary practical advice between a litany of obsolete cryptosystems, that has been superseded by serious cryptography engineering. See sockpuppet.org/blog/2013/07/22/applied-practical-cryptography for some issues with it, and some errata for its largely much better successor Cryptography Engineering. $\endgroup$ – Squeamish Ossifrage Dec 6 '17 at 0:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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