How does the meet in the middle attack work on double DES?

Question

I am having trouble understanding the meet in the middle attack and how it works on double DES.

I understand that on single DES the key length is 2⁵⁶ but why when using double DES is it 2⁵⁷? Can someone explain it in simple terms please?

Answer 1

There is a concept of effective/actual key strength. For Double DES the effective key strength is 2⁵⁷ even though double DES uses 2¹¹² keys. The below example will make it clear.

Assume that you are a cryptanalyst who has access to the plain text and encrypted text. Your aim is to recover the secret key. Assume AAA (plaintext) -> XXX (After 1st encryption) -> ZZZ (after 2nd encryption).

You start with AAA and try all the 2⁵⁶ combinations for secret key by encrypting AAA. This will give you a big list of possible values for XXX. Next you take ZZZ and try all the 2⁵⁶ combinations for secret key by decrypting ZZZ. This will give you a big list of possible values for XXX.

The amount of effort you have put in 2⁵⁶ + 2⁵⁶ = 2⁵⁷.

Now do a simple lookup between the two lists to find a matching value. As soon you see a matching value XXX in both the lists, you have found out the secret key. So this means that with effort of 2⁵⁷ keys you have broken the encryption.

Answer 2

Recovering the key for double-DES takes three steps. Given the plaintext and the ciphertext you do the following:

1. Encrypt the plaintext with all 2⁵⁶ possible keys and write down the results
2. Decrypt the ciphertext with all 2⁵⁶ possible keys and write down the results
3. Check where the results are the same. That is your key.

Note that all you had to do to recover the key was using DES 2 × 2⁵⁶ times, which makes 2⁵⁷.