Meet-in-the-middle Attack - Multidimensional-MITM

Multidimensional-MITM

While 1D-MITM can be efficient, a more sophisticated attack has been developed: Multi Dimensional-Meet In The Middle attack, also abbreviated MD-MITM. This is more 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:

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

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.