# Double DES meet in the middle attack: probability that wrong key pair remains

My Question is based on poncho's answer in this post.

If you're doing a meet-in-the-middle attack against 2DES with only on a plaintext-ciphertext pair $$(P,C)$$, I understand that the expected amount of remaining key candidates is $$2^{48}$$, assuming that DES encryption/decryption yields a random 64-bit block if done with a wrong key.

What makes me curious now is: if you have another plaintext-ciphertext pair $$(P',C')$$ to validate the candidates, what is the probability that a wrong key still remains?

So my approach is the following: We just start a new attack, with the reduced key set. Since there are only $$2^{48}$$ keys left, the possibility of a specific block is $$\frac{2^{48}}{2^{64}}$$ which is $$2^{-16}$$. Is this is already the possibility I'm looking for? If yes, then this leads me to the conclusion that despite the probability of one specific block is very small, there are still $$2^{48} * 2^{-16} = 2^{32}$$ candidates in the set!

The reason I say approximation is that the second search in the sample space should really be conducted in the restricted set of DES permuataions that already map $$P$$ to $$C$$ (sampling without replacement) but for such a huge sample space the inaccuracy due to not doing this is likely much much less than the modelling step of assuming DES is a pseudorandom permutation.
• So I asked my crypto teacher about this and she told me $2^{32}$ is wrong, because we we have $2^{48}$ key candidates (pairs) left. So every key of the first set only maps to one of the other set, since they matched. This was not the case in the first run of the attack, where every key could map to any of the $2^{56}$ of the other set and we didn't knew which one. So $2^{-16}$ is the probability of a wrong key remaining in the set. Only my conclusion $2^{48} * 2^{−16}=2^{32}$ is wrong, but I still don't get why ... – Wigglepee Oct 20 '18 at 18:50