Meet-in-the-middle attack
|
|
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.
It was first developed as an attack on an attempted expansion of a block cipher by Merkle and Hellman in 1981. 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 double the security of the double-encryption scheme.
Merkle 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,
- <math>
C=E_{K_2}(E_{K_1}(P))
<math>,
where 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 compute DK(C) for each K and compare with the table in memory. If he gets a match it is likely that he has discovered the two keys and he can verify it with a second set of plaintext and ciphertext. If the keysize is n, this attack uses only 2n+1 encryptions in contrast to the naive attack, which needs 22 n encryptions.