Proof of probability of weak keys in block cipher My textbook has the following theorem:


  Given a block cipher with a key length of K bits and blocksize of n bits as well as t plaintext-ciphertext pairs, the expected number of false keys which encrypt all plaintexts to the corresponding cipher text is $$2^{k - tn}$$


This makes sense if you consider DES gives us roughly $2^{-8}$ for a single plaintext-ciphertext pair as explained here. However the author doesn't give a proof to this theorem, I want to know if it's possible to prove it and how can I prove it? I thought about using induction but I'm having some problems about which assumptions I can make
However the author doesn't give a proof to this theorem, I want to know if it's possible to prove it and how can I prove it?


The author likely doesn't bother with the proof because it is so straight-forward; we also need to note that the figure $2^{k-tn}$ is not exact, but merely an approximation (albeit a very close one for realistic key and block sizes); once we skip the approximation, the proof becomes slightly less trivial.

First, the assumption we make: that the cipher acts like an ideal cipher, in particular, if we give an incorrect key to the cipher, that it generates random ciphertext blocks (and ones that are independent of the ones generated with the correct key).

Then, if we consider giving the known $t$ plaintexts to the cipher with an incorrect key, it will generate $t$ random ciphertexts, each of which is $n$ bits.  Given that these are random, the probability that all $n$ of them are precisely the same bits as the expected ciphertext bits is $2^{-nt}$ (as there are a total of $nt$ bits, all of which need to be precisely the correct value.

Now, this isn't quite accurate.  The block cipher, even given an incorrect key, is still a permutation, and assuming that all the plaintext blocks are distinct, all the generated ciphertext blocks will be distinct.  This means that, if $t&gt;1$, that certain outputs (such as the all-0 output) will be impossible (because the cipher will never encrypt two different plaintexts into the same all-0 ciphertext block); the precise probability for an incorrect key is $(2^n-t)! / 2^n! = \frac{1}{2^n \cdot (2^n-1) \cdot (2^n-2) \cdot … \cdot (2^n-t+1)}$.  If $2^{n/2} \ggg t$, that is, we're considerably under the "birthday bound", this is quite close to $2^{-nt}$

Now, this is the expected value for one incorrect key, and the total expected value is the sum of the expected values for all the various disjoint possibilities.  There are a total of $2^k$ incorrect keys, and so the total expected value is $2^k \cdot 2^{-nt} = 2^{k - nt}$

Now, this also isn't quite accurate, there are $2^k-1$ incorrect keys (as we assumed that there was a correct key); obviously, for the key sizes we use, $2^k$ is quite a good approximation; we've also seen that $(2^k-1)(2^n-t)! / 2^n!$ is the precise (if generally less useful) expectation.