1
$\begingroup$

I was reading my professors slides, I understand how meet in the middle works, but I have a few confusions. So we need two $\{(P_1, C_1), (P_2, C_2)\}$. Let $\lg{(k_1)} = \lg{(k_2)} = 56$, we generate $2^{56}$ of the $X = \{x_i = E_{k_{1,i}}(P_1)\}$ and $2^{56}$ of the $Y = \{y_i = D_{k_{2,i}}(C_1)\}$. So far it took us $2^{56}+ 2^{56}= 2^{57}$ steps to compute $X, Y$.

My understanding is that this is why we say that double DES only increases security by one bit?

Now our job is to find all $x_i,y_j$ such that $x_i = y_j$. I suppose we can use $2^{56}$ binary searches so we could do this in $2^{56}\lg{2^{56}}= 2^{56} \times 56$ steps?

Total steps are now:

\begin{align*} 2^{57}+(2^{56} \times 56) &= 2^{57}+(2^{56} \times (2^5+24)) \\ &= 2^{57}+(2^{56+5} + (2^{56}\times24)) \\ &= 2^{57}+2^{61} + (2^{56}\times24) \\ &= 2^{61}+2^{57} + (2^{56}\times24) \\ \end{align*}

Now we worry about how many candidate paires do we have to check on the second plaintext ciphertext pair $(P_2, C_2)$. This depends on how many collisions we saw from the previous step. On average the probability is that $x_i = y_j$ is $1/2^{56}$ right? Here is one of the confusions, the slides I am reading say that it is $1/2^{64}$. Since I can't see why, for now I'll proceed with $1/2^{56}$. So the average number of collisions thus must be,

$$ \frac{2^{112}}{2^{56}} = 2^{56} $$

So now we have to check the $2^{56}$ candidate pairs on $(P_2, C_2)$ meaning the average number of steps are now:

$$ 2^{61}+2^{57} + (2^{56}\times24) + 2^{56} $$

But the slides do this analysis like this, they say there are $2^{64}$ many $x_i$ thus the candidate checks are $2^{112-64} = 2^{48}$. This is followed by this slide which is entirely lost on me:

enter image description here

Could someone offer some clarification?

EDIT: I think I see my oversight, the $|X| = |Y| = 2^{56}$ are subsets of the exhaustive $|X'| = |Y'| = 2^{64}$ sets because $\lg{(x_i)} = \lg{(y_i)} = 64$. Hence $X, Y$ were sampled using encryption decryption. Therefore, when we calculate the collision probablity, we use the cardinalities of the $X', Y'$ yielding $1/2^{64}$.

Is this right?

$\endgroup$
2
$\begingroup$

Now our job is to find all $x_i,y_j$ such that $x_i = y_j$. I suppose we can use $2^{56}$ binary searches so we could do this in $2^{56}\lg{2^{56}}= 2^{56} \times 56$ steps?

Actually, you're more likely to go with a hashing-based approach (which doesn't scale at O(n log n)), or a disk-based sorting approach (which is technically O(n log n), but a rather better constant of proportionality than repeated binary search); a binary search approach would run into a lot of cache misses (assuming you had that much memory). On the other hand, sifting through that much data is a tad on the nontrivial side, and one we generally ignore when doing this high-level analysis; we simplify the problem by assuming that all computations, aside from the DES evaluations themselves, are "free".

And, the 'steps' involved with doing this search for duplicates are quite a bit different than performing a DES operation (and are likely to be considerably faster); that makes it difficult to sum them meaningfully.

However, to get your real question:

on average the probability is that $x_i = y_j$ is $1/2^{56}$ right?

Nope; it's $2^{-64}$; that's because both $x_i, y_j$ are 64 bits, and can be assumed (with an incorrect key) to act completely random.

So now we have to check the $2^{56}$ candidate pairs

Nope; there are about $2^{112} / 2^{64} = 2^{48}$ expected

That should explain where the slide is coming from.

$\endgroup$
4
  • $\begingroup$ I don't see how the length of $x_i$ has anything to do with the cardinality of $X$. We constructed $X$ like this $X = \{1 \leq i \leq 2^{56} : E_{k_{1,i}}(P_1)\}$ since the key space has $2^{56}$ keys. Therefore, could you elaborate the math which shows that $p(x_i = y_j) = 2^{-64}$? $\endgroup$ – scribe Dec 15 '20 at 23:54
  • 1
    $\begingroup$ @scribe: I don't see how the cardinality of $X$ has anything to do with the probability $p(x_i = y_j)$, for any specific $x_i, y_j$. For an incorrect key guess, $x_i$ is a random 64 bit value, and so is $y_j$. The probability that $y_j$ just happens to be the same random 64 bit value that $x_i$ is is $2^{-64}$. Look at it this way; suppose we tried just one $x_0, y_0$ value (and so the cardinality of $X$ is 1. What's the probability that $x_0 = y_0$? $\endgroup$ – poncho Dec 15 '20 at 23:57
  • $\begingroup$ I am stuck incorrectly thinking of this as some $x_i \in X$ as a side of a $|Y| = 2^{56}$ sided die. Which when rolled, the probability of pulling out $x_i$ out of $Y$, i. e., a collision is then $1/|Y| = 1/2^{56}$. $\endgroup$ – scribe Dec 16 '20 at 0:14
  • $\begingroup$ @poncho, nice answer; would you say that hashing based approach has constant lookup complexity? Even for such a large table, say as $n$ goes from 48 to 64 just to pick some numbers. $\endgroup$ – kodlu Dec 16 '20 at 0:31

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.