Multiple Encryption: Weighing Security and Performance
Burton S. Kaliski, Jr. and M.J.B. Robshaw
As time passes, encryption algorithms age and become vulnerable to new or previously infeasible attacks. In particular, interest is often paid to the size of the key used for encryption, since, in the absence of any other weaknesses, this is one way to compare the strength of ciphers. Key lengths once considered adequate are now vulnerable to adversaries with only modest resources.
While old, well-trusted ciphers approach the end of their useflife, new ciphers are continually being proposed. But new ciphers should be greeted with extreme caution and deep skepticism. They should be subjected to prolonged cryptanalysis (by people other than the designers) before they are considered safe for use by the community at large. Several ciphers are currently earning their credentials as part of this process; IDEA is perhaps the foremost among them (see "The IDEA Encryption Algorithm," by Bruce Schneier, DDJ, December 1993).
To span this period of uncertainty, you should try to use trusted ciphers in more secure ways. As a first step, it is natural to suppose that encrypting twice is better than encrypting once; that the more times you encrypt data which has already been encrypted (perhaps with a different cipher), the safer you must be.
For the most part, this might be true. However, you don't get something for nothing. More encryption means more work, and you need to know exactly how much extra security is gained from the additional work.
In this article, we will examine these issues, paying particular attention to repeated encryption with the same cipher. We will then consider some issues involved in the mixed use of different block ciphers.
Triple encryption (encrypting three times) is mentioned frequently. But whatever happened to double encryption? Destined to remain the perfect tutorial example, double encryption increases security so little that the extra effort cannot be justified.
With double encryption, the same block cipher is used twice with two different keys. If we denote block-cipher encryption of a message m under a key k1 by E(m,k1), then double encryption might be written as E(E(m,k1),k2). One argument for the effort required to mount an exhaustive search is that if each key is k bits long and k1 and k2 are independent, then the best brute-force search for the keys used in double encryption requires 22k operations.
But what if the opponent is willing to invest in memory? Very often, the time required to mount an attack is reduced by memory; hence the "time-memory" trade-off. In the case of double encryption, a brute-force attack requires 2k table entries, where a table entry consists of a key value and an intermediate data value, and 2k+1 operations, where an operation is encryption under the particular cipher.
To mount this "meet-in-the-middle" attack, you encrypt some known plaintext m under every possible key k1 and store a table with 2k entries, where each resulting intermediate block is indexed by the choice of first key. Then you use every possible key k2 to decrypt the ciphertext; if there is a match in the table, then you have a guess (k1*,k2*) for the pair of keys that were actually used. (Figure 1 shows this attack.) The cryptanalyst might need additional known-plaintext/ciphertext pairs to check that the guess is correct (depending on block and key size, there may well be false alarms).
While such an attack still seems to have large requirements--a table of size 2k, for instance--if the attacker can choose the plaintext, only one table must be compiled for all keys. (If the plaintext is only known rather than chosen, then the table needs to be prepared for that particular plaintext.) Thus, while encryption of each plaintext block requires twice as much work, the cryptanalyst with resources to invest in memory is only faced with twice the computational effort required for single encryption. This is certainly not the 22k operations we might have expected.
Unlike double encryption, triple encryption can provide the kind of security we want at a price we are willing to pay, and in several different ways.
In two-key triple encryption we can write the ciphertext equivalent of some plaintext m as E(D(E(m,k1),k2),k1), where D(,k2) denotes decryption under key k2. When k1=k2, this mode of triple encryption reduces to the single encryption E(m,k1). This useful property is referred to as "backward compatibility." For shorthand, let's call this version of triple encryption with two distinct keys "EDE2"; obvious changes will be made to this notation to accommodate other variants.
Two-key triple encryption is vulnerable to some forms of attack. While the attacks we will describe require large amounts of time and memory, they show that two-key triple encryption does not provide as much security as we might have hoped. Nevertheless, two-key triple encryption is used quite widely in banking; we are not suggesting any practical problem with two-key triple encryption, but there are benefits in using three keys.
In their paper "On the Security of Multiple Encryption" (Communications of the ACM, July 1981), R.C. Merkle and M.E. Hellman showed how two-key triple encryption is vulnerable to a chosen-plaintext attack that requires the encryption of 2k chosen plaintexts, 2k words of memory, and about 2k+1 operations. This is essentially the same work effort required to tackle double encryption, though the plaintext requirements have been vastly increased. Merkle and Hellman were the first to point out the essential impracticality of their own attack, but they referred to the attack as a "certificational weakness" in two-key triple encryption.
This somewhat prophetic view was later upheld. In the paper "A Known-plaintext Attack on Two-key Triple Encryption" (Advances in Cryptology: Eurocrypt '90, Springer-Verlag, 1991), P.C. van Oorschot and M.J. Wiener described a known-plaintext attack that requires 2120/n operations when given n known plaintext blocks, and memory requirements that grow linearly as n increases. While this attack may also be considered impractical, anyone using two-key triple encryption must consider it seriously.
Instead, it is recommended that three independent keys be used. Thus, we can write the ciphertext equivalent to some plaintext encrypted using three-key triple encryption as E(D(E(m,k1),k2),k3), where backward compatibility is provided by putting k3=k2 or k1=k2.
Three-key triple encryption is still vulnerable to a meet-in-the-middle attack requiring 22k words of memory and about 2k+1 operations. However, for any cipher with a reasonably sized key, this brute-force attack will not be a substantial threat.
All these brute-force attacks are applicable, at least to some degree, to any cipher. However, there are some technical issues to resolve in adapting the attack. These attacks were devised with DES in mind, and they make assumptions about key size compared to block size. The sizes can vary considerably between different ciphers.
Finally, one potential property of a block cipher that would jeopardize the security of triple and even higher multiples of encryption is the possibility that the underlying block cipher generates a "group." If so, then for each set of keys k1, k2, and k3, there would be a fourth key k4, such that E(D(E(m,k1),k2),k3)=E(m,k4). Clearly, this would be disastrous. Unfortunately, for most ciphers it's still unknown whether or not the cipher forms a group. DES, however, is not a group, and triple encryption is not vulnerable to attack in this way (see the accompanying text box, "The Data Encryption Standard").
So far, we have only considered the triple-encryption cipher as an "electronic code book," where each plaintext block is encrypted independently of the others. Previously, triple encryption has been used to encrypt valuable information such as other encryption keys (see American National Standard X9.17: Financial Institution Key Management, 1985), and this information can often be accommodated within a single block.
For longer messages, however, it is customary to "chain" the series of encryptions in a mode known as "cipher block chaining" (CBC). With single-encryption CBC, the previous ciphertext is XORed with the plaintext prior to block-cipher encryption.
With triple encryption, we can use one of two CBC modes (see Figure 2):
- Inner-CBC, where each individual component is used in CBC mode.
- Outer-CBC, where the three stages of encryption are considered a single unit and the ciphertext is fed back to the plaintext.
All triple-encryption modes obviously require more resources than single encryption: more hardware or more time. But it would be nice if, given sufficient hardware, the throughput were the same as for single encryption. (For software implementations, the different triple-encryption modes all take roughly the same amount of time.)
Throughput is the main performance distinction between the inner- and outer-CBC modes. In the inner-CBC modes, feedback is around one operation. Three chips, each implementing a single cipher operation, can be kept busy continually, each feeding back to itself, so the throughput is the same as for single encryption. (Latency, the amount of time it takes to process a particular block, is nevertheless three times longer than in single encryption.)
In outer-CBC, feedback is around all three operations. This means that even with three chips, the throughput is only one third that of single encryption; the first chip must wait until the other two are done to move on to the next block. Of course, the chip can process blocks from other messages during its idle time. By interleaving the processing of three messages, the chips can be kept busy all the time. This changes the encryption protocol at a higher level, but may be appropriate for some applications.
With three encryption chips then, inner-CBC is intrinsically more efficient than outer-CBC, unless three messages are interleaved for the latter.
It appears that inner-CBC offers more security than outer-CBC, since the values of the internal feedbacks are never revealed. In an EDE configuration the usual feedback around the middle decryption unit actually becomes a feedforward. This hinders meet-in-the-middle attacks, and inner-CBC appears to offer considerable security against brute-force attacks.
The use of three keys is obviously beneficial, and any additional operational overhead it incurs is insignificant. So, three-key inner-CBC EDE seems to be the mode of choice against brute-force attacks.
But in "Cryptanalysis of Multiple Modes of Operation," Advances in Cryptology: Asiacrypt '94 (Springer-Verlag, 1995), E. Biham showed that inner-CBC modes are vulnerable to a class of sophisticated attacks. The trouble is that the use of feedback around each unit in triple encryption allows controlled changes in the ciphertext to be propagated as changes to the internal and unseen data.
By controlling these changes in the ciphertext, powerful differential and linear cryptanalysis techniques can be used on individual components (see Differential Cryptanalysis of the Data Encryption Standard, by E. Biham and A. Shamir, Springer-Verlag, 1993). Depending on the exact form of triple encryption--two- or three-key, EDE, or EEE--different attacks can be mounted.
In essence, Biham has demonstrated that the use of feedback in the internals of an encipherment procedure is dangerous. It is better to use one substantial encryption transformation and to employ any feedback around its entirety, rather than to consider the encryption as a succession of small, and essentially less secure, transformations, each with its own feedback.
When using triple encryption with chaining, we recommend three-key, outer-CBC triple encryption with an EDE configuration for backward compatibility.
One frequent suggestion is to mix the use of different ciphers. Perhaps we should encrypt the plaintext with one cipher, the result with a second, incompatible cipher, and so on. This might well be the basis of a strong design, although the difficulty and cost of implementation must be considered, and potentially intricate solutions to backward compatibility must be provided.
Of course, this more-general question could have been the theme of this entire article; after all, multiple encryption with a single cipher is merely one restricted case where all the ciphers are the same. But more-practical issues have influenced our emphasis. Multiple encryption with the same cipher is standardized and widely used, whereas the use of different ciphers remains, at best, merely a proposal. In "Cascade Ciphers: The Importance of Being First," Proceeding of the IEEE Symposium on Information Theory, 1990, U.M. Maurer and J.L. Massey demonstrated that a cascade of ciphers, where the key used at each stage is chosen independently of the others, is at least as strong as its first component. This property is often casually referred to as "the importance of being first." When the chain of ciphers can be equivalently rewritten with any of the ciphers first (technically, the ciphers are said to "commute"), then the cascade is as strong as its strongest component.
Others have addressed related questions, and it seems reasonable to suppose that the successive use of different and incompatible ciphers can only provide additional protection against more-sophisticated methods of cryptanalysis. The basic brute-force and meet-in-the-middle attacks can always be mounted, whatever the cipher, in one way or another. (There are some technical issues to resolve when the key size either differs between the ciphers or becomes larger than the block size.) But there appears to be some reluctance in establishing a precedent; as yet, no one has offered a good choice of ciphers or basic results on the security of a particular mix.
As we add encryption operations to the chain of multiple encryptions, we increase the work required to encrypt a block of data by another factor. Is there some less-computation-intensive way to increase the security of our basic block cipher without resorting to multiple encryptions?
With regard to DES, there have been a few proposals that might easily be used on other block ciphers. In one variant, which we call "DES-SES" (see "Foiling an Exhaustive Key-search Attack," by F. Rubin, Cryptologia, April 1987), a secret substitution operation S is used on the plaintext before encryption using single DES. We'll focus on DES-XEX, another variant where an XOR is used both before and after single encryption with DES; hence the -XEX. Thus, the plaintext m would be encrypted as E(ms1, k1)s2, where k1 is the usual secret DES key and s1 and s2 are secret 64-bit quantities which may be the same (DES-XEX2) or different (DES-XEX3).
Against brute-force attacks, both DES-XEX2 and DES-XEX3 offer a marked improvement over single-encryption DES. The effort required to attack DES-XEX2 is 2120/n operations with n known plaintexts; to attack DES-XEX3, 2121 DES operations are required when three plaintext blocks are known.
The additional protection offered against differential and linear cryptanalysis is not as dramatic but still significant; DES-XEX2 or DES-XEX3 offer the same protection as DES with so-called independent subkeys. Such attacks, while impractical (they require more than 261 chosen plaintexts for differential and 260 known plaintexts for linear cryptanalysis; see Biham's "Cryptanalysis of Multiple Modes of Operation"), offer only a small improvement over the requirements for single-DES.
But DES-XEX is cheap--only an additional two XORs are required to encrypt each plaintext block. DES-XEX or similar variants may offer a very realistic balance between increased encryption effort and increased security.
As an exercise, we pose the following question: Is DES-EXE--that is, E(E(m,k1)s1,k2), where k1 and k2 are independent DES keys and s1 is a secret value--stronger or weaker than DES-XEX?
While there may be significant advantages in using several types of ciphers, the approach is essentially untried and has significant operational implications. Instead, it is most commonly proposed to use multiple iterations of the same cipher, often DES. In particular, three-key triple-DES in EDE mode is just starting to be widely accepted for the encryption of data streams.
The use of triple encryption raises an interesting question: Surely we need something stronger than triple encryption to transmit the keys used for triple encryption?
When considering triple-DES in a system, perhaps you should examine higher multiples of DES encryption. In quintuple-DES, if a three-key variant is used, then E(D(E(D(E(m,k1),k2),k3),k2),k1) would be among the strongest key sequences against meet-in-the-middle attacks. Backward compatibility with triple-DES is provided by putting k2=k3, and backward compatibility with single-DES is provided by putting k1=k2=k3. Of course, a five-key variant would have obvious additional advantages.
Whatever the future with DES, the issue of multiple encryption will have to be considered for the block cipher of the day. We now have a sufficient understanding of current cryptanalytic techniques to provide a fairly accurate estimate for the additional security provided in return for the increase in work effort and key size.
The Data-Encryption Standard
Designed in the early 1970s, the Data Encryption Standard (DES) is, in the 1990s, still arguably the world's most trusted block cipher, and with good reason. Its resistance to all published cryptanalytic attacks bears continuing testament to the exceptional quality of its design. In the absence of any new major cryptanalytic breakthrough, the declining security offered by DES is essentially a symptom of technological aging--as a basic, primitive building block, it can still be cryptographically useful.
DES is a block cipher that transforms plaintext blocks of 64 bits to 64 bits of ciphertext. The transformation is controlled by a 56-bit key. DES is an iterated cipher consisting of 16 rounds, each using a 48-bit subkey derived from the 56-bit key chosen by the user. Sometimes a variant of DES is described as using independent subkeys. In this case, the subkeys used in each of the 16 rounds are unrelated, rather than being derived from the same user-provided 56-bit quantity.
Apart from a potential halving of the search space gained by using the so-called complementation property (this results from the way the subkey is used in each round), no known shortcuts allow a reduction in the complexity of a brute-force attack. Compared to some more-recent variants, DES is remarkably resilient against sophisticated attacks such as differential and linear cryptanalysis. The best differential attack requires 247 chosen plaintexts, and the best linear cryptanalytic attack requires 243 known plaintexts. In fact, in an experiment lasting 50 days, 12 workstations were used to recover the key used for the DES encryption of 243 known plaintexts (see "The First Experimental Cryptanalysis of the Data Encryption," by M. Matsui, Advances in Cryptology: Crypto '94, Springer-Verlag, 1994). This attack is impractical, however; 40 of the 50 days were spent just encrypting the data.
More significantly, in a Crypto '93 Rump Session entitled "Efficient DES Key Search," M.J. Wiener estimated that for $1 million, a machine can be built which would search exhaustively for the key used in any DES encryption. It is estimated that this machine could find the correct key in an average time of 3.5 hours.
While DES is still practically secure to those without $1 million to invest, it is time to move to stronger methods of encryption, be they new ciphers or multiple iterations of an old favorite.
--B.S.K. & M.J.B.R.
Figure 1: Double encryption using two independent keys and a meet-in-the-middle attack.
Figure 2: Two different ways of implementing the CBC mode of triple encryption.