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

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