- des meet-in-the-middle-attack
- Updated Mon, 30 May 2022 22:38:50 GMT

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?

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

- +0 – Should be 2^56 / 2^64 in the second paragraph. — Oct 18, 2017 at 10:02
- +0 – @FD_: no, it is correct as written. I am discussing the total number of keys that we expect to map a specific plaintext to a specific ciphertext; there are a total of $2^{112}$ keys (and hence maps), and the probability that any one map is correct is $2^{-64}$; the expected number is the product of these two. — Oct 18, 2017 at 13:14
- +0 – Sorry, I think I wasn't clear enough: there's a 256 in 256/2^64 that I think should be 2^56 instead (a syntax issue). Near the end of your answer. — Oct 18, 2017 at 13:23
- +0 – @FD_: sorry, I counted paragraphs differently than you. — Oct 18, 2017 at 13:25
- +0 – @FD_: actually, thank you for pointing out my typo... — Oct 18, 2017 at 13:39