Difference between revisions 8061769 and 8336621 on simplewiki

{{complex|date=April 2012}}
The '''Meet-in-the-middle attack''' is a [[cryptography|cryptographic]] attack which, like the [[birthday attack]], makes use of a [[space-time tradeoff]]. While the birthday attack attempts to find two values in the domain of a function that map to the same value in its range, the meet-in-the-middle attack attempts to find a value in each of the ranges and domains of the composition of two functions such that the forward mapping of one through the f(contracted; show full)| volume=10
| issue=6
| pages=74–84
| doi=10.1109/C-M.1977.217750
| s2cid=2412454
}}</ref> The attack works by encrypting from one end and decrypting from the other end, thus meeting in the middle.

Assume the attacker knows a set of 
[[plaintext]] and [[ciphertext]]: ''P'' and ''C''. That is,
: <math>
  C=E_{K_2}(E_{K_1}(P))
  </math>,
where E is the encryption function (cipher), and ''K''<sub>1</sub> and ''K''<sub>2</sub> are the two keys.

The attacker can then compute ''E<sub>K</sub>''(''P'') for all possible keys ''K'' and store the results in memory. Afterwards he can decrypt the ciphertext by computing ''D<sub>K</sub>''(''C'') for each ''K''. Any matches between these two resulting sets are likely to reveal the correct keys. (To speed up the comparison, the ''E<sub>K</sub>''(''P'') set is stored in an in-memory [[lookup table]], then each ''D<sub>K</sub>''(''C'') can be matched against the values in the lookup table to find the candidate keys.)

Once the matches are discovered, they can be verified with a second test-set of plaintext and ciphertext. If the keysize is ''n'', this attack uses only <math>2^{n+1}</math> encryptions (and <math>O(2^n)</math> space) in contrast to the naive attack, which needs <math>2^{2n}</math> encryptions (but only <math>O(1)</math> space).

==Related pages==
*[[Birthday attack]]

==References==
<references/>


{{Math-stub}}

[[Category:Cryptography]]