Applied Cryptography, Second Edition: Protocols, Algorthms, and Source Code in C (cloth)
(Publisher: John Wiley & Sons, Inc.)
Author(s): Bruce Schneier
ISBN: 0471128457
Publication Date: 01/01/96

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].

K1 and K2 alternate to prevent the meet-in-the-middle attack previously described. If C = EK2(EK1(EK1(P))), then a cryptanalyst could precompute EK1(EK1(P))) for every possible K1 and then proceed with the attack. It only requires 2n + 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 2n - 1 steps using 2n blocks of memory [1075].

For each possible K2, decrypt 0 and store the result in memory. Then, decrypt 0 with each possible K1 to get P. Triple-encrypt P to get C, and then decrypt C with K1. If that decryption is a decryption of 0 with a K2 (stored in memory), the K1 K2 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 2n time and memory, and 2m 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 K1, the second intermediate value, b, when the first intermediate value is a, using known plaintext:
b = DK1(C)

where C is the resulting ciphertext from a known plaintext.
(3)  Look up in the table, for each possible K2, elements with a matching second intermediate value, b:
b = EK2(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 2n + m/p time and p memory. For DES, this is 2120/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 = EK3(DK2(EK1(P)))
P = DK1(EK2(DK3(C)))

The best time-memory trade-off attack takes 22n steps and requires 2n 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: X1 and X2:

K1 = EX1(DX2(EX1(T1)))
K2 = EX1(DX2(EX1(T2)))
K3 = EX1(DX2(EX1(T3)))

T1, T2, and T3 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.
Ci = EK3(SiCi - 1); Si = DK2(TiSi - 1); Ti = EK1(PiTi - 1)
Pi = Ti - 1DK1(Ti); Ti = Si - 1EK2(Si); Si = Ci - 1DK3(Ci)

C0, S0, and T0 are IVs.
Outer-CBC: Triple-encrypt the entire file in CBC mode (see Figure 15.1b). This requires one IV.
Ci = EK3(DK2(EK1(PiCi - 1)))
Pi = Ci - 1DK1(EK2(DK3(Ci)))

[an error occurred while processing this directive]