Author(s): Bruce Schneier

ISBN: 0471128457

Publication Date: 01/01/96

Previous | Table of Contents | Next |

This is sometimes called **encrypt-decrypt-encrypt (EDE)** mode [55]. If the block algorithm has an *n*-bit key, then this scheme has a 2*n*-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*_{1} and *K*_{2} 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*_{1} 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^{n} blocks of memory [1075].

For each possible *K*_{2}, decrypt 0 and store the result in memory. Then, decrypt 0 with each possible *K*_{1} to get *P*. Triple-encrypt *P* to get *C*, and then decrypt *C* with *K*_{1}. If that decryption is a decryption of 0 with a *K*_{2} (stored in memory), the *K*_{1} *K*_{2} 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^{n} 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*_{1}, 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*_{2}, 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^{120}*/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^{2n} steps and requires 2^{n} 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*_{1} and *X*_{2}:

*K*_{1}=*E*_{X1}(*D*_{X2}(*E*_{X1}(*T*_{1})))*K*_{2}=*E*_{X1}(*D*_{X2}(*E*_{X1}(*T*_{2})))*K*_{3}=*E*_{X1}(*D*_{X2}(*E*_{X1}(*T*_{3})))

*T*_{1}, *T*_{2}, and *T*_{3} 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*_{0},*S*_{0}, and*T*_{0}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})))

Previous | Table of Contents | Next |