This is sometimes called encrypt-decrypt-encrypt (EDE) mode [55]. If the block algorithm has an n-bit key, then this scheme has a 2n-bit key. The curious encrypt-decrypt-encrypt pattern was designed by IBM to preserve compatibility with conventional implementations of the algorithm: Setting the two keys equal to each other is identical to encrypting once with the key. There is no security inherent in the encrypt-decrypt-encrypt pattern, but this mode has been adopted to improve the DES algorithm in the X9.17 and ISO 8732 standards [55,761].

K₁ and K₂ alternate to prevent the meet-in-the-middle attack previously described. If C = E_K2(E_K1(E_K1(P))), then a cryptanalyst could precompute E_K1(E_K1(P))) for every possible K₁ and then proceed with the attack. It only requires 2^{n + 2} encryptions.

Triple encryption with two keys is not susceptible to the same meet-in-the-middle attack described earlier. But Merkle and Hellman developed another time-memory trade-off that could break this technique in 2^{n - 1} steps using 2ⁿ blocks of memory [1075].

For each possible K₂, decrypt 0 and store the result in memory. Then, decrypt 0 with each possible K₁ to get P. Triple-encrypt P to get C, and then decrypt C with K₁. If that decryption is a decryption of 0 with a K₂ (stored in memory), the K₁ K₂ pair is a possible candidate. Check if it is right. If it’s not, keep looking.

This is a chosen-plaintext attack, requiring an enormous amount of chosen plaintext to mount. It requires 2ⁿ time and memory, and 2^m chosen plaintexts. It is not very practical, but it is a weakness.

Paul van Oorschot and Michael Wiener converted this to a known-plaintext attack, requiring p known plaintexts. This example assumes EDE mode.

(1)  Guess the first intermediate value, a.

(2)  Tabulate, for each possible K₁, the second intermediate value, b, when the first intermediate value is a, using known plaintext:

b = D_K1(C)

where C is the resulting ciphertext from a known plaintext.

(3)  Look up in the table, for each possible K₂, elements with a matching second intermediate value, b:

b = E_K2(a)

(4)  The probability of success is p/m, where p is the number of known plaintexts and m is the block size. If there is no match, try another a and start again.

The attack requires 2^{n + m}/p time and p memory. For DES, this is 2¹²⁰/p [1558]. For p greater than 256, this attack is faster than exhaustive search.

Triple Encryption with Three Keys

If you are going to use triple encryption, I recommend three different keys. The key length is longer, but key storage is usually not a problem. Bits are cheap.

C = E_K3(D_K2(E_K1(P)))

P = D_K1(E_K2(D_K3(C)))

The best time-memory trade-off attack takes 2²ⁿ steps and requires 2ⁿ blocks of memory; it’s a meet-in-the-middle attack [1075]. Triple encryption, with three independent keys, is as secure as one might naïvely expect double encryption to be.

Triple Encryption with Minimum Key (TEMK)

There is a secure way of using triple encryption with two keys that prevents the previous attack, called Triple Encryption with Minimum Key (TEMK) [858]. The trick is to derive three keys from two: X₁ and X₂:

K₁ = E_X1(D_X2(E_X1(T₁)))

K₂ = E_X1(D_X2(E_X1(T₂)))

K₃ = E_X1(D_X2(E_X1(T₃)))

T₁, T₂, and T₃ are constants, which do not have to be secret. This is a special construction that guarantees that for any particular pair of keys, the best attack is a known-plaintext attack.

Triple-Encryption Modes

It’s not enough to just specify triple encryption; there are several ways to do it. The decision of which to use affects both security and efficiency.

Here are two possible triple-encryption modes:

Inner-CBC: Encrypt the entire file in CBC mode three different times (see Figure 15.1a). This requires three different IVs.

C_i = E_K3(S_i ⊕ C_{i - 1}); S_i = D_K2(T_i ⊕ S_{i - 1}); T_i = E_K1(P_i ⊕ T_{i - 1})

P_i = T_{i - 1} ⊕ D_K1(T_i); T_i = S_{i - 1} ⊕ E_K2(S_i); S_i = C_{i - 1} ⊕ D_K3(C_i)

C₀, S₀, and T₀ are IVs.

Outer-CBC: Triple-encrypt the entire file in CBC mode (see Figure 15.1b). This requires one IV.

C_i = E_K3(D_K2(E_K1(P_i ⊕ C_{i - 1})))

P_i = C_{i - 1} ⊕ D_K1(E_K2(D_K3(C_i)))