0
$\begingroup$

In page 358 of Bruce Schneier's Apllied Crypto, when explaining the meet-in-the-middle attack, he states that the success probability is «1 in $2^{2m - 2n}$» with two plaintext/ciphertext pairs, and «1 in $2^{3m - 2n}$» if one uses one additional pt/ct pair. $n$ is the key length, and $m$ the block length.

My question is: shouldn't $m$ and $n$ be reversed? I.e. «1 in $2^{2n - 2m}$» and «1 in $2^{2n - 3m}$»? As stated in the book, we would get a lower success probability when using 3 pairs, as «1 in $2^{2m - 2n}$» is a bigger probability than «1 in $2^{3m - 2n}$» (because $2^{3m - 2n}$ > $2^{2m - 2n}$).

Or is there something obvious that I am not seeing?

$\endgroup$
2
$\begingroup$

In the sentence, the "probability of success" of «1 in $2^{2m - 2n}$» or «1 in $2^{3m - 2n}$» really is an approximation of the probability of concluding that the key was found, when in fact another key that happens to give the same result as the true key for 2 or 3 blocks was found.

It should be read "probability of wrongly concluding success" instead; or "probability of false positive".

$\endgroup$
  • $\begingroup$ This makes no sense. In the scenario of the book, this probability is calculated when the cryptanalyst already has one key, he just doesn't know if it is the right one. What you are describing is the probability of unsuccess, which is the exact opposite of what is stated (and it is also not calculated like this, as far as I can tell). $\endgroup$ – wmnorth Mar 19 at 22:12
  • 2
    $\begingroup$ @wmnorth: in the above comment, does "this" refer to the scenario of the book, or to the answer that I propose? The answer agrees with you that what the book and the answer discuss is not the probability of success, and that it is only a raw approximation of the probability that finding a key was not a success. $\endgroup$ – fgrieu Mar 20 at 8:50
2
$\begingroup$

We are given two plaintext/ciphertext pairs $(P_1, C_1)$ and $(P_2, C_2)$ with $E_{k_1^*}(P_i) = D_{k_2^*}(C_i)$ where the true key is $k^* = (k_1^*, k_2^*)$. Suppose the cipher key is $n$ bits long, and the block is $b$ bits long. (Schneier uses $m$ for the block size, but as a confusion of minims I cannot keep these letters straight, so I will use the much more sensible letter $b$ for block size.)

Let's model the $k_i^*$ as independent uniform random bit strings, because that's how a sensible user will choose them. For simplicity, let's model $E_{k_1}$ and $D_{k_2}$ as independent uniform random functions. Obviously this model is wrong because they're both permutations, and if $k_1 = k_2$ then they can't be independent, but $\Pr[k_1 = k_2] = 1/2^n$ so this event happens only a negligible fraction of the time, and all models are wrong—some are just useful.

Suppose we find a candidate key $k = (k_1, k_2)$ such that $E_{k_1}(P_1) = D_{k_2}(C_1)$. What is the probability that $k = k^*$ given this—that is, what is the probability that we have found the true key given that we have found a matching candidate?

A priori, $\Pr[k = k^*] = 2^{-2n}$ because the true key $k^*$ is uniformly distributed among $2^{2n}$ possibilities. And obviously if $k = k^*$, then $E_{k_1}(P_1) = D_{k_2}(C_1)$ with probability $1$; whereas if $k \ne k^*$, then in the independent uniform random function model for $E$ and $D$, we have $E_{k_1}(P_1) = D_{k_2}(C_1)$ with probability $2^{-b}$. The unconditional probability that $E_{k_1}(P_1) = D_{k_2}(C_1)$ is

\begin{align*} \Pr&\bigl[E_{k_1}(P_1) = D_{k_2}(C_2)\bigr] \\ &= \Pr[E_{k_1}(P_1) = D_{k_2}(C_2) \bigm| k = k^*\bigr] \Pr[k = k^*] \\ &\qquad + \Pr[E_{k_1}(P_1) = D_{k_2}(C_2) \bigm| k \ne k^*\bigr] \Pr[k \ne k^*] \\ &= 2^{-2n} + 2^{-b} (1 - 2^{-2n}). \end{align*}

So by Bayes' rule, the conditional probability that the key is correct given that it matches a known plaintext/ciphertext pair is

\begin{align*} \Pr&\bigl[k = k^* \bigm| E_{k_1}(P_1) = D_{k_2}(C_1)\bigr] \\ &= \Pr[k = k^*] \frac{\Pr\bigl[E_{k_1}(P_1) = D_{k_2}(C_2) \bigm| k = k^*\bigr]} {\Pr\bigl[E_{k_1}(P_1) = D_{k_2}(C_2)\bigr]} \\ &= 2^{-2n} \frac{1} {2^{-2n} + 2^{-b}(1 - 2^{-2n})} \\ &= \frac{1}{1 + 2^{-b} (2^{2n} - 1)} \\ &= \frac{2^b}{2^b + 2^{2n} - 1}. \end{align*}

For $b \ll 2n$, this is roughly $2^{b - 2n}$. For $b = 2n$, this is roughly $1/2$. For $b \gg 2n$, this is roughly $1$.

What if we also confirm $E_{k_1}(P_2) = D_{k_2}(C_2)$? Then it is roughly as if the block size were $2b$ instead of $b$ in the above analysis since we are considering whether $E'_{k_1}(P_1, P_2) = D'_{k_2}(C_1, C_2)$ where $E'_{k_1}(P_1, P_2) = \bigl(E_{k_1}(P_1), E_{k_1}(P_2)\bigr)$ and likewise for $D'$. In this case, the conditional probability of a true positive is about $2^{2b - 2n}$, or $2^{3b - 2n}$ with three blocks, and so on, until the total size of the blocks reaches the size of the combined key at which point the probability rapidly converges to $1$.


In conclusion, I think you are correct that Schneier mixed up the sense of the ‘success probability’ (better named ‘true positive probability’): it should have just been $2^{2m - 2n}$, $2^{3m - 2n}$, etc., not $1$ in $2^{2m - 2n}$, $1$ in $2^{3m - 2n}$, etc., where $m$ is the confusingly named block size.

It is a small error in a book that is otherwise full of grievous intellectual harm.

$\endgroup$
  • 1
    $\begingroup$ Mr. Schneier will be the first to admit that the second edition of his most famous book is not perfect, and that it is getting a bit old, too. But let's not forget what a valuable contribution he made to applied cryptography. In fact, it's a landmark work. As Whitfield Diffie said, the book gave programmers and engineers a place to turn to when there was none before. For that alone he deserves much credit. $\endgroup$ – Patriot Sep 19 at 4:47
  • 1
    $\begingroup$ It's a landmark work that set a generation of cryptography nerds running with scissors. We're still cleaning up the bloody mess of conceptual misguidance today. $\endgroup$ – Squeamish Ossifrage Sep 19 at 15:44
  • $\begingroup$ And sock slides... $\endgroup$ – Patriot Sep 19 at 15:48

Your Answer

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

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