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

91–100 of 249 posts

Re: “Should you encrypt or compress first?”

#91

Post by DanBlake »

zeveb wrote: post #87
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…

> 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 n…

Feel free to upload a 5MB file under your narrow restrictions and I will see if I can reduce it with one of the 20 different compression systems available to me.

Re: “Should you encrypt or compress first?”

#93

Post by appleflaxen »

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.

this difference is because your random text values are not random binary values.

you are trying to bring empirical evidence to an information theoretic fight :(

Re: “Should you encrypt or compress first?”

#94

Post by readams »

DanBlake wrote: post #91
zeveb wrote: post #87

Earlier quoted context omitted.

> 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 n…

Feel free to upload a 5MB file under your narrow restrictions and I will see if I can reduce it with one of the 20 different compression systems available to me.

The larger the random file the _less_ likely you are the successfully compress it.

Everyone here is telling you that you are wrong, and have even clearly demonstrated this through both mathematical reasoning and empirical tests. Quit digging :-)

Re: “Should you encrypt or compress first?”

#95

Post by mikeash »

DanBlake wrote: post #88
charleslmunger wrote: post #70

Earlier quoted context omitted.

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 hu…

That's not encrypted with AES256, that's encrypted with AES256 and then encoded with base64.

Do you understand the difference between base64 and binary data? Base64 only uses six bits per byte. It's designed to allow data to transit cleanly through places which only allow text, such as JSON. Binary data is eight bits per byte. Binary data is what encryption and compression algorithms output. Naturally, if you take data which only uses six bits per byte, and run it through a compression algorithm which is able to use eight bits per byte, you can achieve good compression. But this is illusory, because you expanded the original by 33% when you applied base64 in the first place! All your attempts at compression can be beaten by simply decoding the base64 into the original binary data.

It doesn't matter what magnitude of compression you specified. Random data cannot be compressed at all on average. This is a simple mathematical certainty with a straightforward proof. Encrypted data looks and acts like random data. If you find a way to reliably compress the output of a modern, secure encryption algorithm (not the base64 encoding, but the original binary) then you'll have found a massive security hole in it which will make you famous.

Re: “Should you encrypt or compress first?”

#97

Post by VLM »

biokoda wrote: post #4

If you're compressing audio, the simple solution is to compress using constant bitrate.

Unfortunately one way to define variable bit rate is its compressed CBR.

Rather than defining at the protocol level "insert comfort noise here" at the compression level you get bitstream level "I donno what this stream is at a higher level, but replace the next 1000 bits with zeros".

That's if you do simple sampling. I donno about weird higher level vocoders. I think you could create a constant bit rate vocoder that really is constant. But it'll likely be uncompressible if its a good one because a vocoder basically is a compressor that's specifically very smart about human speech input. If your vocoder output is compressible its not a good one.

I think if you replaced your compression step with run it thru a constant rate vocoder you'd get what you're looking for. Probably.

Re: “Should you encrypt or compress first?”

#98

Post by DanBlake »

mikeash wrote: post #74
DanBlake wrote: post #67

Earlier quoted context omitted.

Im happy to reproduce in other formats. The contents are still random which is the crux of the issue here.

The contents are not purely random. For example, I can predict with 100% certainty that any given byte in the file is not the value zero (ASCII NUL). Try compressing the output of /dev/urandom on your nearest convenient UNIX-like system. If you figure out a way to reliably and significantly compress that, please report back.

My point was never that it was possible 100% of the time. Simply that it was possible some of the time.

Re: “Should you encrypt or compress first?”

#100

Post by mikeash »

DanBlake wrote: post #98
mikeash wrote: post #74

Earlier quoted context omitted.

The contents are not purely random. For example, I can predict with 100% certainty that any given byte in the file is not the value zero (ASCII NUL). Try compressing the output of /dev/urandom on your nearest convenient UNIX-like system. If you figure out a way to reliably and significantly compress that, please report back.

My point was never that it was possible 100% of the time. Simply that it was possible some of the time.

On average, you will expand files, not compress them.

Also, the odds of getting finding even a single encrypted file of that length which can be compressed are lower than the odds of winning the lottery three times in a row. Trust me, you didn't just happen to stumble across a working example. You screwed up the test.

Post reply on HN