Meetinthemiddle attack
This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages)
(Learn how and when to remove this template message)

The meetinthemiddle attack (MITM) 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 (168bit) can be bruteforced by an attacker with 2^{56} space and 2^{112} operations.^{[1]}^{[2]}
Description[edit]
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 ntuples the security of the multipleencryption scheme, depending on the number of times the data is encrypted, because an exhaustive search on all possible combination of keys (simple bruteforce) would take 2^{n·k} attempts if the data is encrypted with kbit keys n times.
The MITM 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 the decryption keys. This makes a MeetintheMiddle attack (MITM) a generic space–time tradeoff cryptographic attack.
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 56bit keys, Double DES can be broken with 2^{57} encryption and decryption operations.
The multidimensional MITM (MDMITM) uses a combination of several simultaneous MITM attacks like described above, where the meeting happens in multiple positions in the composed function.
History[edit]
Diffie and Hellman first proposed the meetinthemiddle attack on a hypothetical expansion of a block cipher in 1977.^{[3]} Their attack used a space–time tradeoff to break the doubleencryption scheme in only twice the time needed to break the singleencryption scheme.
In 2011, Bo Zhu and Guang Gong investigated the multidimensional meetinthemiddle attack and presented new attacks on the block ciphers GOST, KTANTAN and Hummingbird2.^{[4]}
Meetinthemiddle (1DMITM)[edit]
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 k_{1} and k_{2} are two keys.
The naive approach at bruteforcing this encryption scheme is to decrypt the ciphertext with every possible k_{2}, and decrypt each of the intermediate outputs with every possible k_{1}, for a total of 2^{k1} × 2^{k2} (or 2^{k1+k2}) operations.
The meetinthemiddle attack uses a more efficient approach. By decrypting C with k_{2}, one obtains the following equivalence:
The attacker can compute ENC_{k1}(P) for all values of k_{1} and DEC_{k2}(C) for all possible values of k_{2}, for a total of 2^{k1} + 2^{k2} (or 2^{k1+1}, if k_{1} and k_{2} are the same size) operations. If the result from any of the ENC_{k1}(P) operations matches a result from the DEC_{k2}(C) operations, the pair of k_{1} and k_{2} is possibly the correct key. This potentiallycorrect key is called a candidate key. The attacker can determine which candidate key is correct by testing it with a second testset of plaintext and ciphertext.
The MITM attack is one of the reasons why Data Encryption Standard (DES) was replaced with Triple DES and not Double DES. An attacker can use a MITM attack to bruteforce Double DES with 2^{57} operations and 2^{56} space, making it only a small improvement over DES.^{[5]} Triple DES uses a "triple length" (168bit) key and is also vulnerable to a meetinthemiddle attack in 2^{56} space and 2^{112} operations, but is considered secure due to the size of its keyspace.^{[1]}^{[2]}
MITM algorithm[edit]
Compute the following:
 :
 and save each together with corresponding in a set A
 :
 and compare each new with the set A
When a match is found, keep k_{f1},k_{b1} as candidate keypair in a table T. Test pairs in T on a new pair of to confirm validity. If the keypair does not work on this new pair, do MITM again on a new pair of .
MITM complexity[edit]
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 (MDMITM)[edit]
This section possibly contains original research. (May 2013) (Learn how and when to remove this template message) 
While 1DMITM can be efficient, a more sophisticated attack has been developed: multidimensional meetinthemiddle attack, also abbreviated MDMITM. 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 MDMITM attack attempts to reach several specific intermediate states using the forward and backward computations at several positions in the cipher.^{[4]}
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 MDMITM has been used for cryptanalysis of, among many, the GOST block cipher, where it has been shown that a 3DMITM has significantly reduced the time complexity for an attack on it.^{[4]}
MDMITM algorithm[edit]
This section does not cite any sources. (May 2015) (Learn how and when to remove this template message) 
Compute the following:
 and save each together with corresponding in a set .
 and save each together with corresponding in a set .
For each possible guess on the intermediate state compute the following:
 and for each match between this and the set , save and in a new set .
 ^{[verification needed]}
 and save each together with corresponding in a set .
 For each possible guess on an intermediate state compute the following:

 and for each match between this and the set , check also whether
 it matches with and then save the combination of subkeys together in a new set .
 For each possible guess on an intermediate state compute the following:
 and for each match between this and the set , check also whether it matches with , save and in a new set .
 and for each match between this and the set , check also

whether it matches with . If this is the case then:"
Use the found combination of subkeys on another pair of plaintext/ciphertext to verify the correctness of the key.
Note the nested element in the algorithm. The guess on every possible value on s_{j} is done for each guess on the previous s_{j1}. This make up an element of exponential complexity to overall time complexity of this MDMITM attack.
MDMITM complexity[edit]
Time complexity of this attack without brute force, is ⋅⋅
Regarding the memory complexity, it is easy to see that are much smaller than the first built table of candidate values: as i increases, the candidate values contained in must satisfy more conditions thereby fewer candidates will pass on to the end destination .
An upper bound of the memory complexity of MDMITM 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 , where l is the intermediate state in the first MITM phase. The size of the intermediate state and the block size is often the same! Considering also how many keys that are left for testing after the first MITMphase, it is .
Therefore, after the first MITM phase, there are , where is the block size.
For each time the final candidate value of the keys are tested on a new plaintext/ciphertextpair, the number of keys that will pass will be multiplied by the probability that a key may pass which is .
The part of brute force testing (testing the candidate key on new pairs, have time complexity , clearly for increasing multiples of b in the exponent, number tends to zero.
The conclusion on data complexity is by similar reasoning restricted by that around pairs.
Below is a specific example of how a 2DMITM is mounted:
A general example of 2DMITM[edit]
This is a general description of how 2DMITM is mounted on a block cipher encryption.
In twodimensional MITM (2DMITM) the method is to reach 2 intermediate states inside the multiple encryption of the plaintext. See below figure:
2DMITM algorithm[edit]
Compute the following:
 and save each together with corresponding in a set A
 and save each together with corresponding in a set B.
For each possible guess on an intermediate state s between and compute the following:

 and for each match between this and the set A, save and in a new set T.

 and for each match between this and the set B, check also whether it matches with T for
 if this is the case then:
Use the found combination of subkeys on another pair of plaintext/ciphertext to verify the correctness of the key.
2DMITM complexity[edit]
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.
For data complexity see subsection on complexity for MDMITM.
See also[edit]
 Birthday attack
 Wireless security
 Cryptography
 3subset meetinthemiddle attack
 Partialmatching meetinthemiddle attack
References[edit]
 ^ ^{a} ^{b} Moore, Stephane (November 16, 2010). "MeetintheMiddle Attacks" (PDF): 2. Cite journal requires
journal=
(help)  ^ ^{a} ^{b} Blondeau, Céline. "Lecture 3: Block Ciphers" (PDF). CSE4320 Cryptography and Data Security.
 ^ ^ Diffie, Whitfield; Hellman, Martin E. (June 1977). "Exhaustive Cryptanalysis of the NBS Data Encryption Standard" (PDF). Computer. 10 (6): 74–84. doi:10.1109/CM.1977.217750.
 ^ ^{a} ^{b} ^{c} Zhu, Bo; Guang Gong (2011). "MDMITM Attack and Its Applications to GOST, KTANTAN and Hummingbird2". eCrypt.
 ^ Zhu, Bo; Guang Gong (2011). "MDMITM Attack and Its Applications to GOST, KTANTAN and Hummingbird2". eCrypt.