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

221–230 of 249 posts

Re: “Should you encrypt or compress first?”

#221

Post by [deleted] »

pshc wrote: post #205
scj wrote: post #204

Earlier quoted context omitted.

Let's say you are using a one-time pad, and the encrypted text is a string of a million A characters. While unlikely to the point that it is barely worth mentioning, it is possible. And could trivially be compressed. I think your main point is correct, just presented too strongly. In many cases compression after encryption will yield poor results. But I wouldn't go so far as to say that it can't be done.

This seems overly pedantic. In my mind "incompressible" does not mean "there are absolutely zero situations in which the output could be shorter than the input." There will always be (compression scheme, input) combinations that produce smaller outputs. The qualifying criteria is "does expected input data typically compress?" For a reasonable definition of incompressible, properly encrypted data is it.

[deleted]

Re: “Should you encrypt or compress first?”

#223

Post by hinkley »

danielweber wrote: post #156
hinkley wrote: post #65

Earlier quoted context omitted.

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.

Even a few years ago, the "obvious answer" in the infosec space was that you should compress first.

I think most of my upvotes are from people who only read half the article waiting for him to say something interesting and giving up. My grade schooler tells better stories.

As someone else said, the title is terrible. What we are left with in some scenarios is choosing one or the other, not one before the other.

Re: “Should you encrypt or compress first?”

#224

Post by mjevans »

geofft wrote: post #202
mjevans wrote: post #178

Earlier quoted context omitted.

Actually in the context of security compressing the data you're about to encrypt still matters. The problem exposed by the CRIME exploit (and anything similar) is that the size of the payload also can be an indication of the data within it. To combat this, systems which are exchanging data interactively (in a stream) should further pad messages /up to/ a target size (which might be random per message). As I mentioned…

That reduces, but doesn't eliminate, the amount of information you're leaking. If you pad the data to a multiple of some fixed block size, you'll still learn something across the boundary between two block sizes. An attacker can do a CRIME-style attack that includes a wrong password guess plus some of their own padding, and vary the amount of padding until it is just big enough to take n + 1 blocks instead of n . The…

You still want to compress in the first place as a means of removing entropy and some known plain text if possible. Most systems that give you the option of compressing or not do so because you may have already used some other method of compressing the data (E.G. it's a video file or already a compressed transport archive).

The addition of padding, even worthless (hopefully at least pseudo-random) garbage, up to some reasonable minimum message size, is a form of making analysis of message /size/ useless.

Re: “Should you encrypt or compress first?”

#225

Post by hinkley »

DougBTX wrote: post #172
lisper wrote: post #151

Earlier quoted context omitted.

Well, yeah, but the point is that compression can cause the leakage of information through timing that would not otherwise have leaked.

Yes, in other words compression can move information from the content of the data (which is encrypted) to the size of the data (which is not encrypted).

Which is one of the selling points of block cyphers. They may not conceal the magnitude of the payload but they do obscure the exact byte count by rounding up. But that probably doesn't stop CRIME from being workable.

Re: “Should you encrypt or compress first?”

#226

Post by [deleted] »

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.

[deleted]

Re: “Should you encrypt or compress first?”

#227

Post by geofft »

mjevans wrote: post #224
geofft wrote: post #202

Earlier quoted context omitted.

That reduces, but doesn't eliminate, the amount of information you're leaking. If you pad the data to a multiple of some fixed block size, you'll still learn something across the boundary between two block sizes. An attacker can do a CRIME-style attack that includes a wrong password guess plus some of their own padding, and vary the amount of padding until it is just big enough to take n + 1 blocks instead of n . The…

You still want to compress in the first place as a means of removing entropy and some known plain text if possible. Most systems that give you the option of compressing or not do so because you may have already used some other method of compressing the data (E.G. it's a video file or already a compressed transport archive). The addition of padding, even worthless (hopefully at least pseudo-random) garbage, up to some…

I've heard this advice before a few times, but I've never seen a rigorous analysis of what "removing entropy" is supposed to mean. Any half-reasonable encryption system will deal just fine with low-entropy inputs, and produce an equally rigorous output. (ECB mode is not a half-reasonable encryption system, but even, say, 1DES-CTR satisfies this requirement.)

Compressing inputs that are completely not controlled by an attacker is fine. For instance, gzipping static files on your CDN is totally fine.

Padding to a minimum message size does not make message size useless. It only makes message sizes below the threshold useless. If an attacker can control part of the input (which is the threat model for things like CRIME, where an attacker-controlled URL and a non-attacker-controlled cookie header are part of the same HTTP request), they can just provide their own padding to get the input past the minimum size. Setting a fixed and unchangeable size for messages works (... provided there's nothing secret in the number of messages!).

Re: “Should you encrypt or compress first?”

#229

Post by angry_octet »

hinkley wrote: post #225
DougBTX wrote: post #172

Earlier quoted context omitted.

Yes, in other words compression can move information from the content of the data (which is encrypted) to the size of the data (which is not encrypted).

Which is one of the selling points of block cyphers. They may not conceal the magnitude of the payload but they do obscure the exact byte count by rounding up. But that probably doesn't stop CRIME from being workable.

Hmm, I don't think it is really a selling point. A block cipher also implies needing a technique like CBC to prevent watermarking, and using CBC actually helps with oracle attacks.

An interesting paper on using padding to obscure length: http://cihangir.forgottenlance.com/papers/lengthhiding-corre...

Re: “Should you encrypt or compress first?”

#230

Post by angry_octet »

LeoPanthera wrote: post #196
choosername wrote: post #192

Earlier quoted context omitted.

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.

Ah, but they can repeat! There is a finite chance that any sequence of any length will occur in a random sequence.

So while a compression alg applied to a very large amount of random data is unlikely to reduce the size, it is quite possible to achieve some compression on smaller blocks.

Post reply on HN