Meet-in-the-middle attack: Difference between revisions
imported>Howard C. Berkowitz (This needs more explanation of the transition from a basic model to the arguments of triple vs. double DES. See talk page) |
imported>Howard C. Berkowitz (See talk page. Too sudden a jump from a basic definition to detailed cryptographic examples, assuming knowledge of cryptanalytic strategies) |
||
| Line 1: | Line 1: | ||
If Bob and Alice desired to communicate securely, exchanging credentials, they would be subject to a '''meet-in-the-middle''' attack if Melvin, the [[miscreant]], purported to be Alice to Bob, and to be Bob to Alice. Bob and Alice would, unless additional security measures were present, give confidential information to Melvin. More formally, a '''meet-in-the-middle attack'' against a [[cryptosystem]] involves a third party's successfully forging information that would be expected from the legitimate communications peer. | If Bob and Alice desired to communicate securely, exchanging credentials, they would be subject to a '''meet-in-the-middle''' attack if Melvin, the [[miscreant]], purported to be Alice to Bob, and to be Bob to Alice. Bob and Alice would, unless additional security measures were present, give confidential information to Melvin. More formally, a '''meet-in-the-middle attack''' against a [[cryptosystem]] involves a third party's successfully forging information that would be expected from the legitimate communications peer. | ||
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 | ||
Revision as of 00:43, 9 August 2008
If Bob and Alice desired to communicate securely, exchanging credentials, they would be subject to a meet-in-the-middle attack if Melvin, the miscreant, purported to be Alice to Bob, and to be Bob to Alice. Bob and Alice would, unless additional security measures were present, give confidential information to Melvin. More formally, a meet-in-the-middle attack against a cryptosystem involves a third party's successfully forging information that would be expected from the legitimate communications peer.
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.