Added to Favorites

Related Searches

The Meet-in-the-middle attack is a 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 Diffie and Hellman in 1977. When trying to improve the security of a block cipher, one might get the idea to simply use two independent keys to encrypt the data twice. Naively, one might think that this would square the security of the double-encryption scheme. Certainly, an exhaustive search of all possible combination of keys would take $2^\{2n\}$ attempts if each key is n bits long, compared to the $2^n$ attempts required for a single key.

Diffie and Hellman, however, devised a time-memory tradeoff that could break the scheme in only double the time to break the single-encryption scheme. 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,

- $$

,where E is the encryption function (cipher), and K

The attacker can then compute E_{K}(P) for all possible keys K and store the results in memory. Afterwards he can decrypt the ciphertext by computing D_{K}(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_{K}(P) set is stored in an in-memory lookup table, then each D_{K}(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 it with a second test-set of plaintext and ciphertext. If the keysize is n, this attack uses only $2^\{n+1\}$ encryptions (and $O(2^n)$ space) in contrast to the naive attack, which needs $2^\{2n\}$ encryptions (but only $O(1)$ space).

- Birthday attack
- Man in the middle attack — an unrelated attack with a similar, confusable name.
- Triple DES

- W. Diffie and M. E. Hellman "Exhaustive Cryptanalysis of the NBS Data Encryption Standard".
*Computer*10 (6): 74–84.

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Friday October 03, 2008 at 02:18:23 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Friday October 03, 2008 at 02:18:23 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2015 Dictionary.com, LLC. All rights reserved.