DES: What is a meet-in-the-middle attack? For a moment suppose that the best att
ID: 3662798 • Letter: D
Question
DES: What is a meet-in-the-middle attack? For a moment suppose that the best attacks against DES were brute force, that is an attack of trying all possible keys to decrypt the message. Let DES ^Ki(M) denote encrypting message M with key Ki. What is the strength of a DES double encryption (that is, E= DES ^k2(DES ^ki(M)))? Now imagine a triple encryption of DES, E = DES ^k3(DES ^k2(DESKi(M))). How secure is that against a brute-force attack? How do the running times of double DES and triple DES compare with|DES?Explanation / Answer
Meet-in-the-middle is an optimized brute-force attack or technique used to reduce the brute force combinations to break ciphers which have two or more secret keys for multiple encryption using the same algorithm. The cipher can be defined as two algorithms one for encryption and another for decryption. In MIM attack brute force techniques is used on plaintext and ciphertext of a block cipher. It is called meet in the middle because the attacker launches the attack on both sides simultaneously and a successful attempt enables him to meet in the middle of the block cipher.
Double-DES is two successive DES instances, while Triple-DES is three successive DES instances. 2DES doesn't actually provide much security than DES. If we take a bunch of possible plain-texts and start trying to encode them and simultaneously take a bunch of encrypted values and start decrypting them, we only have to look for where they meet in the middle with the same value. Those intersections then reveal the key. While 3DES avoids this because of the middle step. A third operation is needed to tell if they met in the middle and thus we can't simply look for where the first and last operation produce the same value.
All these algorithms normally work on a fixed block size and thus take same time which is O(m) (for mode of operation) where m is message size. Triple DES need thrice computation power but it gets in O(m) too.
Regarding brute force attacks, 2DES is slightly more secure than DES because it uses double encryption but its not much secure against "meet in the middle" attack. 3DES is more secure both against "brute force" attack as well as "meet in the middle attacks".
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.