 Meetinthemiddle attack

Not to be confused with maninthemiddle attack.
The meetinthemiddle attack is a cryptographic attack which, like the birthday attack, makes use of a spacetime 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 meetinthemiddle attack attempts to find a value in each of the range and domain 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.
Contents
History
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 doubleencryption 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 timememory tradeoff that could break the scheme in only double the time to break the singleencryption scheme.^{[1]} The attack works by encrypting from one end and decrypting from the other end, thus meeting in the middle.
Example
Assume the attacker knows a set of plaintext and ciphertext: P and C. That is,
 ,
where E is the encryption function (cipher), and K_{1} and K_{2} are the two keys.
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 inmemory 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 with a second testset 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).
See also
References
 ^ Diffie, Whitfield; Hellman, Martin E. (June 1977). "Exhaustive Cryptanalysis of the NBS Data Encryption Standard". Computer 10 (6): 74–84. doi:10.1109/CM.1977.217750. http://www.computer.org/portal/web/csdl/doi/10.1109/CM.1977.217750.
Categories: Cryptographic attacks
Wikimedia Foundation. 2010.
Look at other dictionaries:
Meet in the Middle — This article is about the song. For the cryptographic attack, see Meet in the middle attack. Meet in the Middle Single by Diamond Rio … Wikipedia
Maninthemiddle attack — Not to be confused with Meet in the middle attack. In cryptography, the man in the middle attack (often abbreviated MITM), bucket brigade attack, or sometimes Janus attack, is a form of active eavesdropping in which the attacker makes independent … Wikipedia
THE MIDDLE AGES — … Encyclopedia of Judaism
The Heart Attack — Infobox Television episode Title = The Heart Attack Series = Seinfeld Caption = Elaine and Jerry visit George in the hospital. Season = 2 Episode = 13 Airdate = April 25 1991 Production = Writer = Larry Charles Director = Tom Cherones Guests =… … Wikipedia
List of Malcolm in the Middle episodes — Malcolm in the Middle ran for seven seasons from 2000 to 2006 with 151 episodes produced. Contents 1 Series overview 2 Season 1: 2000 3 Season 2: 2000–2001 4 … Wikipedia
Kingdom of Hungary in the Middle Ages — Kingdom of Hungary Magyar Királyság (hu) Regnum Hungariae (la) ← … Wikipedia
Infantry in the Middle Ages — at the Battle of Aljubarrota, 1385] Infantry in the Middle Ages were soldiers who fought on foot during the Middle Ages. They were frequently part of a specialised division such as the pikemen, crossbowmen and longbowmen. Throughout much of the… … Wikipedia
Meet Me Halfway — For Meet Me Half Way by Kenny Loggins, see Meet Me Half Way. Meet Me Halfway Single by The Black Eyed Peas from the album The E.N.D … Wikipedia
The United States of America — The United States of America † Catholic Encyclopedia ► The United States of America BOUNDARIES AND AREA On the east the boundary is formed by the St. Croix River and an arbitrary line to the St. John, and on the north by the… … Catholic encyclopedia
The Amanda Show — Format Sketch comedy Variety show Created by Dan Schneider Starring Amanda Bynes … Wikipedia