Meet-in-the-middle attack

The meet-in-the-middle attack (MITM), a known-plaintext attack, is a generic space–time tradeoff cryptographic attack against encryption schemes that rely on performing multiple encryption operations in sequence. The MITM attack is the primary reason why Double DES is not used and why a Triple DES key (168-bit) can be brute-forced by an attacker with 2⁵⁶ space and 2¹¹² operations.

Their attack used a space–time tradeoff to break the double-encryption scheme in only twice the time needed to break the single-encryption scheme.

In 2011, Bo Zhu and Guang Gong investigated the multidimensional meet-in-the-middle attack and presented new attacks on the block ciphers GOST, KTANTAN and Hummingbird-2.

thumb|upright=1.5|An illustration of 1D-MITM attack

MITM algorithm

Compute the following:

• <math>\mathit{SubCipher}_1=\mathit{ENC}_{f_1}(k_{f_1},P),\; \forall k_{f_1} \in K </math>:
• : and save each <math>\mathit{SubCipher}_{1} </math> together with corresponding <math> k_{f_1} </math> in a set A
• <math>\mathit{SubCipher}_1=\mathit{DEC}_{b_1}(k_{b_1},C),\; \forall k_{b_1} \in K </math>:
• : and compare each new <math>\mathit{SubCipher}_1 </math> with the set A

When a match is found, keep <math>k_{f_1},k_{b_1}</math> as candidate key-pair in a table T. Test pairs in T on a new pair of to confirm validity. If the key-pair does not work on this new pair, do MITM again on a new pair of .

MITM complexity

If the keysize is k, this attack uses only 2^k+1 encryptions (and decryptions) and O(2^k) memory to store the results of the forward computations in a lookup table, in contrast to the naive attack, which needs 2^2·k encryptions but O(1) space.

Multidimensional MITM (MD-MITM)

While 1D-MITM can be efficient, a more sophisticated attack has been developed: multidimensional meet-in-the-middle attack, also abbreviated MD-MITM.

This is preferred when the data has been encrypted using more than 2 encryptions with different keys.

Instead of meeting in the middle (one place in the sequence), the MD-MITM attack attempts to reach several specific intermediate states using the forward and backward computations at several positions in the cipher.

Assume that the attack has to be mounted on a block cipher, where the encryption and decryption is defined as before:

: <math> C=\mathit{ENC}_{k_n}(\mathit{ENC}_{k_{n-1(...(\mathit{ENC}_{k_1}(P))...))</math> <br />

: <math> P=\mathit{DEC}_{k_1}(\mathit{DEC}_{k_2}(...(\mathit{DEC}_{k_n}(C))...))</math>

that is a plaintext P is encrypted multiple times using a repetition of the same block cipher

thumb|center|upright=4|An illustration of MD-MITM attack

The MD-MITM has been used for cryptanalysis of, among many, the GOST block cipher, where it has been shown that a 3D-MITM has significantly reduced the time complexity for an attack on it.