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

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^56 but why when using double DES is it 2^57? Can someone explain it in simple terms please?

There is a concept of effective/actual key strength. For Double DES the effective key strength is 2^57 even though double DES uses 2^112 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^56 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^56 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^56 + 2^56 = 2^57.

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^57 keys you have broken the encryption.

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^56 possible keys and write down the results
2. Decrypt the ciphertext with all 2^56 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^56 times, which makes 2^57.