News for hackers. Stuff that matters.
Re:“Should you encrypt or compress first?” by admax88q on Tuesday June 28, 2016 @03:30PM (#11996777)
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.

Re:“Should you encrypt or compress first?” by choosername on Tuesday June 28, 2016 @04:15PM (#11997149)
wit truly random data, patterns should randomly appear.
Re:“Should you encrypt or compress first?” by zzazzdsa on Tuesday June 28, 2016 @04:34PM (#11997325)
There's a pretty easy proof to show why compression of truly random data is impossible. Let C be a compression algorithm. Assume that for all bit strings S, C(S) is not longer than S, and assume that there exists strings S' such that C(S') is shorter than S'. Also, assume that for any two distinct bit strings S1 and S2, C(S1) != C(S2). Let S'' be the shortest such string: the shortest string that C shortens. Let the length of S'' be M, and the length of C(S'') be N < M. Note N >= 1, and by assumption every string of length N does not have its length changed by C. There are 2^N strings of length N, and by assumption it is easy to see that since the images of any pair of N bit strings under C are distinct, every string of N bits is the image of some other N bit string. But now, S'' has length M but has an image of length N. This necessarily collides with the image of some string of length N, a contradiction. Thus, for any compression algorithm which is injective (in effect, reversible) and successfully shortens some strings, the algorithm must lengthen some others.

What this short proof shows is that even though random data may have patterns, no compression algorithm can successfully leverage this for every random string.

Re:“Should you encrypt or compress first?” by jahewson on Tuesday June 28, 2016 @04:29PM (#11997284)
Encrypted data is "indistinguishable from random data" but it is not actually random data. No patterns will appear.
Re:“Should you encrypt or compress first?” by qu4z-2 on Tuesday June 28, 2016 @07:02PM (#11998275)
If patterns appear in random data, and no patterns appear in encrypted data, then it's trivially distinguishable from random data: look for patterns.
Re:“Should you encrypt or compress first?” by qu4z-2 on Wednesday June 29, 2016 @05:58PM (#12005139)
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?” by gameofdrones on Tuesday June 28, 2016 @04:24PM (#11997230)
Re:“Should you encrypt or compress first?” by choosername on Tuesday June 28, 2016 @04:32PM (#11997308)
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
Re:“Should you encrypt or compress first?” by LeoPanthera on Tuesday June 28, 2016 @04:42PM (#11997394)
tl;dr Random data may appear to have patterns, but those patterns do not repeat, so they cannot be compressed.
Re:“Should you encrypt or compress first?” by angry_octet on Tuesday June 28, 2016 @10:00PM (#11999033)
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.

Re:“Should you encrypt or compress first?” by taneq on Tuesday June 28, 2016 @11:17PM (#11999279)
Any given _example_ of a random sequence may have less than maximum entropy, and so may be compressible, but a truly random sequence _in general_ will not be compressible. So you can make a compression algorithm that will compress random data in some cases but it will never be able to compress any arbitrary random data. Does this help?
Re:“Should you encrypt or compress first?” by analogj on Wednesday June 29, 2016 @02:41AM (#11999907)
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?” by gameofdrones on Tuesday June 28, 2016 @05:21PM (#11997683)
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.
Re:“Should you encrypt or compress first?” by Retra on Tuesday June 28, 2016 @07:59PM (#11998537)
Saying something true but burying it is not wise either.
Re:“Should you encrypt or compress first?” by scj on Tuesday June 28, 2016 @06:21PM (#11998056)
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.

Re:“Should you encrypt or compress first?” by pshc on Tuesday June 28, 2016 @06:33PM (#11998108)
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.

Re:“Should you encrypt or compress first?” by bryondowd on Tuesday June 28, 2016 @10:53PM (#11999205)
My intuition says that if your ciphertext after using a one-time pad is trivially compressible, it means there's a strong correlation between your plaintext and your key. It's an interesting thought.

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.