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

Re: “Should you encrypt or compress first?”

#161

Post by Dylan16807 » Tue, Jun 28, 2016, 6:51 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'

> People are literally saying that a encrypted output can NEVER be compressed.

No they're not. They're saying that as a class, you cannot compress the data. That is a statement about what happens in aggregate. And the aggregate result of trying to compress securely-encrypted data is that you don't save bytes. Even just having the option of compression does not save bytes, because you have to store the choice.

Re: “Should you encrypt or compress first?”

#162

Post by s_tec » Tue, Jun 28, 2016, 6:51 PM UTC

lisper wrote: post #71

witty_username wrote: post #64

Earlier quoted context omitted.

@lisper Stream ciphers.

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

The AES-GCM mode of operation turns the AES block cipher into a stream cipher. Doing this makes it possible to add authentication on top for relatively cheap. The ChaCha20-poly1305 has a similar construction. These are the two most secure and efficient ciphers available in TLS, so they get a lot of use. If you are sending documents over HTTPS, you definitely want them encrypted with one of these two.

Re: “Should you encrypt or compress first?”

#163

Post by Normal_gaussian » Tue, Jun 28, 2016, 6:53 PM UTC

mikeash wrote: post #153

olliej wrote: post #144

Earlier quoted context omitted.

Success: compress.sh: #!/bin/bash echo "#!/bin/bash" echo curl $1 ./compress.sh https://mikeash.com/tmp/randomfile.bin > randomfile.compressedzomg :D /me hides

You're lucky I'm too lazy to edit a byte on the server and then ask you if it still matches.

It would. You would need to change the location of the file

Re: “Should you encrypt or compress first?”

#164

Post by kbenson » Tue, Jun 28, 2016, 6:59 PM UTC

danbruc wrote: post #133

kbenson wrote: post #110

Earlier quoted context omitted.

So, it's not just compression per se, but compression plus real-time plus some knowledge about the underlying information. These sorts of attacks don't matter against a compressed and then encrypted file of indeterminate data, correct? Similarly, an amalgamation of many types of data, such as a disk or archive?

If you know absolutely nothing about the uncompressed original, then it seems indeed pretty hard to infer anything from the compressed version. But as soon as you know something, for example the rough size of the uncompressed original, you can for example start to infer that the content is either more like AAA or more like ABC because repetitions will compress better. And in reality it is really unlikely that an atta…

Sure, but isn't there more implied by what you just said? It's not just that you know the size, but if you know the header format, then you also know the type (which you might). But, I'm not sure how much more of less information compression provides for non-trivial size files. Where individual packets are encrypted, you have quite a bit of information. Where you have one file of non trivial size, there is much less information exposed.

For example, you know its type, and it's 150KB. Even if you know it's a text document, or a WAV file, or bitmap, I think you get far less information from the compressed version than from the non-compressed version. The non-compressed version of the text document may give you approximate word count, and the WAV file will give you some probable lengths of the recording at common sampling rates, and the bitmap will give you some probable dimensions. Compressed versions hide this information within the natural variance of the compression.

The problem seems less to do with compression, and more to do with splitting larger data (or streams of data) into smaller chunks to encrypt, which in itself loses some of the benefits of hiding information in the variance of the data presented. Compression seems to exacerbate this situation by amplifying variances in very small data sets in a way that yields additional information, but it seems to me that's just a natural progression of encrypting very small amounts of data being not nearly as effective as large amounts of data.

At least, that's what I can intuit about the situation. It may be partly (or totally) wrong given some more advanced security theory (I am not a security professional).

Re: “Should you encrypt or compress first?”

#165

Post by rpearl » Tue, Jun 28, 2016, 7:00 PM UTC

arjie wrote: post #128

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

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?

Re: “Should you encrypt or compress first?”

#166

Post by mikeash » Tue, Jun 28, 2016, 7:03 PM UTC

Normal_gaussian wrote: post #163

mikeash wrote: post #153

Earlier quoted context omitted.

You're lucky I'm too lazy to edit a byte on the server and then ask you if it still matches.

It would. You would need to change the location of the file

Fine, fine, you're^Wthey're lucky I'm too lazy to make it return new random data each time.

Re: “Should you encrypt or compress first?”

#167

Post by [deleted] » Tue, Jun 28, 2016, 7:06 PM UTC

[deleted]

Re: “Should you encrypt or compress first?”

#168

Post by cm2187 » Tue, Jun 28, 2016, 7:06 PM UTC

Can't you just add some random length data at the end. You are defeating compression a little bit, but are also making the length non deterministic. I thought pgp did that.

Re: “Should you encrypt or compress first?”

#169

Post by b101010 » Tue, Jun 28, 2016, 7:07 PM UTC

mikeash wrote: post #78

b101010 wrote: post #63

Earlier quoted context omitted.

Why is the debate about "compress/encrypt then sign" vs "sign then compress/encrypt"? Is there a non obvious problem with sign then compress/encrypt then sign again? (overcomplicated or unnecessary?)

It's pointless. If you sign the encrypted data, then once the signature is verified in the receiver, you know that the decrypted data is also good. Repeating the signature just wastes time and space.

After some thought, The only advantage of signing before and after i can think of is without it you are left with the (theoretical?) problem of not knowing if the output from your implementation/version of the utility to decrypt/decompress is identical to the senders input to their implementation of the utility if the sender only signs the compressed/encrypted version.

Of course, if the compression/encryption method has some way of checking the integrity of the output (that's of equal strength to the signature) then then signing first would be completely redundant.

EDIT: so in many scenarios, signing first and last would have no advantage. For example if you get to decide what implementation will be used by the sender and the recipient (most package managers?)

Re: “Should you encrypt or compress first?”

#170

Post by nearbuy » Tue, Jun 28, 2016, 7:08 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'

In practice, with any real, widely used compression algorithm, encrypted output will never be compressed. You can generate 100,000 random binary files and run them through all the major compression tools and not one of them will compress by even a single bit.

In theory, some random outputs will be compressible by common tools (for example, a file that's all zeroes). However, the probability of encountering a random file that compresses more than the overhead from any common compression tool is vanishingly small.