# ALGORITHM ALLEY

## Multiple Encryption: Weighing Security and Performance

### Burton S. Kaliski, Jr. and M.J.B. Robshaw

*Burt and Matt are scientists at RSA
Laboratories. They can be contacted at [email protected] and [email protected],
respectively.*

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.

### Double Encryption

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*_{1} by *E*(*m*,*k*_{1}), then double
encryption might be written as
*E*(*E*(*m*,*k*_{1}),*k*_{2}). One
argument for the effort required to mount an exhaustive search is that if each
key is *k* bits long and *k*_{1} and *k*_{2} are
independent, then the best brute-force search for the keys used in double
encryption requires 2^{2}* ^{k}* 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.

To mount this "meet-in-the-middle" attack, you encrypt some known
plaintext *m* under every possible key *k*_{1} and store a
table with 2* ^{k}* entries, where each resulting intermediate block
is indexed by the choice of first key. Then you use every possible key

*k*

_{2}to decrypt the ciphertext; if there is a match in the table, then you have a guess (

*k*

_{1}

^{*},

*k*

_{2}

^{*}) 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
2* ^{k}*, 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 2

^{2}

*operations we might have expected.*

^{k}

### Triple Encryption

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*_{1}),*k*_{2}),*k*_{1}),
where *D*(** ^{}**,

*k*

_{2}) denotes decryption under key

*k*

_{2}. When

*k*

_{1}=

*k*

_{2}, this mode of triple encryption reduces to the single encryption

*E*(

*m*,

*k*

_{1}). 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

*words of memory, and about 2*

^{k}*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.*

^{k+1}

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^{120}/*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*_{1}),*k*_{2}),*k*_{3}),
where backward compatibility is provided by putting
*k*_{3}=*k*_{2} or
*k*_{1}=*k*_{2}.

Three-key triple encryption is still vulnerable to a meet-in-the-middle attack
requiring 2^{2}* ^{k}* words of memory and about
2

*operations. However, for any cipher with a reasonably sized key, this brute-force attack will not be a substantial threat.*

^{k+1}

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*_{1}, *k*_{2}, and
*k*_{3}, there would be a fourth key *k*_{4}, such that
*E*(*D*(*E*(*m*,*k*_{1}),*k*_{2}),*k*_{3})=*E*(*m*,*k*_{4}).
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").

### Modes of Triple Encryption

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.

### Mixing Ciphers

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.

### Less-Computation-Intensive Alternatives

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*(*m**s*_{1},
*k*_{1})*s*_{2}, where *k*_{1} is the
usual secret DES key and *s*_{1} and *s*_{2} 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^{120}/*n* operations with *n* known plaintexts; to attack
DES-XEX3, 2^{121} 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^{61} chosen plaintexts for
differential and 2^{60} 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*_{1})*s*_{1},*k*_{2}),
where *k*_{1} and *k*_{2} are independent DES keys and
*s*_{1} is a secret value--stronger or weaker than DES-XEX?

### Final Thoughts

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*_{1}),*k*_{2}),*k*_{3}),*k*_{2}),*k*_{1})
would be among the strongest key sequences against meet-in-the-middle attacks.
Backward compatibility with triple-DES is provided by putting
*k*_{2}=*k*_{3}, and backward compatibility with
single-DES is provided by putting
*k*_{1}=*k*_{2}=*k*_{3}. 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^{47} chosen plaintexts, and the best
linear cryptanalytic attack requires 2^{43} 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^{43} 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.