Double DES meet in the middle attack: number of candidate keys

My question is, where do we get the $2^{64}$ mentioned in the very first sentence?

There are a couple of equivalent ways of looking at the problem.

One way is to treat 2DES with an incorrect key as a completely random mapping; there are $2^{112}$ possible keys, and each incorrect key will map our one known plaintext block to a random ciphertext block; there are $2^{64}$ possible ciphertext blocks (of which 1 is the one which we know is valid); and hence each key will do the mapping correctly is $1 / 2^{64}$; hence the number of keys we expect to happen to get the mapping right is about $2^{112} / 2^{64}$ (as stated in the paragraph).

So wouldn't the number of candidate keys be the number of elements of the intersection of these 2 sets?

That's another, equally valid way of looking at the problem.

If we treat DES (both encrypt and decrypt) with an incorrect key as a completely random mapping, then both the set of $2^{56}$ ciphertexts from the first level encryption, and the $2^{56}$ plaintexts from the second level decryption, are completely random. There are $2^{64}$ plaintexts possible from the second level decryption, and so a specific block is a possible second level decryption with probability circa $2^{56}/2^{64} = 2^{-8}$. There are $2^{56}$ ciphertexts from the first level, and each one happens to be a possible second level decryption with probability $2^{-8}$, and so the expected size of the intersection is, wait for it..., $2^{56} \cdot 2^{-8} = 2^{48}$.

Solved by user452 (131,615 )
Sep 15, 2016 at 21:04