Take the 2-minute tour ×
Super User is a question and answer site for computer enthusiasts and power users. It's 100% free, no registration required.

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 here: http://blog.superuser.com/2011/03/21/compression-and-encryption

share|improve this question
4  
Writing as "programming"? Would be better suited for Stack Overflow then. –  Suma Mar 15 '11 at 14:07
4  
If I were asking about the programming of it, yes, but I'm not. This is a general compress then encrypt or encrypt then compress question which could apply to just working with plain files if you wanted. The programming side is just context for why I am asking the question. –  Majenko Mar 15 '11 at 14:08
    
    
Probably a question best meant for security.stackexchange.com –  Jeff Ferland Mar 16 '11 at 14:32
1  
They know about compression there do they? –  Majenko Mar 16 '11 at 14:59
show 1 more comment

6 Answers 6

up vote 130 down vote accepted

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.

share|improve this answer
35  
More important: compression adds entropy. Adding entropy is good for your encryption (harder to break with known-plaintext attacks). –  Olli Mar 15 '11 at 10:52
5  
Also, encrypting costs resources, encrypting a smaller file will take less resources. So compress before encrypt. –  GAThrawn Mar 15 '11 at 16:23
7  
@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 '11 at 17:25
10  
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 Mar 15 '11 at 19:51
5  
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 '11 at 20:00
show 5 more comments

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.

share|improve this answer
8  
Well, this is correct, but was posted 2 hours before you posted... Entropy –  Konerak Mar 15 '11 at 16:43
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

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

share|improve this answer
2  
Wait, don't you have that backwards? I thought entropy increased as redundancy decreased. Therefore compression should increase entropy. –  Zan Lynx Mar 16 '11 at 20:06
    
Nop, less entropy = more patterns. Randomness has most entropy. –  AbiusX Mar 16 '11 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 '11 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 '11 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 '11 at 23:58
show 1 more comment

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.