Meet-in-the-middle
attacks were first introduced by Diffie and Hellman as a cryptanalytic attack
on the DES algorithm. DES is essentially a sound cipher with one exception: the
keyspace is simply too small. In DES, since there are only 56 key bits (2^{56}
possible keys) this is computationally possible nowadays for an attacker to
brute force their way in.

**Double DES (2DES)**

So, what if we were to double encrypt using DES to increase our keyspace? In other words, why not use two rounds of DES encryption with two secret keys for each round (P_{1 –> }*E _{1 –>} E_{2} –> *C

_{1}). Within the context of a brute force attack, this double encryption method seems to provide a higher level of security: 2

^{56}* 2

^{56}= 2

^{112}possible key tests. However, one can use a meet-in-the-middle attack that will completely undermine this security advantage. MITM is a known plaintext attack technique where an attacker has pairs of plaintext and the ciphertext. The main idea is to search for the secrets keys of each encryption round separately (key examples: k

_{a}and k

_{b}). By implementing this technique, it is possible to reduce the complexity of 2DES from 2

^{112}down to 2

^{57}, explained mathematically: 2

^{56}(searches for k

_{a}) + 2

^{56}(searches for k

_{b}) = 2 * 2

^{56}= 2

^{57}

By attacking both sides of the algorithm, storing and looking for matching values (collisions) between the two rounds of encryption or decryption, a MITM attack can effectively reduce the time required to brute force keys.

So how does it work?

There are two phases in a meet-in-the-middle attack. We can break down a simplified 2DES cipher into two basic equations: one equation for encryption and one for decryption. (*Note: P is plaintext, C is ciphertext, k represents the secret keys, E is the encryption algorithm, and D is the decryption algorithm*):

** C = E**_{2}**(k**_{b}**, E**_{1}**(k**_{a}**, P))**

** P = D**_{1}**(k**_{a}**, D**_{2}**(k**_{b}**, C))**

The following equation can be written for this cipher:** **D_{2}(k_{b}, C) = E_{1}(k_{a}, P)

Phase
one begins with breaking the cipher down into two equations (shown above) and
searching through all possible values for k_{a} using the known
plaintext and calculating all possible respective ciphertexts (2^{56}
possible encryptions, represented as k_{a,i}). The results are organized
and stored in a table (2^{56} storage). The second phase is to calculate
the other side of the equation (D_{2}(k_{b}, C)) and determine
all possible values (2^{56} possible decryptions, represented as k_{b,j}).
Finally, the results are compared with the values calculated and stored in the
table from phase one. The attacker is looking for any collisions, or matching
values, of (k_{a,i}, k_{b,j}). Any collisions found have a
relatively high probability of being the secret keys (k_{a}, k_{b}).
Sometimes it is necessary to use a
second pair of known plaintext and ciphertexts. Analyzing the total computational
complexity of a 2DES encryption against a MITM attack is as follows:

**Phase I (2**^{56}** encryptions + 2**^{56}** storage) + Phase II (2**^{56}** encryptions) **

**= 2**^{57}** possible key tests + 2**^{56}** storage**

In other words, a meet-in-the-middle attack here demonstrates how 2DES encryption is only marginally more secure than single DES encryption. The MITM attack is the primary reason why 2DES is not used today and instead 3DES is employed (triple DES encryption).

**Triple DES (3DES)**

3DES has proven to be much more secure than both single and double encryption. To demonstrate this we can use the same attack scheme to see how 3DES has an effective key length of 112 bits:

** Phase I (2**^{56}** encryption + 2**^{56}** storage) + Phase II (2**^{56}** * 2**^{56}** encryption)**

** = 2**^{57}** + 2**^{112}** ≈ 2**^{112}

Because there is
an odd number of encryption rounds there is no middle to ‘meet’ in, and so the
complexity remains high relative to a purely brute force attack on 3DES (which
has the complexity of 2^{56} * 2^{56} * 2^{56} = 2^{168}).