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

Question

I'm new to cryptography and found this statement in a book, which says that when having a message block of $64$ bits and using a key of $56$ bits, we will get $\frac{2^{112}}{2^{64}}=2^{48}$ candidate keys if we encrypt a given plaintext and decrypt the corresponding ciphertext (in double DES).

So, assuming that using one key, each of the $2^{64}$ plaintexts will be mapped to again $2^{64}$ ciphertexts and let's also assume that the function of encryption is such, that there are no repetitive ciphertexts, that being said, the mapping is bijective. Now, if we make a new set of ciphertexts for each key, there will be a total of $2^{56}$ (out of $2^{64}!$ possible permutations) different sets, corresponding to different mappings. My question is, where do we get the $2^{64}$ mentioned in the very first sentence? I get it that there are $2^{64}$ possible ciphertexts, but don't we get a set of $2^{56}$ ciphertexts from encryption, and also that much from decryption? So wouldn't the number of candidate keys be the number of elements of the intersection of these 2 sets?

Answer 1

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}$.