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

Re: “Should you encrypt or compress first?”

#241

Post by analogj » Wed, Jun 29, 2016, 6:41 AM UTC

angry_octet wrote: post #230

LeoPanthera wrote: post #196

Earlier quoted context omitted.

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.

You should take a look at the almost 15 year old (and unsolved) "Random Compression Challenge"

http://marknelson.us/2012/10/09/the-random-compression-chall...

Re: “Should you encrypt or compress first?”

#242

Post by phlo » Wed, Jun 29, 2016, 7:26 AM UTC

dllthomas wrote: post #130

lmm wrote: post #61

Earlier quoted context omitted.

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).

CRIME works because the compression/encryption algorithms aren't aware of which data is secret and which isn't. They treat the whole HTTP stream as a stream of text and operate on that. To them, text within the page is just the same as cookie data in the corresponding header field or (for example) the URI in the header.

If such a distinction were possible, the system could just not compress secret data. But if that were the case, nonsecret data wouldn't even need to be encrypted; it's nonsecret after all.

Re: “Should you encrypt or compress first?”

#243

Post by hinkley » Wed, Jun 29, 2016, 2:41 PM UTC

angry_octet wrote: post #229

hinkley wrote: post #225

Earlier quoted context omitted.

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

Oh, I'm a fan of prepadding, and there are other surveillance problems that TLS doesn't solve that are similar to the voice analysis attack. Web pages on a site have distinct patterns of load operations and I'm certain that if we haven't established how to profile a visitor by the pattern of packets that are sent and received, that it's only a matter of time until we do.

Re: “Should you encrypt or compress first?”

#244

Post by zeveb » Wed, Jun 29, 2016, 2:59 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.

I don't have a handy place to stash 5MB of data publicly, but you can run the following in SBCL (or the equivalent in whatever language you prefer):

    (in-package :cl-user)
    (use-package :ironclad)
    (let ((data (make-array (* 5 1024 1024)
                            :element-type '(unsigned-byte 8)
                            :initial-element (char-code #\X))))
      (encrypt-in-place
       (make-cipher
        :aes
        :key (sb-ext:string-to-octets "YELLOW SUBMARINE")
        :mode :ctr
        :initialization-vector (make-array 16 :element-type '(unsigned-byte 8)))
       data)
      (with-open-file (tmp "/tmp/data" :direction :output
                           :element-type '(unsigned-byte 8))
        (write-sequence data tmp)))

That's a file of 5,242,880 'X' characters, encrypted with the key 'YELLOW SUBMARINE' and an all-zero initialization vector. You will not be able to compress it.

Re: “Should you encrypt or compress first?”

#245

Post by tuatara » Wed, Jun 29, 2016, 8:54 PM UTC

mcguire wrote: post #86

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.

Once upon a time I was at a talk given by a visiting professor (associated, I think, with the Horus project[1]; I'm reasonably sure some of you would recognize the name if I could remember it ) on designing network protocols using plug-n-play software components. The illustrations he showed used Lego bricks. His big example was a Lego brick labelled "Compression" and another brick labelled "Encryption", and how you c…

Perhaps you're referring to Prof. Ken Birman, inventor of Paxos and slayer of CAP? I could barely contain myself at his recent MesosCon keynote[1,2].

[1] https://mesosconna2016.sched.org/event/6ljt/keynote-a-real-t... [2] http://go.linuxfoundation.org/mesoscon-north-america-2016-vi...

Re: “Should you encrypt or compress first?”

#246

Post by qu4z-2 » Wed, Jun 29, 2016, 9:58 PM UTC

qu4z-2 wrote: post #210

jahewson wrote: post #191

Earlier quoted context omitted.

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

If patterns appear in random data, and no patterns appear in encrypted data, then it's trivially distinguishable from random data: look for patterns.

To be clear, I'm not claiming that encrypted data is compressible. I'm just pointing out that any detectable "patterns" that appear in random data but not encrypted data are inconsistent with the claim that random and encrypted data are indistinguishable. Also if you find such a "pattern" that's probably a good starting point for breaking whatever cipher you're using.

Re: “Should you encrypt or compress first?”

#247

Post by labianchin » Thu, Jun 30, 2016, 1:49 PM UTC

lisper wrote: post #39

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.

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

Interesting. Keepass[0] (password store) compress with GZip by default before encryption.

[0] http://keepass.info/help/v2/dbsettings.html#compression

Re: “Should you encrypt or compress first?”

#248

Post by rpearl » Thu, Jun 30, 2016, 7:09 PM UTC

arjie wrote: post #231

rpearl wrote: post #165

Earlier quoted context omitted.

If you're encrypting it, it is to hide information from some sort of attacker, not the trusted recipient of the document. If there is literally no possibility at all of someone else intercepting the document, then why are you bothering to encrypt in the first place?

Because the wire is unsafe.

In which case the considerations in the featured article apply entirely to any attacker with access to the wire/transit.

Your original comment makes no sense.

Re: “Should you encrypt or compress first?”

#249

Post by arjie » Fri, Jul 01, 2016, 3:11 PM UTC

rpearl wrote: post #248

arjie wrote: post #231

Earlier quoted context omitted.

Because the wire is unsafe.

In which case the considerations in the featured article apply entirely to any attacker with access to the wire/transit. Your original comment makes no sense.

No. The considerations in the article apply to certain kinds of input under certain conditions. Those caveats mean it doesn't apply to self-generated text documents encrypted all at once, in general.