231–240 of 249 posts
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?
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.
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.
Consider using basic modular addition of letters, with A=1, B=2 ... Z = 26. If your plaintext is HELLO, and you get AAAAA as ciphertext, then your key has to be SVOOL. If you look, that's just an inversion of each letter. H is the 8th letter of the alphabet, whereas S is the 8th from the end, etc. So, your one-time pad was incidentally a simple translation of your message.
I'm not sure if there's any interesting information being leaked this way. Perhaps by seeing that the encrypted message can be heavily compressed, or knowing that it has been heavily compressed, you can assume that the encryption key has some very improbable patterns, and use that to bound guesses about the encryption key.
Not an expert. Not even an intermediate.
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.
Earlier quoted context omitted.
This is exactly what the article says.
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.
Indeed, I think the conventional wisdom was that compressing first would in fact improve security a little bit. This idea goes back all the way to Shannon in 1949, who noted that compressing before encrypting should improve information-theoretic security, because if the messages contain redundancy, then an adversary with infinite computing power can use that to decode the message. (Just try all possible keys, and see if it decrypts to an actual English sentence.) On the other hand, if you first compress using an ideal compressor, then every compressed plaintext will look the same (just random noise), so every possible encryption key will produce some plausible plaintext.
[1] http://netlab.cs.ucla.edu/wiki/files/shannon1949.pdf ; see sections 16 - 19.
In fact, if you successfully compress data after encryption, then the only logical conclusion is that you've found a flaw in the encryption algorithm.
Earlier quoted context omitted.
Good catch! Although the article talks about encrypt+sign versus sign+encrypt, the same argument goes for compress+sign versus sign+compress.
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?)
Regardless of whether you're encrypting or compressing or signing twice or what order those are in.
I think it is best to use built-in compression scheme by the compression program to do the encryption first, as those often take these into account (and the header is not leaked, since only the content is encrypted).
Earlier quoted context omitted.
I think compression is a read herring here. Think about keyboard-interactive ssh authentication. Whether or not the data is compressed, the timing of the packets depends on the timing between when you pressed the keys on your keyboard. Thus information is leaked, and compression was not involved. Therefore, I feel like compression complicates the discussion unnecessarily. Information that's not encrypted (the time a…
Well, yeah, but the point is that compression can cause the leakage of information through timing that would not otherwise have leaked.
As for compress. My understanding is that the inscurity has nothing much to do with timing, and everything to do with giving an attacker some "known" plaintext they can use Bayesian (Turing?) analysis against to shorten the key space.
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.
well. My first comment would be. If your encryption algorithm produces output that can be compressed. Your encryption algorithm is broken. As for compress. My understanding is that the inscurity has nothing much to do with timing, and everything to do with giving an attacker some "known" plaintext they can use Bayesian (Turing?) analysis against to shorten the key space.
Earlier quoted context omitted.
well. My first comment would be. If your encryption algorithm produces output that can be compressed. Your encryption algorithm is broken. As for compress. My understanding is that the inscurity has nothing much to do with timing, and everything to do with giving an attacker some "known" plaintext they can use Bayesian (Turing?) analysis against to shorten the key space.
No, read the dang article. You leak information about the content of the plaintext because you're changing the length. The crib doesn't matter with secure constructions.
Problem with compress is the protocol headers give you a known part at the start of every message. Which you can then very quickly test keys against rainbow tables or other statistical means.
The best solution i know for this is to compress, then xor with a stream cipher then run into a decent block cipher.
The "compress after encrypt" is a trick question. If your data doesnt get bigger after that your encryption implementation is royally broken.
But you definately don't want every "plaintext" message starting with "..gzip".