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

== A general example of 2D-MITM ==

This is a general description of how 2D-MITM is mounted on a block cipher encryption.

In two-dimensional MITM (2D-MITM) the method is to reach 2 intermediate states inside the multiple encryption of the plaintext. See below figure:

[[File:2D MITMNEW.png|thumb|upright=2|An illustration of 2D-MITM attack]]

=== 2D-MITM algorithm ===
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 A
:; <math> \mathit{SubCipher}_2=\mathit{DEC}_{b_2}(k_{b_2},C) \qquad \forall k_{b_2}  \in K </math> 
:: and save each <math> \mathit{SubCipher}_2 </math> together with corresponding <math> k_{b_2} </math> in a set B.

For each possible guess on an intermediate state ''s'' between <math>\mathit{SubCipher}_1</math> and <math>\mathit{SubCipher}_2</math> 
compute the following:

*  <math> \mathit{SubCipher}_1=\mathit{DEC}_{b_1}(k_{b_1},s) \qquad \forall k_{b_1}  \in K </math> 
*: and for each match between this <math>\mathit{SubCipher}_1</math> and the set A, save   <math>k_{b_1}</math> and <math>k_{f_1}</math> in a new set T.
* <math> \mathit{SubCipher}_2=\mathit{ENC}_{f_2}(k_{f_2},s)  \qquad \forall k_{f_2}  \in K </math> 
*: and for each match between this <math>\mathit{SubCipher}_2</math> and the set B, check also whether it matches with T for 
*: 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})</math> on another pair of plaintext/ciphertext to verify the correctness of the key.

=== 2D-MITM complexity ===
Time complexity of this attack without brute force, is 
: <math>2^{|k_{f_1}|} + 2^{|k_{b_2}|} + 2^{|s|} \cdot \left(2^{|k_{b_1}|} + 2^{|k_{f_2}|}\right)</math>
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 [[#MD-MITM complexity|subsection on complexity for MD-MITM]].