4 ms·
If your input is "perfectly" random then the codebreaker has no chance of determining when he/she has successfully decrypted it (regardless of how weak your enc
by Tloewald 13y ago
If your input is "perfectly" random then the codebreaker has no chance of determining when he/she has successfully decrypted it (regardless of how weak your encryption is). So the more random your unencrypted data, the harder it is to decrypt it once it is encrypted. It follows that less random data will be easier to decrypt. Now I can't prove the shape of the intermediate function (e.g. might there be a sweet spot in the middle? "Common sense" suggests the relationship would be monotonic, but common sense is often wrong).
Incidentally, it's also clear that if the encryption schema is large relative to the compressed data then it will also be harder to decrypt (of course if the encryption schema is public, e.g. a public key, then this is decidedly not true).
So, none of this should be terribly surprising. What it does suggest is that you should compress data before (or while) encrypting it, and the better your compression algorithm, the more entropy there will be in your data, and the more secure your encryption.
- CWuestefeld 13y agoAh, but if you compress it into, say, a ZIP file, then an attacker would be able to look for the characteristics that are typical of a ZIP file. The opening bytes, for example, are completely predictable. This would be just like the Nazi mistake of always ending messages in "Heil Hitler".
- eru 13y agoJust cut out the common parts.
- parfe 13y ago>This would be just like the Nazi mistake of always ending messages in "Heil Hitler". Got any source for that? Closest I can find is a Polish cryptologist facetiously adding "Heil Hitler!" to ENIGMA encrypted messages he sent to Britain. https://en.wikipedia.org/wiki/Marian_Rejewski https://en.wikipedia.org/wiki/Marian_Rejewski
- Tloewald 13y agoI believe the actual issue was that messages started with very predictable greetings. "we relied on the fact that the greater number of messages began with the letters ANX—German for "to", followed by X as a spacer" http://en.wikipedia.org/wiki/Cryptanalysis_of_the_Enigma http://en.wikipedia.org/wiki/Cryptanalysis_of_the_Enigma Compressed files (indeed ANY files) having predictable headers is, of course, a major problem, and the argument that you could just omit the common stuff won't work very well either. (Let's suppose you leave off all the static parts until you get to a length stamp -- lengths are a classic example of not-very-random numbers (more significant digits are prone to be lower-valued). In general, you want your cryptographic system to be reasonably foolproof when used by bored, careless people. For this reason rolling compression and encryption into a single implementation is probably the best option.
- nialo 13y agoThis is the obvious intuitive response, but it turns out that it's broken: Compressing data before encryption can give attackers a new side channel to recover the plaintext, by just watching the message length, and seeing when the compression is more or less effective. See, for example, the CRIME attack on TLS.
- p0ckets 13y agoObvious next step: compress and pad to original length.
- rmidthun 13y agoObvious? Didn't that word already cause enough trouble? What are you going to pad it with? Random values? In that case, I'll just make two requests for the same information and clip it where they differ. Some sort of value based on the message? That also has issues, see link below. So far it doesn't seem like there are any obvious crypto ideas that are not also wrong. http://en.wikipedia.org/wiki/Padding_oracle_attack http://en.wikipedia.org/wiki/Padding_oracle_attack
- nknighthb 13y ago> I'll just make two requests for the same information and clip it where they differ. So, byte 0? You're not really using ECB, are you?
- rmidthun 13y agoD'oh. Good point. At least I can point to it as another example of someone not expert in the field making a stupid statement about crypto... I think the general problem of padding with random values resulting in non-determinism would still matter in some cases, but IANAC.
- Tloewald 13y agoSeems to me that the inherent problem here was that you could get the sender to send messages of your choosing, which is always going to be a vulnerability. Consider that this entire line of discussion is redundant if (a) the encryption key is public (as stated above) or (b) you know what the plaintext looks like for some encrypted examples.