Difference between revisions 4918747 and 5957521 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 first function is the same as the inverse image of the other through the second function—quite literally meeting in the middle of the composed function.

It was first developed as an attack on an attempted expansion of a [[block cipher]] by [[Whitfield Diffie|Diffie]] and [[Martin Hellman|Hellman]] in 1977. When trying to improve the security of a block cipher, one might get the idea to simply use two independent [[Key (cryptography))|keys]]s to encrypt the data twice and think that this would square the security of the double-encryption scheme. Certainly, an exhaustive search of all possible combination of keys would take <math>2^{2n}</math> attempts if each key is n bits long, compared to the <math>2^n</math> attempts required for a single key. However, Diffie and Hellman, discovered a time-memory tradeoff that could break the scheme in only double the time to break the single-encryption scheme.<ref>{{cite journa(contracted; show full)

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

==
OtherRelated pages==
*[[Birthday attack]]

==References==
<references/>

⏎
⏎
{{Math-stub}}

[[Category:Cryptography]]