A brief report by RSA Laboratories on the security and performance of
several triple-DES modes is attached for consideration at the next PEM
working group. I apologize for not giving the participants more time
before the meeting to consider the document, and remain available via
email or telephone to answer any questions.
This document is intended initially for study by the PEM working group
and subscribers to <pem-dev(_at_)tis(_dot_)com>; please do not distribute
further. A full report intended for general distribution is in
preparation.
-- Burt Kaliski
RSA Laboratories
======================================================================
Triple-DES: A Brief Report
Burt Kaliski
RSA Laboratories
October 29, 1993
DRAFT --- NOT FOR GENERAL DISTRIBUTIOM
1. Introduction
With the increasing concerns over the security of the Data Encryption
Standard (DES) [1,2], many are considering alternative algorithms.
Given the even greater concerns over the security of many of those
algorithms (for instance, differential cryptanalysis [3], one of the
most powerful attacks known against DES, has been even more effective
against alternatives), the ``triple-DES'' mode involving three DES
operations is receiving renewed interest.
Originally intended for encrypting keys (e.g., in the ANSI X9.17
standard [4]), triple-DES is generally considered to have twice the
effective key size of DES, 112 bits of security instead of 56 bits.
(Double-DES has been shown to have the same security as DES against
brute-force attacks.) But most published analysis of triple-DES has
focused on single-block encryption. Its security in modes intended
for multiple-block encryption is an open issue. Indeed, there are as
many modes of triple-DES as there are ways to interconnect the three
DES operations. The security and performance of the modes varies
considerably.
This brief report summarizes the security and performance of several
modes of triple-DES; full reports are in preparation. This report is
intended initially for study by the Internet's Privacy-Enhanced Mail
working group. Questions and comments can be sent to <burt(_at_)rsa(_dot_)com>.
2. Definitions
DES is a secret-key cryptosystem with a 56-bit key. It is a ``block
cipher'' in that each key defines an ``electronic code book'' mapping
plaintext blocks to ciphertext blocks; in DES, a block is 64 bits
long. DES applies an initial, fixed permutation on the input block,
then 16 key-dependent ``rounds,'' then a final permutation that is
the inverse of the initial one.
Applied to multiple-block messages, DES has several standard modes
[5], including electronic code book where each block is encrypted
independently of the others, and cipher block chaining (CBC) where a
plaintext block is exclusive-ored with the previous ciphertext block
before encryption. In CBC mode, the ciphertext block ``previous'' to
the first plaintext block is the ``initialization vector.''
This note considers the following modes of triple-DES, named
following examples in a recent note [6]:
DES-EEE3, with three DES encryptions and three different keys
DES-EDE3, like DES-EEE3 except that the second operation is a
decryption
DES-EEE2 and DES-EDE2, like the foregoing, but with only two
keys, where the first and third DES operations are with the
same key
DES-EEE3-CBC, DES-EDE3-CBC, DES-EEE2-CBC and DES-EDE2-CBC, the
previous four modes with cipher block chaining; there
is one feedback value, and one initialization vector
DES-CBC-EEE3, single-DES in cipher block chaining mode, repeated
three times with three different keys; there are thus three
feedback values and three initialization vector
DES-CBC-EDE3, like DES-CBC-EEE3 except that the second operation
is a cipher block chaining mode decryption; there are only
two initialization vectors, not three, as one is shared
between the first and second operations, and hence only
two initialization vectors
DES-CBC-EEE2 and DES-CBC-EDE2, the foregoing with only two keys
In this note, the modes with cipher block chaining outside the three
DES operations are called ``outer CBC''; those with the chaining on
each DES operation are called ``inner CBC.'' The ``three-key'' modes
have three different keys; the ``two-key'' modes are those where the
first and third DES operations are with the same key.
For most of the cipher block chaining modes, security doesn't depend
on whether the initialization vectors are secret, so they are
generally made public. However, it does seem to make a difference in
DES-CBC-EDE3 and DES-CBC-EDE2, as described below.
Most of the modes are backward compatible with single-DES. For
instance, DES-EEE3 is the same as a single-DES when the first two
keys are the same ``weak'' (self-inverse) key, such as the key with
all zero bits; DES-EDE3 is the same when the first two keys are the
same. But DES-EEE2 and the associated CBC modes do not seem to have a
compatible mode, nor does DES-CBC-EEE2.
3. Performance
All the triple-DES modes obviously require more resources than
single-DES: more hardware, or more time. But it would be nice if,
given sufficient hardware, the throughput---the number of blocks the
hardware can process per second---were the same as for single-DES.
Throughput is the main performance distinction between the inner-CBC
and outer-CBC modes. In the ``inner CBC'' modes, feedback is around
one DES operation. Three DES chips can be kept busy all the time,
each feeding back to itself, so the throughput is the same as for
single-DES. (Latency---the amount of time it takes to process a
block---is nevertheless three times longer as in single-DES.)
In the outer-CBC modes, however, feedback is around all three DES
operations. This means even with three DES chips, the throughput is
only one third as much as for single-DES, because the first DES 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 DES chips, then, inner-CBC is intrinsically more efficient
than outer-CBC, unless three messages are interleaved for the latter.
If there is only one DES chip, then the modes will probably all take
about the same time, assuming the chip has enough functionality and
registers to encrypt with two of three different keys and
exclusive-or arbitrary values. Ideally, the chip should process one
block at a time through all three DES operations, or otherwise I/O
overhead could be prohibitive. If the chip has limited functionality
(e.g., it does not allow arbitrary exclusive-oring), then some modes
may be more efficient than others.
In software, the triple-DES modes all take about the same time. The
two-key modes have one fewer key setup, which may be significant for
short messages; the reduction in key setups may also save some
memory. The additional feedback values and exclusive-ors in the
inner-CBC modes are not all that significant, compared to the DES
rounds. In all the modes, the initial permutation in one DES
operation cancels the final permutation in the previous one, thus
saving four of the six permutations. This is especially helpful in
software, where the each permutation may cost as much as a few DES
rounds.
4. Security
Ordinary single-DES can be broken with about 2^56 DES operations,
given a known plaintext block. Double-DES, as shown by Diffie and
Hellman [7], can be broken with about the same number of operations,
and storage for 2^56 blocks, under an attack called
``meet-in-the-middle.'' For this reason, triple-DES is the usual mode
for strengthening DES, rather than double-DES.
A meet-in-the-middle attack can break three-key triple-DES with about
2^112 operations and storage for 2^56 blocks, following techniques
similar to those for double-DES. For two-key triple-DES, there are
even better attacks.
Merkle and Hellman have shown a chosen-plaintext attack that breaks
two-key triple-DES with about 2^56 DES operations, given 2^56 chosen
plaintext blocks [8]. Their attack, while impractical, at least
demonstrates a ``certificational weakness'' in two-key triple-DES.
The attack is not known to extend to three-key triple-DES.
The most effective known-plaintext attack on two-key triple-DES is
due to van Oorschot and Wiener [9]. Their attack breaks triple-DES
with about (2^120)/n DES operations, given n known plaintext blocks.
If n is greater than 256, then the attack is faster than exhaustive
search. No such attack is known for three-key triple DES.
The attacks just described all apply to electronic code book mode,
where each block is encrypted independently of the others. Since a
plaintext/ciphertext pair for the outer-CBC modes directly gives a
pair for electronic code book mode, the outer-CBC modes are
vulnerable to the same known-plaintext attacks. The outer-CBC modes
are not vulnerable to Merkle and Hellman's chosen-plaintext attack,
however, since cipher block chaining randomizes the resulting
electronic code book mode pairs.
Whether the initialization vector is secret or public doesn't really
matter for the outer-CBC modes, since all the other external feedback
values are visible. The only case where it might make a difference is
when the first plaintext block is known; then, if the initialization
vector is secret, the attacker would not know the
plaintext/ciphertext pair for the electronic code book mode attacks.
The security of the inner-CBC modes appears to be quite different
than that of the outer-CBC modes, and to some extent it depends on
whether the initialization vectors are known.
For instance, in the CBC-EDE modes, the feedback value between the
first and second DES operations is hidden; it cannot be recovered by
decrypting ciphertext blocks. (This is because it's a ``feed
forward'' for the second DES operation.) The only way to get it is by
starting at the beginning of the message and working forward,
assuming the initialization vectors are known. If they are unknown,
then the attacker must guess the feedback value.
Meet-in-the-middle attacks don't seem to work that well in any of the
inner-CBC modes, since there is usually an unknown internal feedback
value on the plaintext side. It is usually easy to get to some middle
point from the ciphertext side, since the feedback values are
uncovered in the process. For example, the ciphertext blocks
themselves are typically feedback values. But it is hard to get to
the same middle point from the plaintext side, because the feedback
values are not uncovered in the process.
In what follows, it is assumed that all ciphertext blocks are known,
some but not all plaintext blocks are known, and that the first
plaintext block is unknown. (If the first plaintext block and the
initialization vectors are all known, then the modes are basically
the same as outer-CBC as far as security.)
The security of the four inner-CBC modes seems to break down as
follows (details are left to the full report):
DES-CBC-EEE3:
- meet-in-the-middle attack
- three known plaintext blocks, at least two adjacent
- about 2^120 DES operations
- storage for about 2^112 blocks
DES-CBC-EDE3, initialization vectors known:
- meet-in-the-middle attack
- three known plaintext blocks, at least two adjacent
- about 2^120 or (2^112)*t DES operations, whichever is
larger, where t is the distance in blocks from the
beginning of the message to the known plaintext blocks
- storage for about 2^112 blocks
DES-CBC-EDE3, initialization vectors unknown:
- meet-in-the-middle attack
- three known plaintext blocks, at least two adjacent
- about 2^176 DES operations
- storage for about 2^56 blocks
DES-CBC-EEE2:
- exhaustive search
- two known plaintext blocks
- about 2^112 DES operations
- minimal storage
DES-CBC-EDE2, initialization vectors known:
- exhaustive search
- two known plaintext blocks
- about (2^112)*t DES operations, where t is the distance in
blocks from the beginning of the message to the known
plaintext blocks
- minimal storage
DES-CBC-EDE2, initialization vectors unknown:
- van Oorschot-Wiener-like attack
- two known plaintext blocks
- about 2^120 DES operations
- storage for 2^56 blocks
All the attacks described involve ``brute-force'' where internal
details of the algorithm are not considered. For DES, there are other
attacks that do consider the details. For instance, DES has a
``complementation'' property that can halve the number of operations
in some cases, although chosen plaintext blocks are usually required.
Also, with one exception DES's internal functions are linear (i.e.,
exclusive-OR), a feature that Biham and Shamir's differential
cryptanalysis [2] and Matsui's linear cryptanalysis [10] exploit.
The effectiveness of differential and linear cryptanalysis on the
various modes of triple-DES is an interesting question for further
study. On single-DES, differential cryptanalysis is faster than
exhaustive search, though it requires about 2^47 chosen plaintext
blocks. Linear cryptanalysis is also faster, and it requires the same
number of known plaintext blocks. Both types of cryptanalysis rely on
relationships whose probability decreases exponentially with the
number of rounds. After 48 rounds, the probability may well be so
small that the relationships are no longer of any benefit. On the
other hand, the triple-DES modes may introduce new relationships not
present in single-DES whose probability is much higher, something
that further study will determine.
5. Conclusions
The inner-CBC modes of triple-DES appear to be at least as secure as
the outer-CBC modes, and have intrinsically better performance, so
they are probably the modes of choice, if one wants to encrypt
messages with three DES operations. The inner-CBC modes have
additional initialization vectors, but in most applications the extra
overhead is unlikely to be a concern.
Three-key triple-DES is considerably more secure than two-key
triple-DES, especially in terms of the storage required by attacks.
There may be slight difference in software due to key setup, but the
performance is basically the same. The overhead due to the additional
key is again unlikely to be an issue to most applications.
Security of the CBC-EDE modes seems slightly better than that of the
CBC-EEE modes, though both are quite good; keeping the initialization
vectors secret provides additional security in the CBC-EDE modes.
Based on these considerations, the ``preferred'' mode of triple-DES
is DES-CBC-EDE3. It has good performance in general, and it appears
to have the greatest security. It is also backward compatible with
ordinary DES-CBC. The initialization vectors may either be secret or
public; in either case, the security is much higher than single-DES.
Of course, without further study, the recommendation remains
tentative; there may well be tradeoffs between the modes other than
those considered here.
If the reason for considering triple-DES is that it involves a well
studied algorithm, then perhaps one can broaden the discussion to
other ways to strengthen DES, without the performance impact of three
DES operations.
One mode that seems to be stronger than single-DES, but which costs
almost the same, is so-called ``DES-XEX'' where blocks are
exclusive-ored with a secret value before and after encryption. The
secret values may be the same (DES-XEX2) or different (DES-XEX3).
Preliminary analysis suggests the following security:
- for the two-key mode, about 2^120/n DES operations given n
known plaintext blocks, under an attack like van Oorschot and
Wiener's
- for the three-key mode, about 2^120 DES operations given three
known plaintext blocks, under a modified exhaustive search that
cancels some of the exclusive-ors
Its security against differential and linear cryptanalysis is
currently being studied.
Rubin describes another mode that costs almost the same as DES, which
one might call ``DES-SES,'' the ``S'' standing for substitution [11].
The mode applies a secret byte-wise substitution before and after
encryption. How it compares with the other modes, and its security
against differential and linear cryptanalysis, remains to be studied.
Interestingly, internal changes to DES, such as making each round's
48-bit subkey, which is ordinarily derived from the 56-bit DES key,
an independent secret, have generally been rendered ineffective by
differential cryptanalysis. The external changes seem much more
promising.
Triple-DES is receiving renewed interest for good reason, and its
security in modes intended for encrypting messages has been an open
issue. This note has summarized the security and performance of
several of those modes, recommending modes for message encryption;
further study on the topic is encouraged.
Acknowledgments
This work was prompted by the Internet's Privacy-Enhanced Mail
working group. I have benefited from various discussions on the
<pem-dev(_at_)tis(_dot_)com> mailing list. For instance, Carl Ellison gave a
performance analysis for the inner-CBC and outer-CBC modes; Steve
Crocker suggested the interleaving of messages; and Tom Jones
addressed I/O overhead. Matt Robshaw has also given helpful
suggestions. I also thank God (Col. 3:17).
References
[1] National Institute of Standards and Technology (NIST). FIPS
Publication 46-1: Data Encryption Standard. January 22, 1988.
[2] M.J. Wiener. Efficient DES key search. Presented at CRYPTO '93
rump session (Santa Barbara, CA, August 20, 1993).
[3] Eli Biham and Adi Shamir. Differential Cryptanalysis of the Data
Encryption Standard. Springer-Verlag, New York, 1993.
[4] American National Standard X9.17: Financial Institution Key
Management (Wholesale). American National Standards Institute,
1985.
[5] National Institute of Standards and Technology (NIST). FIPS
Publication 81: DES Modes of Operation. December 2, 1980.
[6] Michael Roe. New modes of operation for a k-bit block cipher.
Cambridge University, July 1993. Version 0.2.
[7] Whitfield Diffie and Martin E. Hellman. Exhaustive cryptanalysis
of the NBS data encryption standard. Computer, 10:74-84, June
1977.
[8] Ralph C. Merkle and Martin E. Hellman. On the security of
multiple encryption. Communications of the ACM, 24(7):465-467,
July 1981.
[9] Paul C. van Oorschot and Michael J. Wiener. A known-plaintext
attack on two-key triple encryption. In Advances in Cryptology
--- EUROCRYPT '90, pages 318-325, Springer-Verlag, New York,
1991.
[10] Mitsuru Matsui. Linear cryptanalysis method for DES cipher.
Presented at EUROCRYPT '93 (Lofthus, Norway, May 24-27, 1993).
[11] Frank Rubin. Foiling an exhaustive key-search attack. Cryptologia
11(2):102-107, April 1987.