Schneier on Security

solinym • November 27, 2006 12:06 AM

His site appears hacked, but not maliciously so.

@Clive Robinson:
“Then you have to ask yourself a question, is it possible to put an incompressable Ptext into a cipher function and obtain a Ctext output with compressable redundancy?

The answer is yes, think back to the feedback system above using an IV of all zeros what happens if you carry on encrypting all zeros?”

BTW, in this case he means p_n=0 for all n. At first I couldn’t tell if he meant this or if he meant that the plaintext was chosen so that the input to the block cipher was 0 each time, but that makes even less sense when you work it out, since the output is always a constant, so the ciphertext is either a repeated (constant) block or 0.

“You should (asuming it’s working properly) get an output where the encryption function steps through every possible output in some apparently random order (actually dependent on the key). As there are no repeats of the output blocks there is no redundancy at the block size so it is uncompressable at that level.”

c_1 = e(IV), c_n = e(c_(n-1))

In any mode that uses feedback (CBC, CFB, OFB). Is that really guaranteed to step through every value? If so, it must rely on some property of the block cipher that I’m not thinking of. It seems to me that it could just as easily slip into a short cycle; if e(IV) = x and e(x) = IV, those two blocks repeat over and over. What you’re describing sounds a lot like CTR mode, which doesn’t use feedback at all. What makes you think iterating the block cipher forms a permutation?

“Then as the encryption function is invertable (ie you can decrypt it) you can simply put the non compressed output back into the encryption block and get an output without information (ie compleatly redundant).”

What’s an “encryption block”? The block cipher? I’m lost.

In any case, redundancy doesn’t go away when you encrypt; it just gets obscured. I assume that’s what he is trying to say. If my stream is the concatenation of the Bible encrypted with a counter as the key, you may have difficulty detecting that it is redundant, unless you happen to try decrypting it with a counter.

And compression algorithms test for one kind of redundancy. In the case of n-byte sliding window algorithms, you just make a repeating sequence with length n+1 bytes and no internal repetition, and the compression function won’t find it. Similar redundant inputs can be constructed for each individual compression algorithm. So by all means use them to check your sanity, but don’t expect them to find every kind of redundancy, and don’t expect them to only yield smaller outputs; that is impossible, by the pigeon-hole principle. What makes them useful is that they detect a certain kind of randomness that’s present in the data sets you are concerned with.

Also, most compression routines create PREDICTABLE bits and LARGER outputs up to some break-even point. For example, in Huffman coding, the “enter a new symbol” bit is predictable on the first byte (if not assumed) and unless the second input byte is the same as the first, is predictable again (if plaintexts are randomly generated, this happens 255/256ths of the time).

Testing for redundancy is like testing for predictable patterns in the output of a HWRNG; the statement “there are no predictable patterns in this output” is a universal statement (negation of an existential quantifier) and so cannot be said rigorously due to testing without testing for every possible prediction algorithm. Usually, the negation of a statement is a universal (because hypotheses tend to be existential), so when people say “you can’t prove a negative”, they really mean “you can’t prove a universal with individual (non-)existence evidence”.

Actually, I can prove negatives; I can prove the negation of “all elephants are dead” by finding a live one. If I say “measurable gravity exists everywhere”, that’s not a negative, but good luck trying to prove it with a gravimeter and a space ship.

Proof by contradiction is often the only hope for proving universals over infinite sets.

What does this all mean for crypto? It means that the claim “there is no shortcut for computing the inverse of this cipher that is more efficient than brute force” is not going to get proven. It means that you can’t test for unpredictability in a RNG. It means that you can’t test for uncompressability. That’s what keeps it interesting…. 😉