How many collisions (identical pairs) are possible in meet in the middle attack on double DES with two unique keys?

Question

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:

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?

Answer 1

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.