“Should you encrypt or compress first?” • Hacker News Board

Re: “Should you encrypt or compress first?”

#121

Post by lisper » Tue, Jun 28, 2016, 5:46 PM UTC

fleitz wrote: post #115

lisper wrote: post #39

Earlier quoted context omitted.

> If security is important, the answer to that is no It's a little more nuanced than that. Compression may cause information leaks or it can prevent them depending on the circumstances. If you're encrypting an audio stream, then compressing it first can cause leaks. If you're encrypting a document, then compressing it first may prevent leaks.

It's more about whether the attacker has control of the any portion of the compressed contents. If they have control over the stream then you don't want compression, if they don't you do.

No, control is not necessary for compression to leak information. It's enough for the attacker simply to know something about the original stream content (e.g. that it is audio) and how it compresses.

Re: “Should you encrypt or compress first?”

#122

Post by jdmichal » Tue, Jun 28, 2016, 5:47 PM UTC

DanBlake wrote: post #90

IanCal wrote: post #58

Earlier quoted context omitted.

> 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'

You're answering a question that no one is interested in. The problem isn't "can any singular instance of an encrypted output be compressed". That's a trivial conclusion -- as it's theoretically completely random bits, of course some combinations of those bits are going to be compressible, maybe even highly compressible. It might be that the encrypted output is entirely a single repeated byte, in which case a 4-gigabyte message could be compressed to 4 bytes (being the integer representing how many times to repeat the byte).

The real question is, can you reliably compress encrypted messages in general? And, given that the encryption is not broken, the answer is no.

Re: “Should you encrypt or compress first?”

#123

Post by jayd16 » Tue, Jun 28, 2016, 5:49 PM UTC

Would be great if Apple understood this and compressed IPA contents before encrypting.

Instead, when you submit something to the AppStore, you end up with a much bigger app than the one you uploaded.

To add insult to injury, if you ask Apple about this fuck up you get an esoteric support email about removing "contiguous zeros." As in, "make your app less compressible so it won't be obvious we're doing this wrong."

Re: “Should you encrypt or compress first?”

#124

Post by lisper » Tue, Jun 28, 2016, 5:49 PM UTC

StavrosK wrote: post #111

lisper wrote: post #71

Earlier quoted context omitted.

Why would you use a stream cipher to encrypt a document?

Why wouldn't you?

http://security.stackexchange.com/questions/334/advantages-a...

Not that this really matters. The advantages/disadvantages of compression are the same in both cases.

Re: “Should you encrypt or compress first?”

#125

Post by mikeash » Tue, Jun 28, 2016, 5:49 PM UTC

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.

Here you go: https://mikeash.com/tmp/randomfile.bin

If you manage to get that under 5MB by applying any tool which allows recovering the original data, I will be most interested to know how you did it.

Re: “Should you encrypt or compress first?”

#126

Post by ontoillogical » Tue, Jun 28, 2016, 5:51 PM UTC

hueving wrote: post #92

That quoted voip paper isn't actually as damaging as it sounds. IIRC that 0.6 rating was for less than half of the words so if you're trying to listen to a conversation to get something meaningful, it's probably not going to happen.

That's a good point, and the .6 is an optimistic score (I think it was from running a subset of their model)

I got the sense that the authors felt that this proves an attack of this sort was possible and viable, but that their model wasn't quite there yet.

OTOH this should be enough to acknowledge that the voice encryption/compression scheme they are attacking is not secure.

Re: “Should you encrypt or compress first?”

#127

Post by danbruc » Tue, Jun 28, 2016, 5:51 PM UTC

lisper wrote: post #101

belorn wrote: post #80

Earlier quoted context omitted.

Could you elaborate what kind of scenario would work on a audio stream but not on a document? In order to use CRIME, the attacker would need to repeatably injected content before the compression stage in order to test if it matches some part of the source. Audio is kind of heavy uncompressed and aren't normally streamed as such.

A raw audio stream is a constant bit rate stream. If you compress it, it becomes (in general) a variable bit rate stream. The bit rate contains information about the raw audio which survives encryption. If you compress a document that simply obscures the size of the original document.

If you compress a document that simply obscures the size of the original document.

That is not generally true - if you compress AAA and ABC then the compressed version also leaks information about the content exactly like in the case of an audio stream and it reveals more information then the lengths of the uncompressed documents which don't differ.

Re: “Should you encrypt or compress first?”

#128

Post by arjie » Tue, Jun 28, 2016, 5:52 PM UTC

None of this seems to apply to documents you generate to supply to someone else you trust. Compress and encrypt seems perfectly fine.

Re: “Should you encrypt or compress first?”

#129

Post by PhasmaFelis » Tue, Jun 28, 2016, 5:53 PM UTC

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.

You were a newbie too, once. Some people read Hacker News precisely to learn things like this.

Re: “Should you encrypt or compress first?”

#130

Post by dllthomas » Tue, Jun 28, 2016, 5:54 PM UTC

lmm wrote: post #61

dllthomas wrote: post #57

Earlier quoted context omitted.

What if the number of padding bytes is a function of the contents?

That would add noise to the information the attacker gets, but ultimately the "output" length has to be correlated with the input length, so you can't ever get the amount of information the attacker gets down to zero which is what's needed to make a cipher secure.

'ultimately the "output" length has to be correlated with the input length'

But perhaps not relative to the size of the secret data, right?

(Note that I'm not saying, "Oh, obviously we should just do this to avoid that attack" - I'm hoping to learn by carefully understanding where it breaks down).