Editing Meet-in-the-middle attack (section)

=== MD-MITM complexity ===
Time complexity of this attack without brute force, is <math>2^{|k_{f_1}|}+2^{|k_{b_{n+1}}|}+2^{|s_1|}</math>⋅<math>(2^{|k_{b_1}|}+2^{|k_{f_2}|}+2^{|s_2|}</math>⋅<math>(2^{|k_{b_2}|}+2^{|k_{f_3}|}+\cdots))</math>

Regarding the memory complexity, it is easy to see that  <math>T_2,T_3,... ,T_n</math> are much smaller than the first built table of candidate values: <math>T_1</math> as i increases, the candidate values contained in <math>T_i</math> must satisfy more conditions thereby fewer candidates will pass on to the end destination <math>T_n</math>.

An upper bound of the memory complexity of MD-MITM is then

:<math> 2^{|k_{f_1}|}+2^{|k_{b_{n+1}}|}+2^{|k|-|s_n|}\cdots</math>

where {{mvar|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 <math>1/2^{|l|}</math>, where {{mvar|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 MITM-phase, it is <math>2^{|k|}/2^{|l|}</math>.

Therefore, after the first MITM phase, there are <math>2^{|k|-b} \cdot 2^{-b} = 2^{|k|-2b}</math>, where <math>|b|</math> is the block size.

For each time the final candidate value of the keys are tested on a new plaintext/ciphertext-pair, the number of keys that will pass will be multiplied by the probability that a key may pass which is <math>1/2^{|b|}</math>.

The part of brute force testing (testing the candidate key on new {{tmath|(P,C)}}-pairs, have time complexity  <math>2^{|k|-b}+2^{|k|-2b}+2^{|k|-3b}+2^{|k|-4b}\cdots</math>
, 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 <math>\lceil|k|/n\rceil</math> {{tmath|(P,C)}}-pairs.

Below is a specific example of how a 2D-MITM is mounted: