What is meant by encrypting/decrypting a known plaintext/ciphertext with every possible key in meet-in-the-middle?

Question

I am working on the Meet-in-the-middle attack on 2DES and I have got some questions I am not sure about. I read several websites/articles about it so I have got an idea of what it is and how it works. However, I do not fully understand what is meant by every possible key.

Let me give an example:

I have a known plaintext, which I encrypt with 2DES - My key only has 20 effective bits of the 64 bits. So, the 20 bits are set as the high order and the rest is padded with zeros (have skipped over all parity bits). This gives me a ciphertext, which is encrypted twice with two different keys. So, when I want to perform a MITM attack on it, I have to encrypt the known plaintext with every possible key (= 2^20) and store the results i.e. the intermediate cipher and the key used in a, let's say, a HashMap where the input is - The Hash key is not an integer.

Next, I have to decrypt the known ciphertext with every possible key and find a match between the decrypted cipher text and one of the encrypted plaintexts in the HashMap.

What confuses me here is what is meant by "every possible key"? Are 2^20 keys generated with random 20 bits (in my case)? If so, this would result in collisions.

Answer 1

Your question has given to you only 20-bit key space so, you can achieve it. As mentioned earlier, even storing one full table is not an easy job and accessing $2^{56}$,too, although we know that Titan can reach $2^{62}$ around one hour, it is a supercomputer. Your task simply says that your key will be in the format in binary case as:

xxxxxxxpxxxxxxxpxxxxxx0p0000000p0000000p0000000p0000000p0000000p

so you have to iterate for x's from

0000000p0000000p0000000p0000000p0000000p0000000p0000000p0000000p

to

1111111p1111111p1111110p0000000p0000000p0000000p0000000p0000000p

and store them in a table T1 ( or hash map). (There are 64-bit over there). The p represents the parity bits.

From Wikipedia:

Initially, 56 bits of the key are selected from the initial 64 by Permuted Choice 1 (PC-1)—the remaining eight bits are either discarded or used as parity check bits

In the next step, use the same iteration for the decryption and look for the result in T1.

Answer 2

An attacker can compute every possible encryption (with every possible key) of a given plaintext and every possible decryption of a given ciphertext. If a result from any encryption matches your decryption, the pair $k_1$ and $k_2$ is possibly the correct key (so-called "candidate key").

1. Compute: $ENC_{k1}(P)\space \forall \space k_1$

($\forall$ = for all)

2. Compute: $DEC_{k2}(C)\space \forall \space k_2$

So an attacker would have to compute $2^{k_1} + 2^{k_2} = 2^{k_1+1}$ keys.

In your case: $keylength = 20 \rightarrow 2^{20+1} = 2^{21}$ keys.