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

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?

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.

• 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}$? – scribe Dec 15 '20 at 23:54
• @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$? – poncho Dec 15 '20 at 23:57
• 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}$. – scribe Dec 16 '20 at 0:14
• @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. – kodlu Dec 16 '20 at 0:31