Therefore, I feel like compression complicates the discussion unnecessarily. Information that's not encrypted (the time a key was typed or the spacing between phonemes in a word) can be recovered by an attacker without breaking the encryption. Obvious when you say it like that ;)
An interesting paper on using padding to obscure length: http://cihangir.forgottenlance.com/papers/lengthhiding-corre...
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.
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".
Freudian slip? I like it anyway.
Encrypted content should be indistinguishable from random data. So encrypt than compress shouldn't be able to yield any reasonable compression.
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.
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.
http://marknelson.us/2012/10/09/the-random-compression-chall...
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.
For a reasonable definition of incompressible, properly encrypted data is it.
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.
If you compress a document that simply obscures the size of the original document.
That is not generally true - if you compress AAA and ABC then the compressed version also leaks information about the content exactly like in the case of an audio stream and it reveals more information then the lengths of the uncompressed documents which don't differ.
Feed that information into a prebuilt phoneme-in-context model trained on that codec and language, and said eavesdropper could probably reconstruct a pretty good estimated transcript - different phonemes compress differently.
There is no reason this would not work in bulk: I am under the impression GCHQ have done a fair amount of research in this area, for example.
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?
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).
I would guess that the phones and voip is a perfect target to do this, as those system are often designed to filter out noise. I guess it also would be almost impossible to use this to transcribe a encrypted movie or music, as the unpredictable sounds would break the prediction model.
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.
I think this is only true if you use a bad encryption algorithm where same plaintext blocks have the same ciphertext.
Stream ciphers.
Other famous AEAD schemes are:
- CCM (Counter with CBC-MAC), packages AES-CTR and CBC-MAC together in an authenticate-then-encrypt regime
- ChaCha20-Poly1305, which packages together the stream cipher ChaCha20 and the MAC Poly1305.
Not that this really matters. The advantages/disadvantages of compression are the same in both cases.
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.