Meet-in-the-middle attack
The Meet-in-the-middle attack is a cryptographic attack on an attempted expansion of a block cipher. It was first developed 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 of 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 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.
See also
Triple DES
|
