DES is an encryption standard which uses 56 bit keys. Today computers can use a brute force approach to break the encryption. One simple approach to make the encryption more secure is to apply it twice, using two different keys. This approach is susceptible to the meet in the middle attack developed by Diffie Hellman. 3DES is less susceptible as it encrypts the message three times using 3 keys.

!<scratch-meet-in-the-middle?2des.png 70%! Let’s see why 2DES is vulnerable. Let $Ek$ be the encryption function using the secret key $k$ and $Dk$ the decryption function using the secret key $k$. 2DES uses $Ek1(Ek2(p)) = s$ to encrypt and $Dk2(Dk1(s)) = p$ to decrypt.

Let’s see why 2DES is vulnerable. Let $Ek$ be the encryption function using the secret key $k$ and $Dk$ the decryption function using the secret key $k$. 2DES uses $Ek1(Ek2(p)) = s$ to encrypt and $Dk2(Dk1(s)) = p$ to decrypt.

Diffie Hellman’s meet in the middle attack trades off space for time to find out the two secret keys.

!<scratch-meet-in-the-middle?2des.png 50%! Diffie Hellman’s meet in the middle attack trades off space for time to find out the two secret keys.

For the pattern p it tries all the possible keys to obtain a set of numbers corresponding $Ek(p)$. Also for the pattern s it uses all the possible keys to decrypt s, $Dk(s)$.
If we find any match in the two sets it means that $Ek1(p) = Dk2(s)$ so the secret keys are k1 and k2.
The naive brute force algorithm would go through $2^56^ * 2^56^$ iterations by brute forcing through all possible values of k1 and k2 while this algorithm uses $2^56^ * 56$ memory to store $Ek(p)$ and does $O(2^56^)$ work to find a match.