Tell me more ×
IT Security Stack Exchange is a question and answer site for IT security professionals. It's 100% free, no registration required.
up vote 11 down vote favorite
2

If we want both encryption and compression during transmission then what will be the most preferable order.

  1. Encrypt then compress
  2. Compress then encrypt
share|improve this question
Do not forget integrity protection. In most settings it is as important as encryption. It can be done with MACs (for example HMAC) in a symmetric setting or signatures in an asymmetric setting. – Perseids Sep 10 '12 at 19:52
That looks like a question from the coursera cryptography course's exams. – Zzz Sep 11 '12 at 4:09

3 Answers

up vote 20 down vote accepted

You should compress before encrypting.

Encryption turns your data into high-entropy data, usually indistinguishable from a random stream. Compression relies on patterns in order to gain any size reduction. Since encryption destroys such patterns, the compression algorithm would be unable to give you much (if any) reduction in size if you apply it to encrypted data.

Compression before encryption also slightly increases your practical resistance against differential cryptanalysis (and certain other attacks) if the attacker can only control the uncompressed plaintext, since the resulting output may be difficult to deduce.

share|improve this answer
11  
However, compression might allow new attacks in some contexts. – Thomas Pornin Sep 10 '12 at 12:21
Wow, never even knew about that attack. Great writeup, too! – Polynomial Sep 10 '12 at 12:34
Attempting to compress encrypted data is a way of testing the diffusion property of the encryption algorithm, it's also a test for key material; neither should compress at all in a perfect world. – lynks Sep 10 '12 at 13:43
@lynks It is not, however, a definitive test of randomness. If the encrypted file does not compress, your cipher isn't a complete joke, but may still very well be insecure in the extreme. If the encrypted file does compress, all hope is lost and you may as well hand over the plaintext to the bad guys. – Thomas Sep 10 '12 at 15:15
2  
@ewanm89: The number of possible compressed messages of length n cannot be greater than the number of possible messages of length n. So, if we average over the set of all possible messages, the average compression ratio (compressed size divided by uncompressed size) cannot be less than 100%. Compression algorithms achieve real-world compression ratios of less than 100% by targeting common patterns at the expense of uncommon ones; so, a truly-randomly-generated message will usually have a compression ratio of greater than 100%. – ruakh Sep 10 '12 at 19:18
show 3 more comments
up vote 4 down vote

I would recommend to first compress the data and than encrypt it.

  1. The compression algorithm might benefit from the knowledge of the data structure and that structure would be disguised by the encryption. An extreme example would be mp3 which can only compress sound data.

  2. you would have to encrypt less data. While when you first encrypt and then compress you would gain no speedup.

share|improve this answer
up vote 9 down vote

If you compress after encryption and the compression does any good (i.e. it really reduces the length by a non-negligible amount) then you can ditch the encryption, it is awfully weak. Encrypted text ought to be indistinguishable from randomness; even badly encrypted data cannot usually be compressed.

Therefore, compress before encryption. This is why protocols which deal with encryption usually include some support for compression, e.g. OpenPGP (section 5.6) and SSL/TLS. In some scenarios, compression can leak information about confidential data (because compression reduces length depending on the data, and encrypted length more or less matches plaintext length); this is the idea behind the new CRIME attack on SSL/TLS.

Fringe exception: if you encrypt a message with OpenPGP and then "ACSII armor" the result, i.e. encode it in Base64, then this encoding enlarges the data by 34%: 3 bytes become 4 characters (plus the odd newline). Compression with DEFLATE will be effective at cancelling this enlargement (thanks to Huffman codes). That's a case of usefulness of compression after encryption -- but, really, that's more compression over Base64, rather than compression over encryption.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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