1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ BTW: the generally accepted meaning of 'weak key' isn't 'one that happens to decrypt this specific ciphertext into the correct plaintext', instead, it is a key with special properties; such as 'one of a set of keys for which we can detect (or decrypt) with much less than expected effort' or 'one with some surprising property' (such as the DES weak keys, which are self-decrypting keys, that is $Enc_k(Enc_k(X)) = X$ if $k$ is a DES weak key. $\endgroup$
    – poncho
    May 16, 2020 at 15:20

1 Answer 1

3
$\begingroup$

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>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.

$\endgroup$
2
  • 1
    $\begingroup$ @kelalaka: $t$ is the number of known plaintext-ciphertext blocks, and so the total number of bits of ciphertext we have is $nt$. I do see I swapped the meanings of $n, t$ around in my answer; fixed it $\endgroup$
    – poncho
    May 16, 2020 at 13:31
  • 1
    $\begingroup$ Now, Ok. I was like in a hell! $\endgroup$
    – kelalaka
    May 16, 2020 at 13:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.