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 k₁ by E(m,k₁), then double encryption might be written as E(E(m,k₁),k₂). One argument for the effort required to mount an exhaustive search is that if each key is k bits long and k₁ and k₂ are independent, then the best brute-force search for the keys used in double encryption requires 2^2k 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 2^k table entries, where a table entry consists of a key value and an intermediate data value, and 2^k+1 operations, where an operation is encryption under the particular cipher.

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,k₁),k₂),k₁), where D(,k₂) denotes decryption under key k₂. When k₁=k₂, this mode of triple encryption reduces to the single encryption E(m,k₁). 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 2^k chosen plaintexts, 2^k words of memory, and about 2^k+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 2¹²⁰/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,k₁),k₂),k₃), where backward compatibility is provided by putting k₃=k₂ or k₁=k₂.

Three-key triple encryption is still vulnerable to a meet-in-the-middle attack requiring 2^2k words of memory and about 2^k+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 k₁, k₂, and k₃, there would be a fourth key k₄, such that E(D(E(m,k₁),k₂),k₃)=E(m,k₄). 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.

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(ms₁, k₁)s₂, where k₁ is the usual secret DES key and s₁ and s₂ 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 2¹²⁰/n operations with n known plaintexts; to attack DES-XEX3, 2¹²¹ 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 2⁶¹ chosen plaintexts for differential and 2⁶⁰ 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,k₁)s₁,k₂), where k₁ and k₂ are independent DES keys and s₁ 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,k₁),k₂),k₃),k₂),k₁) would be among the strongest key sequences against meet-in-the-middle attacks. Backward compatibility with triple-DES is provided by putting k₂=k₃, and backward compatibility with single-DES is provided by putting k₁=k₂=k₃. 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 2⁴⁷ chosen plaintexts, and the best linear cryptanalytic attack requires 2⁴³ known plaintexts. In fact, in an experiment lasting 50 days, 12 workstations were used to recover the key used for the DES encryption of 2⁴³ 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.