Meet-in-the-middle attack
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[clarification needed] by an attacker with 256 space and 2112 operations.
[2] When trying to improve the security of a block cipher, a tempting idea is to encrypt the data several times using multiple keys.
One might think this doubles or even n-tuples the security of the multiple-encryption scheme, depending on the number of times the data is encrypted, because an exhaustive search on all possible combinations of keys (simple brute force) would take 2n·k attempts if the data is encrypted with k-bit keys n times.
The MITM attack is a generic attack which weakens the security benefits of using multiple encryptions by storing intermediate values from the encryptions or decryptions and using those to improve the time required to brute force[clarification needed] the decryption keys.
The MITM attack attempts to find the keys by using both the range (ciphertext) and domain (plaintext) of the composition of several functions (or block ciphers) such that the forward mapping through the first functions is the same as the backward mapping (inverse image) through the last functions, quite literally meeting in the middle of the composed function.
For example, although Double DES encrypts the data with two different 56-bit keys, Double DES can be broken with 257 encryption and decryption operations.
The multidimensional MITM (MD-MITM) uses a combination of several simultaneous MITM attacks like described above, where the meeting happens in multiple positions in the composed function.
Diffie and Hellman first proposed the meet-in-the-middle attack on a hypothetical expansion of a block cipher in 1977.
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.
[5] Assume someone wants to attack an encryption scheme with the following characteristics for a given plaintext P and ciphertext C: where ENC is the encryption function, DEC the decryption function defined as ENC−1 (inverse mapping) and k1 and k2 are two keys.
The naive approach at brute-forcing this encryption scheme is to decrypt the ciphertext with every possible k2, and decrypt each of the intermediate outputs with every possible k1, for a total of 2|k1| × 2|k2| (or 2|k1|+|k2|) operations.
By decrypting C with k2, one obtains the following equivalence: The attacker can compute ENCk1(P) for all values of k1 and DECk2(C) for all possible values of k2, for a total of 2|k1| + 2|k2| (or 2|k1|+1, if k1 and k2 have the same size) operations.
The attacker can determine which candidate key is correct by testing it with a second test-set of plaintext and ciphertext.
An attacker can use a MITM attack to bruteforce Double DES with 257 operations and 256 space, making it only a small improvement over DES.
[5] Triple DES uses a "triple length" (168-bit) key and is also vulnerable to a meet-in-the-middle attack in 256 space and 2112 operations, but is considered secure due to the size of its keyspace.
If the keysize is k, this attack uses only 2k+1 encryptions (and decryptions) and O(2k) memory to store the results of the forward computations in a lookup table, in contrast to the naive attack, which needs 22·k encryptions but O(1) space.
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.
[5] 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.
[5] Compute the following: For each possible guess on the intermediate state
Time complexity of this attack without brute force, is
are much smaller than the first built table of candidate values:
must satisfy more conditions thereby fewer candidates will pass on to the end destination
An upper bound of the memory complexity of MD-MITM is then where k denotes the length of the whole key (combined).
The data complexity depends on the probability that a wrong key may pass (obtain a false positive), which is
Considering also how many keys that are left for testing after the first MITM-phase, it is
The conclusion on data complexity is by similar reasoning restricted by that around
In two-dimensional MITM (2D-MITM) the method is to reach 2 intermediate states inside the multiple encryption of the plaintext.
See below figure: Compute the following: For each possible guess on an intermediate state s between
Time complexity of this attack without brute force, is where |⋅| denotes the length.
Main memory consumption is restricted by the construction of the sets A and B where T is much smaller than the others.
