I'm doing a self study through Understanding Cryptography by Christof Paar and I have a question about Theorem 5.2.1 in the book:

Given a block cipher with a key length of $k$ bits and block size of $n$ bits as well as $t$ plaintext-ciphertext pairs $(x_1, y_1)\cdots(x_t,y_t)$, the expected number of false keys which encrypt all plaintexts to the corresponding ciphertexts is $2^{k-tn}$.

My understanding of the "proof" is that you treat the brute force attack process as picking $2^k$ permutations independently and uniformly at random. The probability that a random permutation encodes $x_1 \rightarrow y_1$ is $1/2^n$ as there are $2^n$ choices for the ciphertext and each are equally likely. So the expected number times that we encounter $x_1\rightarrow y_1$ is $2^k/2^n$. Now, the probability of a random permutation mapping both $(x_1,y_1)$ and $(x_2,y_2)$ is $\frac{1}{2^n}\frac{1}{2^n-1} > 2^{-2n}$ so for $t$ pairs, it's $\frac{1}{2^n}\frac{1}{2^n-1}\cdots\frac{1}{2^n-(t-1)}>2^{-tn}$ so the expected number of false keys should be $>2^{k-tn}$. I.e., this is a lower bound on the expectation rather than the expectation itself. Though it seems that in general $2^n\gg 1$ so it's we should be able to write $\approx$ instead. To get the number of "false keys", we would subtract 1 from this number (since this count includes the "true key" as well).

The text then goes on and use this formula for $k=80, n=64, t=2$ and interprets the result as

the likelihood of a false key $k_f$ that performs both encryptions $e_{k_f}(x_1)=y_1$ and $e_{k_f}(x_2)=y_2$ is $2^{80-2\cdot 64}=2^{-48}$.


  1. Did I miss something in the analysis or should this really be an equality instead of an approximation (or lower bound)?
  2. How/why are we interpreting the expected number as a likelihood?
  3. There something odd about the random permutations approach. The argument seems quite loose. There are $2^n!$ permutations and I imagine we usually have $2^k \ll 2^n!$ so we're only enumerating a very small part of the set of all permutations when doing the brute force key search. It's really not equivalent to choosing permutations uniformly at random.... Is there more intuition that someone can help provide? Maybe I'm missing something that's well known in cryptography? Is there another way to do this analysis that's more precise? Any pointers would be greatly appreciated.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.