Meet-in-the-middle attack: Difference between revisions
imported>Sandy Harris |
imported>Sandy Harris No edit summary |
||
| Line 4: | Line 4: | ||
A naive version of this attack requires huge amounts of memory to store the intermediate values, but there has been considerable work on variants that reduce the memory requirement, often by trading off some speed. See for example <ref>cite paper | A naive version of this attack requires huge amounts of memory to store the intermediate values, but there has been considerable work on variants that reduce the memory requirement, often by trading off some speed. See for example <ref>cite paper | ||
| author=Paul van Oorschot and Michael Wiener | |author=Paul van Oorschot and Michael Wiener | ||
|title=Improving Implementable Meet-in-the-Middle Attacks by Orders of Magnitude | |title=Improving Implementable Meet-in-the-Middle Attacks by Orders of Magnitude | ||
|date=1996 | |date=1996 | ||
|url=http://link.springer.de/link/service/series/0558/bibs/1109/11090229.htm}} | |url=http://link.springer.de/link/service/series/0558/bibs/1109/11090229.htm}} | ||
Revision as of 13:04, 8 August 2008
An attack against a cryptosystem based on looking for a match between intermediate values which may be calculated from either end of the system.
This why triple DES rather than just double DES is used. Suppose you use DES twice expecting to obtain the security of a 112-bit key by combining two 56-bit DES keys. This fails, assuming the attacker can obtain or guess one block of plaintext for which he has the matching ciphertext. He runs a number of decryptions with possible 2nd-half keys, stores results in a table, then runs encryptions using possible first-half keys checking each output to see if it matches the table. On average, his total cost is 257 encrypt/decrypt operations. Against triple DES, a similar attack is possible but not practical; the cost is 2112.
A naive version of this attack requires huge amounts of memory to store the intermediate values, but there has been considerable work on variants that reduce the memory requirement, often by trading off some speed. See for example [1]
References
- ↑ cite paper |author=Paul van Oorschot and Michael Wiener |title=Improving Implementable Meet-in-the-Middle Attacks by Orders of Magnitude |date=1996 |url=http://link.springer.de/link/service/series/0558/bibs/1109/11090229.htm}}