Meet-in-the-Middle Attacks (MITM)

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 (256 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 (P1 –> E1 –> E2 –> C1). Within the context of a brute force attack, this double encryption method seems to provide a higher level of security: 256 * 256 = 2112 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: ka and kb). By implementing this technique, it is possible to reduce the complexity of 2DES from 2112 down to 257, explained mathematically: 256 (searches for ka) + 256 (searches for kb) = 2 * 256 = 257

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 = E2(kb, E1(ka, P))

            P = D1(ka, D2(kb, C))

The following equation can be written for this cipher: D2(kb, C) = E1(ka, P)

Phase one begins with breaking the cipher down into two equations (shown above) and searching through all possible values for ka using the known plaintext and calculating all possible respective ciphertexts (256 possible encryptions, represented as ka,i). The results are organized and stored in a table (256 storage). The second phase is to calculate the other side of the equation (D2(kb, C)) and determine all possible values (256 possible decryptions, represented as kb,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 (ka,i, kb,j). Any collisions found have a relatively high probability of being the secret keys (ka, kb).  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 (256 encryptions + 256 storage) + Phase II (256 encryptions)

= 257 possible key tests + 256 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 (256 encryption + 256 storage) + Phase II (256 * 256 encryption)

            = 257 + 2112 ≈ 2112

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 256 * 256 * 256 = 2168).