Meet-in-the-middle attack: Difference between revisions
imported>Sandy Harris (add a refeence, rewrite some exlanation) |
imported>Sandy Harris No edit summary |
||
| Line 10: | Line 10: | ||
| pages=74–84 | | pages=74–84 | ||
| doi=10.1109/C-M.1977.217750 | | doi=10.1109/C-M.1977.217750 | ||
}}</ref>. | }}</ref>. It has been improved since then; see for example <ref>{{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}} | |||
</ref> | |||
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. You do indeed obtain that if the attacker tries a [[brute force attack]] searching all possible combinations of keys. However, attackers cannot be expected to co-operate. | 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. You do indeed obtain that if the attacker tries a [[brute force attack]] searching all possible combinations of keys. However, attackers cannot be expected to co-operate. | ||
Assuming the attacker can obtain or guess one block of plaintext for which he has the matching ciphertext, the meet-in-the-middle attack is a much better strategy for him. He runs a number of decryptions of the known ciphertext with possible 2nd-half keys, stores results in a table, then runs encryptions of the known plaintext using possible first-half keys and checking each output to see if it matches the table. On average, his total cost is 2<sup>57</sup> encrypt/decrypt operations. Against triple DES, a similar attack is possible but not practical; the cost is 2<sup>112</sup>. | Assuming the attacker can obtain or guess one block of plaintext for which he has the matching ciphertext, the meet-in-the-middle attack is a much better strategy for him. He runs a number of decryptions of the known ciphertext with possible 2nd-half keys, stores results in a table, then runs encryptions of the known plaintext using possible first-half keys and checking each output to see if it matches the table. On average, his total cost is 2<sup>57</sup> encrypt/decrypt operations. Against triple DES, a similar attack is possible but not practical; the cost is 2<sup>112</sup>. | ||
==References== | ==References== | ||
{{reflist|2}} | {{reflist|2}} | ||
Revision as of 17:50, 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.
The attack was first developed by Diffie and Hellman[1]. It has been improved since then; see for example [2]
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. You do indeed obtain that if the attacker tries a brute force attack searching all possible combinations of keys. However, attackers cannot be expected to co-operate.
Assuming the attacker can obtain or guess one block of plaintext for which he has the matching ciphertext, the meet-in-the-middle attack is a much better strategy for him. He runs a number of decryptions of the known ciphertext with possible 2nd-half keys, stores results in a table, then runs encryptions of the known plaintext using possible first-half keys and 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.
References
- ↑ W. Diffie and M. E. Hellman (June 1977). "Exhaustive Cryptanalysis of the NBS Data Encryption Standard". Computer 10 (6): 74–84. DOI:10.1109/C-M.1977.217750. Research Blogging.
- ↑ Paul van Oorschot and Michael Wiener (1996). Improving Implementable Meet-in-the-Middle Attacks by Orders of Magnitude.