Meet-in-the-middle attack: Difference between revisions
imported>Howard C. Berkowitz (See talk page. Too sudden a jump from a basic definition to detailed cryptographic examples, assuming knowledge of cryptanalytic strategies) |
imported>Sandy Harris No edit summary |
||
| Line 1: | Line 1: | ||
A meet-in-the middle attack is an attack on a [[block cipher]] in which the attacker can calculate possible values of the same intermediate variable (the middle) in two independent ways, starting either from the input of the cipher ([[plaintex]]) or from the output ( [[ciphertext]]). The attacker calculates some possible values each way and compares the results. It is a [[known plaintext]] attack; the attacker must get or guess one block of plaintext for which he has the matching ciphertext. | |||
The attack was first developed by [[Whitfield Diffie|Diffie]] and [[Martin Hellman|Hellman]]<ref>{{cite journal | The attack was first developed by [[Whitfield Diffie|Diffie]] and [[Martin Hellman|Hellman]]<ref>{{cite journal | ||
| Line 14: | Line 14: | ||
|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}} | ||
</ref> | </ref> | ||
Where it is applicable, this attack is devastating. The number of encryptions that must be tried is, in general, the square root of the number required for a [[brute force]] attack. For example, if brute force takes 2<sup>128</sup> steps and the cipher is vulnerable to meet-in-the-middle, then m-i-t-m will need only 2<sup>64</sup> steps. However, the attack is rarely applicable; it only works if the two calculations of the middle variable are independent. In most ciphers, they are not; the first and second halves of a block cipher use closely related keys, two groups of [[round key]]s derived from the same basic key by the same [[key schedule]]. | |||
One case where the attack does apply is the construction where the same cipher is applied twice successively with different keys in an attempt to gain greater security. In fact, he gain is negligible because the construction is vulnerable to a meet-in-the-middle attack. | |||
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. | ||
Revision as of 07:29, 9 August 2008
A meet-in-the middle attack is an attack on a block cipher in which the attacker can calculate possible values of the same intermediate variable (the middle) in two independent ways, starting either from the input of the cipher (plaintex) or from the output ( ciphertext). The attacker calculates some possible values each way and compares the results. It is a known plaintext attack; the attacker must get or guess one block of plaintext for which he has the matching ciphertext.
The attack was first developed by Diffie and Hellman[1]. It has been improved since then; see for example [2]
Where it is applicable, this attack is devastating. The number of encryptions that must be tried is, in general, the square root of the number required for a brute force attack. For example, if brute force takes 2128 steps and the cipher is vulnerable to meet-in-the-middle, then m-i-t-m will need only 264 steps. However, the attack is rarely applicable; it only works if the two calculations of the middle variable are independent. In most ciphers, they are not; the first and second halves of a block cipher use closely related keys, two groups of round keys derived from the same basic key by the same key schedule.
One case where the attack does apply is the construction where the same cipher is applied twice successively with different keys in an attempt to gain greater security. In fact, he gain is negligible because the construction is vulnerable to a meet-in-the-middle attack.
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.