Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Meet-in-the-middle attack
(section)
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
== Meet-in-the-middle (1D-MITM) == Assume someone wants to attack an encryption scheme with the following characteristics for a given plaintext ''P'' and ciphertext ''C'': :<math>\begin{align} C &= \mathit{ENC}_{k_2}(\mathit{ENC}_{k_1}(P)) \\ P &= \mathit{DEC}_{k_1}(\mathit{DEC}_{k_2}(C)) \\ \end{align}</math> where ''ENC'' is the encryption function, ''DEC'' the decryption function defined as ''ENC''<sup>−1</sup> (inverse mapping) and ''k''<sub>1</sub> and ''k''<sub>2</sub> are two keys. The naive approach at brute-forcing this encryption scheme is to decrypt the ciphertext with every possible ''k''<sub>2</sub>, and decrypt each of the intermediate outputs with every possible ''k''<sub>1</sub>, for a total of 2<sup>|''k''<sub>1</sub>|</sup> × 2<sup>|''k''<sub>2</sub>|</sup> (or 2<sup>|''k''<sub>1</sub>|+|''k''<sub>2</sub>|</sup>) operations. The meet-in-the-middle attack uses a more efficient approach. By decrypting ''C'' with ''k<sub>2</sub>'', one obtains the following equivalence: :<math>\begin{align} C &= \mathit{ENC}_{k_2}(\mathit{ENC}_{k_1}(P)) \\ \mathit{DEC}_{k_2}(C) &= \mathit{DEC}_{k_2}(\mathit{ENC}_{k_2}[\mathit{ENC}_{k_1}(P)]) \\ \mathit{DEC}_{k_2}(C) &= \mathit{ENC}_{k_1}(P) \\ \end{align}</math> The attacker can compute ''ENC''<sub>''k''<sub>1</sub></sub>(''P'') for all values of ''k''<sub>1</sub> and ''DEC''<sub>''k''<sub>2</sub></sub>(''C'') for all possible values of ''k''<sub>2</sub>, for a total of 2<sup>|''k''<sub>1</sub>|</sup> + 2<sup>|''k''<sub>2</sub>|</sup> (or 2<sup>|''k''<sub>1</sub>|+1</sup>, if ''k''<sub>1</sub> and ''k''<sub>2</sub> have the same size) operations. If the result from any of the ''ENC''<sub>''k''<sub>1</sub></sub>(''P'') operations matches a result from the ''DEC''<sub>''k''<sub>2</sub></sub>(''C'') operations, the pair of ''k''<sub>1</sub> and ''k''<sub>2</sub> is possibly the correct key. This potentially-correct key is called a ''candidate key''. The attacker can determine which candidate key is correct by testing it with a second test-set 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<sup>57</sup> operations and 2<sup>56</sup> space, making it only a small improvement over DES.<ref name="ZhuGuang2011" /> Triple DES uses a "triple length" (168-bit) key and is also vulnerable to a meet-in-the-middle attack in 2<sup>56</sup> space and 2<sup>112</sup> operations, but is considered secure due to the size of its keyspace.<ref name=":0">{{cite journal|last=Moore|first=Stephane|title=Meet-in-the-Middle Attacks|date=November 16, 2010|pages=2|url=http://stephanemoore.com/pdf/meetinthemiddle.pdf}}</ref><ref name=":1">{{Cite book |last=Blondeau |first=Céline |title=CS-E4320 Cryptography and Data Security |chapter=Lecture 3: Block Ciphers |access-date=2018-02-22 |chapter-url=https://mycourses.aalto.fi/pluginfile.php/548524/mod_resource/content/1/lecture03.pdf |archive-url=https://web.archive.org/web/20180223050616/https://mycourses.aalto.fi/pluginfile.php/548524/mod_resource/content/1/lecture03.pdf |archive-date=2018-02-23 |url-status=dead}}</ref> [[File:1D MITMNEW.png|thumb|upright=1.5|An illustration of 1D-MITM attack]] === MITM algorithm === Compute the following: *<math>\mathit{SubCipher}_1=\mathit{ENC}_{f_1}(k_{f_1},P),\; \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}_1=\mathit{DEC}_{b_1}(k_{b_1},C),\; \forall k_{b_1} \in K </math>: *: and compare each new <math>\mathit{SubCipher}_1 </math> with the set A When a match is found, keep <math>k_{f_1},k_{b_1}</math> as candidate key-pair in a table ''T''. Test pairs in ''T'' on a new pair of {{tmath|(P,C)}} to confirm validity. If the key-pair does not work on this new pair, do MITM again on a new pair of {{tmath|(P,C)}}. === MITM complexity === If the keysize is ''k'', this attack uses only 2<sup>''k''+1</sup> encryptions (and decryptions) and ''O''(2<sup>''k''</sup>) memory to store the results of the forward computations in a [[lookup table]], in contrast to the naive attack, which needs 2<sup>2·''k''</sup> encryptions but ''O''(1) space.
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)