90

I am writing a VPN system which encrypts (AES256) its traffic across the net (Why write my own when there are 1,000,001 others already out there? Well, mine is a special one for a specific task that none of the others fit).

Basically I want to run my thinking past you to make sure I'm doing this in the right order.

At the moment packets are just encrypted before being sent out, but I want to add some level of compression to them to optimize the tranfer of data a little. Not heavy compression - I don't want to max out the CPU all the time, but I want to make sure the compression is going to be as efficient as possible.

So, my thinking is, I should compress the packets before encrypting as an unencrypted packet will compress better than an encrypted one? Or the other way around?

I will probably be using zlib for the compression.

Read more on the Super User blog.

Improve this question
8

7 Answers 7

Reset to default
182

If the encryption is done properly then the result is basically random data. Most compression schemes work by finding patterns in your data that can be in some way factored out, and thanks to the encryption now there are none; the data is completely incompressible.

Compress before you encrypt.

Improve this answer
11
  • 44
    More important: compression adds entropy. Adding entropy is good for your encryption (harder to break with known-plaintext attacks).
    – Olli
    Mar 15, 2011 at 10:52
  • 9
    Also, encrypting costs resources, encrypting a smaller file will take less resources. So compress before encrypt.
    – GAThrawn
    Mar 15, 2011 at 16:23
  • 10
    @Olli - not necessarily if the compression scheme adds known text. In the worst case imagine if it put a known 512byte header on the front of the data and you were using a block mode encryption.
    – Martin Beckett
    Mar 15, 2011 at 17:25
  • 28
    I'm not sure why @Olli's comment would get upvoted, as it is incorrect; not only is it significantly less important, for any half-decent encryption it should be not important at all. That is, the strength of the encryption should be completely unrelated to the entropy of the message.
    – BlueRaja - Danny Pflughoeft
    Mar 15, 2011 at 19:51
  • 8
    If you compress at all, it can only really be done before encrypting the message, but bear in mind, this may leak information about 'compressability' of the original message, so you'll want to consider if there are any consequences to this side channel. Consider a fixed sized file that is either all 0s or a message. The all 0 file will result in a smaller payload under any reasonable compression scheme. Not likely an issue in this particular use case though.
    – Edward Kmett
    Mar 15, 2011 at 20:00
22

Compress before encryption. Compressed data can vary considerably for small changes in the source data, therefore making it very difficult to perform differential cryptanalysis.

Also, as Mr.Alpha points out, if you encrypt first, the result is very difficult to compress.

Improve this answer
1
  • 12
    Well, this is correct, but was posted 2 hours before you posted... Entropy
    – Konerak
    Mar 15, 2011 at 16:43
3

Even if it depends on the specific use-case, I would advise Encrypt-then-Compress. Otherwise an attacker could leak information from the number of encrypted blocks.

We assume a user sending a message to the server and an attacker with the possibility to append text to the user message before sending (via javascript e.g.). The user wants to send some sensible data to the server and the attacker wants to get this data. So he can try to append different messages to the data the user sends to the server. Then the user compresses his message and the appended text from the attacker. We assume a DEFLATE LZ77 compression, so the function replaces same information with a pointer to first appearance. So if the attacker can reproduce the hole plaintext, the compression-function reduces the size of the plain text to the original size and a pointer. And after the encryption, the attacker can count the number of cipher blocks, so he can see, if his appended data were the same as the data the user sent to the server. Even if this case sounds a little bit constructed, it is a serious security issue in TLS. This idea is used by an attack called CRIME to leak cookies in a TLS connection to steal sessions.

source: http://www.ekoparty.org/archive/2012/CRIME_ekoparty2012.pdf

Improve this answer
2

My view is that when you compress a message you project it to a lower dimension and therefor there are fewer bits, which means that the compressed message (assuming lossless compressioon) has the same information in fewer bits (the ones you got rid were redundant!) So you have more information per bit and consequently more entropy per bit, but the same total entropy as you had before when the message was not compressed. Now, randomness is another matter and that is where the patterns in compression can throw a monkey wrench.

Improve this answer
1

Compression should be done before encryption. a user doesn't wants to spend time waiting for the transfer of data , but he/she needs it to be immediately done without wasting any time.

Improve this answer
1

Compression before encryption as has been pointed out earlier. Compression looks for structure it can compress. Encryption scrambles the data so as to avoid structure being detected. By compressing first you're much more likely to have a smaller file and thus less payload to transfer. Encryption is going to do it's job regardless if it's compressed or not and, again as pointed out earlier, is likely to be more difficult to perform differential cryptanalysis on a compressed file.

Improve this answer
1
  • This appears to be a repeat of the accepted and second answers. Each answer should contribute a substantively new solution to the question.
    – fixer1234
    Jun 19, 2015 at 20:24
0

Compression reduces information entropy. Maximum compression makes entropy minimum. For a perfectly encrypted data (noise) maximum and minimum entropy is the same.

Improve this answer
6
  • 2
    Wait, don't you have that backwards? I thought entropy increased as redundancy decreased. Therefore compression should increase entropy.
    – Zan Lynx
    Mar 16, 2011 at 20:06
  • Nop, less entropy = more patterns. Randomness has most entropy.
    – AbiusX
    Mar 16, 2011 at 20:11
  • 1
    But it is information entropy so it is all about meaning. Randomness doesn't mean anything so it doesn't apply. An English sentence can have letters changed and still mean the same thing so it has low entropy. A compressed English sentence might be unreadable if a single bit changes so it has the most. Or so I think.
    – Zan Lynx
    Mar 16, 2011 at 20:30
  • Entropy is not about sense and ability to read or understand, its all about patterns. Compressed files are full of patterns.
    – AbiusX
    Mar 16, 2011 at 22:45
  • 1
    @AbiusX: Right. Patterns. And the fewer patterns, the more entropy. Which means that compression which replaces all repeated patterns with a single copy increases entropy.
    – Zan Lynx
    Mar 16, 2011 at 23:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .