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

== Multidimensional MITM (MD-MITM) ==
{{Original research|section|date=May 2013}}

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.<ref name="ZhuGuang2011">{{cite journal |last1=Zhu |first1=Bo |last2=Gong |first2=Guang |author2-link=Guang Gong |year=2014 |title=Multidimensional meet-in-the-middle attack and its applications to KATAN32/48/64 |url=https://doi.org/10.1007/s12095-014-0102-9 |journal=Cryptography and Communications |volume=6 |issue=4 |pages=313–333 |doi=10.1007/s12095-014-0102-9 |via=Springer Link}}</ref>

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

[[File:MD MITMNEW.png|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)|GOST block cipher]], where it has been shown that a 3D-MITM has significantly reduced the time complexity for an attack on it.<ref name="ZhuGuang2011" />

=== MD-MITM algorithm ===
{{Unreferenced section|date=May 2015}}

Compute the following:
:; <math> \mathit{SubCipher}_1=\mathit{ENC}_{f_1}(k_{f_1},P)\qquad\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 <math>H_1</math>.

:; <math> \mathit{SubCipher}_{n+1}=\mathit{DEC}_{b_{n+1}}(k_{b_{n+1}},C) \qquad\forall k_{b_{n+1}}  \in K </math>
:: and save each <math>\mathit{SubCipher}_{n+1}</math> together with corresponding <math>k_{b_{n+1}}</math> in a set <math>H_{n+1}</math>.
For each possible guess on the intermediate state <math>s_1</math> compute the following:

:; <math> \mathit{SubCipher}_1=\mathit{DEC}_{b_1}(k_{b_1},s_1) \qquad\forall k_{b_1}  \in K</math>
:: and for each match between this <math> \mathit{SubCipher}_1 </math> and the set <math> H_1 </math>, save <math> k_{b_1} </math> and <math> k_{f_1} </math> in a new set <math> T_1 </math>.

:; <math> \mathit{SubCipher}_2=\mathit{ENC}_{f_2}(k_{f_2},s_1) \qquad\forall k_{f_2}  \in K </math>{{Verify source|reason=No way to verify this edit: <nowiki>{{diff|Meet-in-the-middle attack|661031004|659749736}}</nowiki> |date=May 2015}}
:: and save each <math> \mathit{SubCipher}_2 </math> together with corresponding <math> k_{f_2} </math> in a set <math> H_2</math>.
: For each possible guess on an intermediate state <math> s_2 </math> compute the following:
:* <math> \mathit{SubCipher}_2=\mathit{DEC}_{b_2}(k_{b_2},s_2) \qquad\forall k_{b_2}  \in K </math>
:*: and for each match between this <math> \mathit{SubCipher}_2 </math> and the set <math> H_2 </math>, check also whether 
:*: it matches with <math> T_1 </math> and then save the combination of sub-keys together in a new set <math> T_2 </math>.
:* For each possible guess on an intermediate state <math> s_n </math> compute the following:
{{Ordered list|list_style=padding-left: 3em; |list_style_type=lower-alpha
|<math> \mathit{SubCipher}_n=\mathit{DEC}_{b_n}(k_{b_n},s_n) \qquad\forall k_{b_n} \in K </math> and for each match between this <math> \mathit{SubCipher}_n </math> and the set <math>H_n</math>, check also whether it matches with <math> T_{n-1} </math>, save <math> k_{b_n} </math> and <math> k_{f_n} </math> in a new set <math> T_n </math>.
|<math> \mathit{SubCipher}_{n+1}=\mathit{ENC}_{f_n+1}(k_{f_n+1},s_n) \qquad\forall k_{f_{n+1}} \in K</math> and for each match between this <math>\mathit{SubCipher}_{n+1}</math> and the set <math>H_{n+1}</math>, check also 
whether it matches with <math>T_n</math>. If this is the case then:"
}}
Use the found combination of sub-keys <math>(k_{f_1},k_{b_1},k_{f_2},k_{b_2}, ... ,k_{f_{n+1}},k_{b_{n+1}})</math>  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<sub>j</sub>'' is done for each guess on the previous ''s''<sub>''j''-1</sub>. 
This make up an element of exponential complexity to overall time complexity of this MD-MITM attack.

=== 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: