Meet-in-the-middle attack: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Sandy Harris
No edit summary
imported>Sandy Harris
(add a refeence, rewrite some exlanation)
Line 1: Line 1:
An attack against a [[cryptosystem]] based on looking for a match between intermediate values which may be calculated from either end of the system.  
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 of he 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>.
The attack was first developed by [[Whitfield Diffie|Diffie]] and [[Martin Hellman|Hellman]]<ref>{{cite journal
| author=W. Diffie and M. E. Hellman
| date=June 1977
| title=Exhaustive Cryptanalysis of the NBS Data Encryption Standard
| journal=Computer
| volume=10
| issue=6
| pages=74–84
| doi=10.1109/C-M.1977.217750
}}</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.
 
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>.


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|title=Improving Implementable Meet-in-the-Middle Attacks by Orders of Magnitude
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|title=Improving Implementable Meet-in-the-Middle Attacks by Orders of Magnitude

Revision as of 14:00, 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].

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.

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 [2]

References

  1. ↑ 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.
  2. ↑ Paul van Oorschot and Michael Wiener (1996). Improving Implementable Meet-in-the-Middle Attacks by Orders of Magnitude.
Retrieved from "https://citizendium.org/wiki/index.php?title=Meet-in-the-middle_attack&oldid=518257"