!<blog/meet-in-the-middle?2des.png 70%!
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.

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.

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 does $2^56^ * 2^56^$ iterations going through all possible values of k1 and k2 while this algorithm uses $2^56^ * 56$ memory to store $Ek(p)$ and does $2^56^$ work to find a match.

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 does $2^56^ * 2^56^$ iterations going through all possible values of k1 and k2 while this algorithm uses $2^56^ * 56$ memory to store all Eki(p) and does $2^56^$ work to find a match.

h2. Discrete logarithm