Live data from Hacker News

“Should you encrypt or compress first?”

blog.appcanary.com

191–200 of 249 posts

Re: “Should you encrypt or compress first?”

#191

Earlier quoted context omitted.

You can't compress after encryption. Encrypted content should be indistinguishable from random data. So encrypt than compress shouldn't be able to yield any reasonable compression.

wit truly random data, patterns should randomly appear.

Encrypted data is "indistinguishable from random data" but it is not actually random data. No patterns will appear.

Re: “Should you encrypt or compress first?”

#192

Earlier quoted context omitted.

wit truly random data, patterns should randomly appear.

https://en.wikipedia.org/wiki/Entropy_(information_theory)

I'm sorry, that article is far too long to tell me what you are trying to say. All I can gather is, I was wrong

Re: “Should you encrypt or compress first?”

#193

Earlier quoted context omitted.

You can't compress after encryption. Encrypted content should be indistinguishable from random data. So encrypt than compress shouldn't be able to yield any reasonable compression.

wit truly random data, patterns should randomly appear.

There's a pretty easy proof to show why compression of truly random data is impossible. Let C be a compression algorithm. Assume that for all bit strings S, C(S) is not longer than S, and assume that there exists strings S' such that C(S') is shorter than S'. Also, assume that for any two distinct bit strings S1 and S2, C(S1) != C(S2). Let S'' be the shortest such string: the shortest string that C shortens. Let the length of S'' be M, and the length of C(S'') be N = 1, and by assumption every string of length N does not have its length changed by C. There are 2^N strings of length N, and by assumption it is easy to see that since the images of any pair of N bit strings under C are distinct, every string of N bits is the image of some other N bit string. But now, S'' has length M but has an image of length N. This necessarily collides with the image of some string of length N, a contradiction. Thus, for any compression algorithm which is injective (in effect, reversible) and successfully shortens some strings, the algorithm must lengthen some others.

What this short proof shows is that even though random data may have patterns, no compression algorithm can successfully leverage this for every random string.

Re: “Should you encrypt or compress first?”

#195

So if the length of the resulting message is leaking information, salt it by adding some extra random bits to the end to increase the length by a random amount.

Which may be useful, unless you can use a padding oracle attack or timing attack, or you're using something stupid like ECB mode, or you aren't authenticating your ciphertext.

In general, it is safe to assume that whatever countermeasure you are thinking of has already been defeated by an attacker, unless you have researched for a really long time and found no possible alternative.

Re: “Should you encrypt or compress first?”

#196

Earlier quoted context omitted.

https://en.wikipedia.org/wiki/Entropy_(information_theory)

I'm sorry, that article is far too long to tell me what you are trying to say. All I can gather is, I was wrong

tl;dr Random data may appear to have patterns, but those patterns do not repeat, so they cannot be compressed.

Re: “Should you encrypt or compress first?”

#197

Earlier quoted context omitted.

It's not just you. I've never used encryption or compression in any serious way, but the right answer seems obvious if you know the definitions of encryption and compression.

Really? I've been reading, and following encryption news for 10+ years, and it had never occurred to me that you should not compress prior to encrypting. The article was an eye opener for me - in hindsight, maybe obvious, but I bet 90% of your average technical audience wouldn't realize that you should not compress prior to encrypting.

mea culpa.

I am guilty of not waiting around for him to get to his point 3/4 of the way through the article. If you're trying to bring up subtle issues, don't bury the lede.

What he's really trying to say is that you shouldn't compress sensitive data at all. And now we're into the non obvious stuff that some of us are clearly talking past each other about.

Personally, I think he's painting too broad a stroke and some domains don't have this problem, and for some there are other factors at play such as insufficient block size giving away too much information.

You could for instance probably figure out who is speaking just by the pattern of pauses, without even trying to decrypt what is said.

And then there's session cookies, which I despair of ever being secure. Because of the chosen plaintext of CRIME, even a large block size would only make the setup phase take a bit longer (finding a message that is one byte bigger than the block size). Encryption is insufficient to protect shared secrets.

Re: “Should you encrypt or compress first?”

#198

Earlier quoted context omitted.

https://en.wikipedia.org/wiki/Entropy_(information_theory)

I'm sorry, that article is far too long to tell me what you are trying to say. All I can gather is, I was wrong

That is still your problem and you need to take responsibility for it. It is wiser to learn and know what you're talking about, don't just add ambient, useless, incorrect noise.

Re: “Should you encrypt or compress first?”

#199
post #29

A more interesting question is whether to compress or sign first. There's an interesting article on that topic by Ted Unangst: "preauthenticated decryption considered harmful" http://www.tedunangst.com/flak/post/preauthenticated-decrypt... EDIT: Although the article talks about encrypt+sign versus sign+encrypt, the same argument goes for compress+sign versus sign+compress. You shouldn't do anything with untrusted dat…

From what I've read it is "encrypt then sign, unless signatures are optional and could be stripped from the message in which case things are complicated"
Post reply on HN