Why we don't use double DES? What is the 'meet in the middle' attack?
DES (Data Encryption Standard) is a symmetric block cipher with key size of 64 bits. However, effective key size is 56 bits because 8 bits out of the original 64 bits are used for parity checking. It is important to keep this in mind as an exhaustive (brute force) attack on the DES standard would require 256 attempts (or 2^55 if we consider that there’s a 50% chance of finding the key halfway through computing the entire key length).
Double DES encrypts plaintext twice by two different keys of 56 bits in the following manner:
P -> E(K1,P) -> X-> E(K2,X) = C OR [alternatively C=EK2(EK1(P))]
Arbitrary length plaintext data is divided into fixed length block of 64 bits (P) and encrypted with key (K1 – 56 bits in length) the resulting output (X) is encrypted with a different key (K2 - 56 bits in length) which gives cipher text output (C – 56 bit output). During this process the X (56 bit intermediary output) which is the result of first round of encryption / decryption is the weakness of double DES.
Decryption of double DES works in the following manner:
C -> (DK2,C) -> X -> (DK1, X) = P[alternatively P = DK2(DK1(C))]
During the process of encryption and decryption the value of X will always remain the same. Meet-in-the-middle attack targets this intermediary output of X. For, an adversary with access to plaintext and resulting cipher text can compute X from both sides with computation requirement of 2^56 (from encryption side) + 2^56 (from decryption side) = 2^57 - which is double computing strength required to brute force double DES. Hence practical strength of the cipher reduces from effective key length of2^112 bits to 2^57 bits for an exhaustive attack.
The adversary will first encrypt the (known) plaintext with all the possible keys to get the cipher text (X from the above protocol working example). In second stage the adversary will decrypt resultant (known) cipher text with (all) possible keys and compare the output with interim cipher text (X) to find a match. There may be multiple key-pair (K1 and K2) matches with X. Hence, attacker needs more than one set of (known) plaintext and (known) resultant cipher text which he can use to eliminated multiple matches and determine the correct key-pair (K1 and K2) and hence the correct key.
Thus, meet-in-the-middle attack reduced the computational required from key-length 2^112 to 2^57 which is twice (2^56+2^56) the time required to crack original DES algorithm. It is important to note that meet-in-the-middle attack isn’t specific to double DES. It is feasible on any cipher running a double encrypt.
Triple DES and improvement over original DES.
Triple DES (3DES / 3DEA) uses 3 keys of 64-bits each, with effective key length of 56 bits (8 bits are used for parity checking). 3DES uses block size of 64-bits.
There are 3 keying modes of 3DES:
1.Three independent keys: Wherein none of the keys are explicitly similar: K1≠K2, K2≠K3, K3≠K1. This is also known as 3TDEA.
2.Two independent keys: Wherein K1 and K2 are explicitly different but K1 and K3 are similar. K1≠K2, K2≠K3, K3=K1. This is known as 2TDEA.
3.All keys are the same. K1 = K2 = K3. This key mode when used with EDE mode of 3DES is in essence – DES.
There are two different operating modes of 3DES:
1.EDE mode: Which functions as encrypt, decrypt, encrypt with K1, K2, K3 respectively.
This mode can be denoted as: C = EK1(DK2(EK3(P))). This is the predominantly used mode as it provides for backward compatibility with original DES standard when used with Key option 2. Using key option 3 with EDE mode is in-fact original DES standard.
2.EEE mode: Wherein plaintext is encrypted 3 times using 3 keys. This is represented as: C = EK1(EK2(EK3(P)))
Breaking 3DES
1.Using key option 2 in EEE and EDE mode:
This mode uses 3 keys such that K1≠K2, K2≠K3, K3=K1. EDE mode is not vulnerable to “meet-in-the-middle” attack. An attacker will need to compute 2 independent keys of 56 bit strength giving security of 2^112. However, there is known plaintext attack (by Merkle and Hellman) [3] chosen plaintext attack (by Paul C. van Oorschot and Michael J. Wiener) [3] on 2TDEA. NIST has classified effective strength to 280. [4]
2.Using key option 1 in EEE[2] mode:
Independent keys of 56 bits effective strength are used. However, EEE mode is susceptible to meet-in-the-middle attack, reducing the computation required from three independent keys with effective key strength of 2^168 bits to exhaustive search of ≈2^112.
To conclude, meet-in-the-middle does not completely work on 3TDEA due to three different rounds of encryption which do reduce the key strength to ≈2^112 bits. In case of 2TDEA which is not vulnerable to meet-in-the-middle attack but vulnerable to known plaintext and chosen plaintext attack the effective strength of the cipher is 280. [4] In any case, 3DES (3TDEA and 2TDEA) is used with keying option 1 (all keys are explicitly independent) or key option 2 (keys K1 and K2 are explicitly independent and K1=K3) either in EDE or EEE mode the computation required to carry out an exhaustive (brute force) search is always greater than in DES (256 maximum) or 2DES (257 due to meet-in-the-middle attack). Hence, 3TDEA or 2TDEA provide better security than double DES and / or DES.
