3.2.6 What is triple-DES?
For some time it has been common practice to protect information with triple-DES instead of DES. This means that the input data is, in effect, encrypted three times. There are a variety of ways of doing this; the ANSI X9.52 standard (see Question 5.3.1) defines triple-DES encryption with keys k1, k2, k3 as
C = Ek3(Dk2(Ek1(M))),
where Ek and Dk denote DES encryption and DES decryption, respectively, with the key k. This mode of encryption is sometimes referred to as DES-EDE. Another variant is DES-EEE, which consists of three consecutive encryptions. There are three keying options defined in ANSI X9.52 for DES-EDE:
- The three keys k1, k2 and k3 are independent.
- k1 and k2 are independent, but k1 = k3.
- k1 = k2 = k3.
The third option makes triple-DES backward compatible with DES.
The use of double and triple encryption does not always provide the additional security that might be expected. For example, consider the following meet-in-the-middle attack on double encryption [DH77]. We have a symmetric block cipher with key size n; let Ek(P) denote the encryption of the message P using the key k. Double encryption with two different keys gives a total key size of 2n. However, suppose that we are capable of storing Ek(P) for all keys k and a given plaintext P, and suppose further that we are given a ciphertext C such that C = Ek2(Ek1(P)) for some secret keys k1 and k2. For each key l, there is exactly one key k such that Dl(C) = Ek(P). In particular, there are exactly 2n possible keys yielding the pair (P,C), and those keys can be found in approximately O(2n) steps. With the capability of storing only 2p < 2n keys, we may modify this algorithm and find all possible keys in O(22n-p) steps.
Another example is given in [KSW96], where triple EDE encryption with three different keys is considered. Let K = (ka, kb, kc) and K¢ = (ka ÅD, kb, kc) be two secret keys, where D is a known constant and Å denotes XOR. Suppose that we are given a ciphertext C and the corresponding decryptions P and P¢ of C with the keys K and K¢, respectively. Since P¢ = Dka ÅD(Eka(P)), we can determine ka (or all possible candidates for ka) in O(2n) steps, where n is the key size. Using an attack similar to the one described above, we may determine the rest of the key (that is, kb and kc) in another O(2n) steps.
Attacks on two-key triple-DES have been proposed by Merkle and Hellman [MH81] and Van Oorschot and Wiener [VW91], but the data requirements of these attacks make them impractical. Further information on triple-DES can be obtained from various sources [Bih95] [KR96].