Section 6.1. Multiple Encryption and Triple DES

[Page 175 (continued)]

6.1. Multiple Encryption and Triple DES

Given the potential vulnerability of DES to a brute-force attack, there has been considerable interest in finding an alternative. One approach is to design a completely new algorithm, of which AES is a prime example. Another alternative, which would preserve the existing investment in software and equipment, is to use multiple encryption with DES and multiple keys. We begin by examining the simplest example of this second alternative. We then look at the widely accepted triple DES (3DES) approach.

[Page 176]

Double DES

The simplest form of multiple encryption has two encryption stages and two keys (Figure 6.1a). Given a plaintext P and two encryption keys K₁ and K₂, ciphertext C is generated as

C = E(K₂, E(K₁, P))

Figure 6.1. Multiple Encryption

Decryption requires that the keys be applied in reverse order:

P = D(K₁, D(K₂, C))

For DES, this scheme apparently involves a key length of 56 x 2 = 112 bits, of resulting in a dramatic increase in cryptographic strength. But we need to examine the algorithm more closely.

[Page 177]

Reduction to a Single Stage

Suppose it were true for DES, for all 56-bit key values, that given any two keys K₁ and K₂, it would be possible to find a key K₃ such that

Equation 6-1

If this were the case, then double encryption, and indeed any number of stages of multiple encryption with DES, would be useless because the result would be equivalent to a single encryption with a single 56-bit key.

On the face of it, it does not appear that Equation (6.1) is likely to hold. Consider that encryption with DES is a mapping of 64-bit blocks to 64-bit blocks. In fact, the mapping can be viewed as a permutation. That is, if we consider all 2⁶⁴ possible input blocks, DES encryption with a specific key will map each block into a unique 64-bit block. Otherwise, if, say, two given input blocks mapped to the same output block, then decryption to recover the original plaintext would be impossible. With 2⁶⁴ possible inputs, how many different mappings are there that generate a permutation of the input blocks? The value is easily seen to be

On the other hand, DES defines one mapping for each different key, for a total number of mappings:

2⁵⁶>10¹⁷

Therefore, it is reasonable to assume that if DES is used twice with different keys, it will produce one of the many mappings that are not defined by a single application of DES. Although there was much supporting evidence for this assumption, it was not until 1992 that the assumption was proved [CAMP92].

Meet-in-the-Middle Attack

Thus, the use of double DES results in a mapping that is not equivalent to a single DES encryption. But there is a way to attack this scheme, one that does not depend on any particular property of DES but that will work against any block encryption cipher.

The algorithm, known as a meet-in-the-middle attack, was first described in [DIFF77]. It is based on the observation that, if we have

C = E(K₂, E(K₁, P))

then (see Figure 6.1a)

X = E(K₁, P) = D(K₂, P)

Given a known pair, (P, C), the attack proceeds as follows. First, encrypt P for all 2⁵⁶ possible values of K₁ Store these results in a table and then sort the table by the values of X. Next, decrypt C using all 2⁵⁶ possible values of K₂. As each decryption is produced, check the result against the table for a match. If a match occurs, then test the two resulting keys against a new known plaintext-ciphertext pair. If the two keys produce the correct ciphertext, accept them as the correct keys.

[Page 178]

For any given plaintext P, there are 2⁶⁴ possible ciphertext values that could be produced by double DES. Double DES uses, in effect, a 112-bit key, so that there are 2¹¹² possible keys. Therefore, on average, for a given plaintext P, the number of different 112-bit keys that will produce a given ciphertext C is 2¹¹²/2⁶⁴ = 2⁴⁸. Thus, the foregoing procedure will produce about 2⁴⁸ false alarms on the first (P, C) pair. A similar argument indicates that with an additional 64 bits of known plaintext and ciphertext, the false alarm rate is reduced to 2^48-64 = 2^-16 Put another way, if the meet-in-the-middle attack is performed on two blocks of known plaintext-ciphertext, the probability that the correct keys are determined is 1 2^-16. The result is that a known plaintext attack will succeed against double DES, which has a key size of 112 bits, with an effort on the order of 2⁵⁶, not much more than the 2⁵⁵ required for single DES.

Triple DES with Two Keys

An obvious counter to the meet-in-the-middle attack is to use three stages of encryption with three different keys. This raises the cost of the known-plaintext attack to 2¹¹², which is beyond what is practical now and far into the future. However, it has the drawback of requiring a key length of 56 x 3 = 168 bits, which may be somewhat unwieldy.

As an alternative, Tuchman proposed a triple encryption method that uses only two keys [TUCH79]. The function follows an encrypt-decrypt-encrypt (EDE) sequence (Figure 6.1b):

C = E(K₁, D(K₂, E(K₁, P)))

There is no cryptographic significance to the use of decryption for the second stage. Its only advantage is that it allows users of 3DES to decrypt data encrypted by users of the older single DES:

C = E(K₁, D(K₁, E(K₁, P))) = E(K₁, P)

3DES with two keys is a relatively popular alternative to DES and has been adopted for use in the key management standards ANS X9.17 and ISO 8732.^[1]

^[1] (ANS) American National Standard: Financial Institution Key Management (Wholesale). From its title, X9.17 appears to be a somewhat obscure standard. Yet a number of techniques specified in this standard have been adopted for use in other standards and applications, as we shall see throughout this book.

Currently, there are no practical cryptanalytic attacks on 3DES. Coppersmith [COPP94] notes that the cost of a brute-force key search on 3DES is on the order of 2¹¹² (5 x 10³³) and estimates that the cost of differential cryptanalysis suffers an exponential growth, compared to single DES, exceeding 10⁵².

It is worth looking at several proposed attacks on 3DES that, although not practical, give a flavor for the types of attacks that have been considered and that could form the basis for more successful future attacks.

[Page 179]

The first serious proposal came from Merkle and Hellman [MERK81]. Their plan involves finding plaintext values that produce a first intermediate value of A = 0 (Figure 6.1b) and then using the meet-in-the-middle attack to determine the two keys. The level of effort is 2⁵⁶, but the technique requires 2⁵⁶ chosen plaintext-ciphertext pairs, a number unlikely to be provided by the holder of the keys.

A known-plaintext attack is outlined in [VANO90]. This method is an improvement over the chosen-plaintext approach but requires more effort. The attack is based on the observation that if we know A and C (Figure 6.1b), then the problem reduces to that of an attack on double DES. Of course, the attacker does not know A, even if P and C are known, as long as the two keys are unknown. However, the attacker can choose a potential value of A and then try to find a known (P, C) pair that produces A. The attack proceeds as follows:

Obtain n (P, C) pairs. This is the known plaintext. Place these in a table (Table 1) sorted on the values of P (Figure 6.2b).

Figure 6.2. Known-Plaintext Attack on Triple DES
Pick an arbitrary value a for A, and create a second table (Figure 6.2c) with entries defined in the following fashion. For each of the 2⁵⁶ possible keys K₁ = i, calculate the plaintext value P_i that produces a:
P_i = D(i, a)
[Page 180]
For each P_i that matches an entry in Table 1, create an entry in Table 2 consisting of the K₁ value and the value of B that is produced for the (P, C) pair from Table 1, assuming that value of K₁:
B = D(i, C)
At the end of this step, sort Table 2 on the values of B.
We now have a number of candidate values of K₁ in Table 2 and are in a position to search for a value of K₂. For each of the 2⁵⁶ possible keys K₂ = j, calculate the second intermediate value for our chosen value of a:
B_j = D(j, a)
At each step, look up B_j in Table 2. If there is a match, then the corresponding key i from Table 2 plus this value of j are candidate values for the unknown keys (K₁, K₂). Why? Because we have found a pair of keys (i, j) that produce a known (P, C) pair (Figure 6.2a).
Test each candidate pair of keys (i, j) on a few other plaintext-ciphertext pairs. If a pair of keys produces the desired ciphertext, the task is complete. If no pair succeeds, repeat from step 1 with a new value of a.

For a given known (P, C), the probability of selecting the unique value of a that leads to success is 1/2⁶⁴. Thus, given n (P, C) pairs, the probability of success for a single selected value of a is n/2⁶⁴. A basic result from probability theory is that the expected number of draws required to draw one red ball out of a bin containing n red balls and N n green balls is (N + 1)/(n + 1) if the balls are not replaced. So the expected number of values of a that must be tried is, for large n,

Thus, the expected running time of the attack is on the order of

Triple DES with Three Keys

Although the attacks just described appear impractical, anyone using two-key 3DES may feel some concern. Thus, many researchers now feel that three-key 3DES is the preferred alternative (e.g., [KALI96a]). Three-key 3DES has an effective key length of 168 bits and is defined as follows:

C = E(K₃, D(K₂, E(K₁, P)))

Backward compatibility with DES is provided by putting K₃ = K₂ or K₁ = K₂.

A number of Internet-based applications have adopted three-key 3DES, including PGP and S/MIME, both discussed in Chapter 15.