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

211–220 of 249 posts

Re: “Should you encrypt or compress first?”

#211

Post by dcposch »

VLM wrote: post #97
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…

No, he's saying you compress CBR, then encrypt. Not compress CBR -> gzip -> encrypt or something silly like that.

CBR audio codec, then encrypt gives you a constant-bitrate stream indistinguishable from randomness. That's pretty much the gold standard.

(Of course, that still only encrypts content, not metadata. You can encrypt a phone call in such a way that a watcher gets mathematically zero information about what's being said, but the watcher still sees who is calling whom, when, and for how long. Hiding that is much harder.)

Re: “Should you encrypt or compress first?”

#212

Post by cvwright »

Qantourisc wrote: post #201

Maybe we need encryption that also plays with the length of the message / or randomly pad our date before encryption ? I am however no expert, so I have no clue how feasible, or full of holes this method would be .

Yes, this is one option that we proposed back in 2009 after we first pointed out the VoIP traffic analysis attacks in 07 and 08.

If you want more information, see our paper on traffic morphing from NDSS 2009 [1]. It works pretty well for VoIP; not as great for trying to counter similar attacks on web browsing traffic.

[1] http://www.internetsociety.org/doc/traffic-morphing-efficien...

Re: “Should you encrypt or compress first?”

#213

Post by cvwright »

jakozaur wrote: post #38

Would adding some tiny random size help? Based on my poorly understanding, if after compress, but before encrypt we add random 0 to 16 bytes or 1% of size that could defeat quite a lot of attacks (like CRIME).

It's really going to depend on what kind of data you're dealing with.

For VoIP, if you're smart you can even fool the attacker into guessing a wrong answer of your choosing. See my comment upthread for a link to our NDSS 2009 paper on traffic morphing.

I'm not familiar enough with the CRIME attack to say how well such a defense might work. Maybe someone who knows more can chime in.

Re: “Should you encrypt or compress first?”

#214

Post by gajjanag »

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…

> That reduces, but doesn't eliminate, the amount of information you're leaking.

All cryptographic systems save the one time pad do leak some information, in the sense that they are not information theoretically secure. For instance we know that the output of standard block or stream ciphers (with fixed plaintext) is distributed over an exponentially small fraction of the possible output space.

So really the question here is whether one can pad to the point where it is computationally infeasible to launch this kind of attack, and whether this padding amount is so large as to defeat the compression entirely.

For example, two normal distributions with variance 1, means ~ 2^(-k) away from each other to each other can require ~ 2^(2k) trials for a constant probability of hypothesis test success (say 1/3).

Has there been any work analyzing this rigorously, taking the length leakage as side information available to the attacker?

Re: “Should you encrypt or compress first?”

#215

Post by cvwright »

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.

Fair enough. The larger point, however, is that this stuff was supposed to be encrypted. The adversary shouldn't be able to learn even one bit about the plaintext.

After all, nobody would buy a new encryption module that advertised it could protect you 40% of the time.

Re: “Should you encrypt or compress first?”

#216

Post by cvwright »

zielmicha wrote: post #177
panic wrote: post #37

Has there been any research into compression that's generally safe to use before encryption? E.g., matching only common substrings longer than the key length would (I think?) defeat CRIME at the cost of compression ratio.

I'm working (finishing paper) on an algorithm compatible with deflate/gzip that is safe to use before encryption (i.e. it is guaranteed to not leak random secrets cookies). It's a bit more complex than your suggestion - matching common substrings longer than key length would still be vulnerable as substring boundary may still fall inside secret.

Cool! Please post a Show HN with a link to your ePrint when it's done.

Re: “Should you encrypt or compress first?”

#217

Post by qu4z-2 »

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'

Any one given input can be losslessly compressed down to 1 bit with the exact right compression algorithm. I think everyone here understands that. The argument is just that that's not really useful in the real world.

Re: “Should you encrypt or compress first?”

#219

Post by crpatino »

IncRnd wrote: post #149
smaddox wrote: post #142

Earlier quoted context omitted.

Could this threat be neutralized by salting before compressing?

No. Salting is to keep stop pre-image attacks in encryption. It doesn’t affect compression.

And bottles are used for holding liquids rather than smashing heads... until you find yourself in a bar fight.

I might be wrong, but I think the parent had something like this in mind:

Assuming you are encrypting with AES-CFB your each plaintext block P[i] produces a ciphertext block C[i] (with key K and initialization vector IV) according to rule:

    C[0] = AES_encrypt(K, IV) ^ P[0], 
    C[i] = AES_encrypt(K, C[i-1]) ^ P[i].
Given that IV is assumed to be known by the attacker, if the plaintext is a vanilla-compressed stream, it is more likely than not that most of bits in P[0] are going to be known as well, which might allow some sort of prunned brute-force attack on key K, given a small set of (C[0] ^ P'[0]), for all P'[0] that satisfy the known bits in P[0].

This particular implementation would benefit then from adding a pseudorandom P[0] block (a "salt", if I understood correctly) that the receiver is to discard on arrival. I don't know enough cryptanalysis to tell if the above scenario is valid or not, but it sounds like a legitimate question at least.

Re: “Should you encrypt or compress first?”

#220

Post by Retra »

gameofdrones wrote: post #198
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

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.

Saying something true but burying it is not wise either.
Post reply on HN