Meet-in-the-middle attack
Encyclopedia
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 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.
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
attempts if each key is n bits long, compared to the 
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.
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
attack which, like the birthday attack
Birthday attack
A birthday attack is a type of cryptographic attack that exploits the mathematics behind the birthday problem in probability theory. This attack can be used to abuse communication between two or more parties...
, makes use of a space-time tradeoff
Space-time tradeoff
In computer science, a space–time or time–memory tradeoff is a situation where the memory use can be reduced at the cost of slower program execution...
. 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 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.
History
It was first developed as an attack on an attempted expansion of a block cipherBlock cipher
In cryptography, a block cipher is a symmetric key cipher operating on fixed-length groups of bits, called blocks, with an unvarying transformation. A block cipher encryption algorithm might take a 128-bit block of plaintext as input, and output a corresponding 128-bit block of ciphertext...
by Diffie
Whitfield Diffie
Bailey Whitfield 'Whit' Diffie is an American cryptographer and one of the pioneers of public-key cryptography.Diffie and Martin Hellman's paper New Directions in Cryptography was published in 1976...
and Hellman
Martin Hellman
Martin Edward Hellman is an American cryptologist, and is best known for his invention of public key cryptography in cooperation with Whitfield Diffie and Ralph Merkle...
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
attempts if each key is n bits long, compared to the 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.
Example
Assume the attacker knows a set of plaintext and ciphertext: P and C. That is,-
,
where E is the encryption function (cipher), and K1 and K2 are the two keys.
The attacker can then compute EK(P) for all possible keys K and store the results in memory. Afterwards he can decrypt the ciphertext by computing DK(C) for each K. Any matches between these two resulting sets are likely to reveal the correct keys. (To speed up the comparison, the EK(P) set is stored in an in-memory lookup tableLookup tableIn computer science, a lookup table is a data structure, usually an array or associative array, often used to replace a runtime computation with a simpler array indexing operation. The savings in terms of processing time can be significant, since retrieving a value from memory is often faster than...
, then each DK(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
encryptions (and 
Big O notationIn mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
space) in contrast to the naive attack, which needs
encryptions (but only 
space).