Section 6.1. Multiple Encryption and Triple DES
6.1. Multiple Encryption and Triple DESGiven 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. Double DESThe simplest form of multiple encryption has two encryption stages and two keys (Figure 6.1a). Given a plaintext P and two encryption keys K1 and K2, ciphertext C is generated as C = E(K2, E(K1, P)) Figure 6.1. Multiple Encryption Decryption requires that the keys be applied in reverse order: P = D(K1, D(K2, 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. Reduction to a Single StageSuppose it were true for DES, for all 56-bit key values, that given any two keys K1 and K2, it would be possible to find a key K3 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 264 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 264 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: 256>1017 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 AttackThus, 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(K2, E(K1, P)) then (see Figure 6.1a) X = E(K1, P) = D(K2, P) Given a known pair, (P, C), the attack proceeds as follows. First, encrypt P for all 256 possible values of K1 Store these results in a table and then sort the table by the values of X. Next, decrypt C using all 256 possible values of K2. 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. For any given plaintext P, there are 264 possible ciphertext values that could be produced by double DES. Double DES uses, in effect, a 112-bit key, so that there are 2112 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 2112/264 = 248. Thus, the foregoing procedure will produce about 248 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 248-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 256, not much more than the 255 required for single DES. Triple DES with Two KeysAn 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 2112, 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(K1, D(K2, E(K1, 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(K1, D(K1, E(K1, P))) = E(K1, 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]
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 2112 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. 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 256, but the technique requires 256 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:
For a given known (P, C), the probability of selecting the unique value of a that leads to success is 1/264. Thus, given n (P, C) pairs, the probability of success for a single selected value of a is n/264. 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 KeysAlthough 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(K3, D(K2, E(K1, P))) Backward compatibility with DES is provided by putting K3 = K2 or K1 = K2. A number of Internet-based applications have adopted three-key 3DES, including PGP and S/MIME, both discussed in Chapter 15. |
(5 x 1033) and estimates that the cost of differential cryptanalysis suffers an exponential growth, compared to single DES, exceeding 1052.
EAN: 2147483647
Pages: 209