Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

“Should you encrypt or compress first?”

blog.appcanary.com

Post reply on HN
Print view View original

81–90 of 249 posts

Re: “Should you encrypt or compress first?”

#81

Post by mikeash »

danielweber wrote: post #6
usloth_wandows wrote: post #3

I thought this was common sense. Compress then encrypt. Encryption leads to higher entropy, therefore less effective compression.

The article is about why that can be wrong.

The article agrees, as should anyone who understands encryption and compression: encrypted data can't be compressed, so encrypt-then-compress is pointless.

The article also covers why compress-then-encrypt is dangerous. But it's not a dichotomy. Those aren't your only two choices, you can also just encrypt and not compress.

Re: “Should you encrypt or compress first?”

#82

Post by olliej »

DanBlake wrote: post #48
orlp wrote: post #14

There's no compress or encrypt _first_. It's just compress or not, before encrypting. If security is important, the answer to that is no, unless you're an expert and familiar with CRIME and related attacks. Compression after encryption is useless, as there should be NO recognizable patterns to exploit after the encryption.

>Compression after encryption is useless, as there should be NO recognizable patterns to exploit after the encryption. Not to nitpick, but this is incorrect. A encrypted file can very well have something like 100 X's in a row which the compression system could turn from XXXXXXXXXXXXXXXX.... into (100 x's go here) - Lousy example I know but it gets the point across. Its also easy enough to test- Just encrypt a file th…

No. If your encryption is not busted then the entropy under /any/ model tends to perfect. If a model is able to predict with /any/ success then your crypto is probably broken.

So yes, it is random, and 100 X's could appear in a row. But if your model can effectively compress that, then the model has to be wasting space for all the other sequences.

Let's just imagine that you are doing some like basic run length coding (gif! Or jif if you're wrong :) )

So 100 x's turns into (100, x). So you've compressed that part of the stream. Unfortunately everything else is likely (1,a), etc so every other symbol/byte increases in size. If we look at the stream probabilities we get something like P(nX)=(P(X)^n) -- very rough I haven't been at uni for a long time :). You can do a bunch of reasonably simple math do verify it but you eventually end up with something that your average symbol size is sum{x in X}-log(P(x))/|X|. Where X is your set of possible symbols (n,x:X).

For a given stream that is not encrypted you may save some space representing the input bytes, but each symbol (n,X) has at /least/ 1 extra bit of information. Overall you can save space.

But let's look at the encrypted data. Each input symbol is independent so your probability of any sequence in the input is equal. You will typically have a run length of 1 (P=0.5), 2 (P=0.5), ...

So 50% of your output symbols will have at least one extra bit of information /added/. This means your output by necessity is bigger than the input.

I used RLE as an example here, but it's true for all compression schemes. This is a necessary property for compression to work: for any data that compresses by n% under a given model there must be some input that increases in size by n% (or some such, again, long time since uni). I believe Wikipedia has an article on the pigeon hole problem or some such that probably explains this better than I can.

Re: “Should you encrypt or compress first?”

#83

Post by r1ch »

DanBlake wrote: post #60
jessriedel wrote: post #53

Earlier quoted context omitted.

No. If the encrypted output is randomly distributed, as it should be, then the expected number of bits cannot be reduced through compression. If it successfully compresses some files, it will make some files larger. For random data, the change will be negligible with overwhelming probability, plus there will be overhead.

Using a random text generator http://pasted.co/encrypted.txt ( 10,002 bytes ) Then compressed it with winrar http://pasted.co/compressed.rar ( 7,743 bytes ) Roughly 20% compression isnt meaningless- so I fail to see why you are just giving a flat 'no' when its obvious what you are saying is untrue.

You aren't performing your test properly. Encryption doesn't output random text, it outputs bytes of data (0-255). It should be obvious that compressing text is possible.

$ dd if=/dev/urandom of=test bs=1k count=10

$ cat test | gzip -9 > test.gz

$ cat test | bzip2 -9 > test.bz2

$ ls -al test*

-rw-r--r-- 1 r1ch r1ch 10240 Jun 28 16:30 test

-rw-r--r-- 1 r1ch r1ch 10739 Jun 28 16:31 test.bz2

-rw-r--r-- 1 r1ch r1ch 10263 Jun 28 16:31 test.gz

Random data is not compressible.

$ dd if=/dev/zero of=test bs=1k count=10

$ openssl enc -in test -aes-256-ctr -out test.encrypted

$ cat test.encrypted | gzip -9 > test.encrypted.gz

$ cat test.encrypted | bzip2 -9 > test.encrypted.bz2

$ ls -al test*

-rw-r--r-- 1 r1ch r1ch 10240 Jun 28 16:32 test

-rw-r--r-- 1 r1ch r1ch 10256 Jun 28 16:33 test.encrypted

-rw-r--r-- 1 r1ch r1ch 10737 Jun 28 16:34 test.encrypted.bz2

-rw-r--r-- 1 r1ch r1ch 10279 Jun 28 16:33 test.encrypted.gz

Encrypted zeroes are not compressible.

Re: “Should you encrypt or compress first?”

#85

Post by hinkley »

b101010 wrote: post #63
vog wrote: post #50

Earlier quoted context omitted.

Good catch! Although the article talks about encrypt+sign versus sign+encrypt, the same argument goes for compress+sign versus sign+compress.

Why is the debate about "compress/encrypt then sign" vs "sign then compress/encrypt"? Is there a non obvious problem with sign then compress/encrypt then sign again? (overcomplicated or unnecessary?)

There are DOS and Trojan attacks against decompression libraries. You definitely want to verify a signature before extracting the archive, but even a 2 pass verification process can leave you with a payload that expands to a terabyte. If your hash algorithm is running at 50MB/s that can take a while.

Re: “Should you encrypt or compress first?”

#86

Post by mcguire »

hinkley wrote: post #65
vog wrote: post #26

Earlier quoted context omitted.

This is exactly what the article says.

Does this really need to be said though? I may be too close to the problem. I've had to explain this to project managers and customers of course, but this is hacker news. It feels like a three page article on why you should put your socks on before your shoes and not after.

Once upon a time I was at a talk given by a visiting professor (associated, I think, with the Horus project[1]; I'm reasonably sure some of you would recognize the name if I could remember it) on designing network protocols using plug-n-play software components. The illustrations he showed used Lego bricks.

His big example was a Lego brick labelled "Compression" and another brick labelled "Encryption", and how you could arbitrarily compose them to achieve different protocols.

Meanwhile, I was sitting at the back of the room wearing my "I'm not a security guy, but this is garbage" look.

[1] http://www.cs.cornell.edu/info/projects/horus/main.html

Re: “Should you encrypt or compress first?”

#87

Post by zeveb »

DanBlake wrote: post #48
orlp wrote: post #14

There's no compress or encrypt _first_. It's just compress or not, before encrypting. If security is important, the answer to that is no, unless you're an expert and familiar with CRIME and related attacks. Compression after encryption is useless, as there should be NO recognizable patterns to exploit after the encryption.

>Compression after encryption is useless, as there should be NO recognizable patterns to exploit after the encryption. Not to nitpick, but this is incorrect. A encrypted file can very well have something like 100 X's in a row which the compression system could turn from XXXXXXXXXXXXXXXX.... into (100 x's go here) - Lousy example I know but it gets the point across. Its also easy enough to test- Just encrypt a file th…

> A encrypted file can very well have something like 100 X's in a row

Any decent encryption algorithm has output indistinguishable from random noise; the odds of 100 Xes in a row in random data is 1:2^800; there are only 10^80 particles in the universe (2^266), which is 534 base-2 orders of magnitude smaller than 2^800. Yes, every particle in the universe could be a universe of fundamental particles and you'd still never see 100 Xs in a row in a decently-encrypted message.

Re: “Should you encrypt or compress first?”

#88

Post by DanBlake »

charleslmunger wrote: post #70
DanBlake wrote: post #60

Earlier quoted context omitted.

Using a random text generator http://pasted.co/encrypted.txt ( 10,002 bytes ) Then compressed it with winrar http://pasted.co/compressed.rar ( 7,743 bytes ) Roughly 20% compression isnt meaningless- so I fail to see why you are just giving a flat 'no' when its obvious what you are saying is untrue.

Your random text isn't uniformly random - any byte that isn't a letter or number never shows up.

Here it is encrypted with AES256 - Pass is wasteoftime

http://pasted.co/wasteoftime.txt 4,732 bytes

http://pasted.co/wasteoftime.rar 3,753 bytes

Also, if there is issues with using the 'wrong' encryption, I feel thats kind of a straw man argument. Please feel free to upload a file over 5MB which cant be reduced in size through any of the various compression tools.

Also, keep in mind that I never said it would be a huge benefit at all- I only said that SOME compression was possible SOME of the time.

Re: “Should you encrypt or compress first?”

#89

Post by TorKlingberg »

api wrote: post #52
orlp wrote: post #14

There's no compress or encrypt _first_. It's just compress or not, before encrypting. If security is important, the answer to that is no, unless you're an expert and familiar with CRIME and related attacks. Compression after encryption is useless, as there should be NO recognizable patterns to exploit after the encryption.

The rule is: never compress something secret together with something potentially attacker-influenced. If the attacker can influence the traffic, they can potentially gather information about the secret by examining the effect of differing traffic patterns on the size of the encrypted result.

No, the rule is: never compress something secret together with something potentially attacker-influenced, at least if the length of the compressed data leaks.

Re: “Should you encrypt or compress first?”

#90

Post by DanBlake »

IanCal wrote: post #58
DanBlake wrote: post #48

Earlier quoted context omitted.

>Compression after encryption is useless, as there should be NO recognizable patterns to exploit after the encryption. Not to nitpick, but this is incorrect. A encrypted file can very well have something like 100 X's in a row which the compression system could turn from XXXXXXXXXXXXXXXX.... into (100 x's go here) - Lousy example I know but it gets the point across. Its also easy enough to test- Just encrypt a file th…

> It wont be a huge difference in file size, but it will be smaller. may be smaller, not all outputs will be smaller, this is true of all lossless compression algorithms: https://en.wikipedia.org/wiki/Pigeonhole_principle

This is literally all I was saying and people went on a downvote frenzy. People are literally saying that a encrypted output can NEVER be compressed. I was saying that it can (although not all the time!) and the gains would be minimal. Ive corrected the first post with the word 'may'
Post reply on HN