- This article is about the DES encryption algorithm. For other uses of DES, see DES (disambiguation).
The Data Encryption Standard (DES) is a cipher (a
method for encrypting information) selected as an official standard for the United States in 1976, and which has subsequently enjoyed widespread use internationally. The algorithm was
initially controversial, with classified design elements, a relatively short
key length, and continuing suspicions about a National Security Agency (NSA) backdoor. DES consequently came under intense academic
scrutiny, and motivated the modern understanding of block ciphers and their
cryptanalysis. The cipher has since been superseded by the Advanced Encryption Standard (AES).
In some documentation, DES is referred to as the DEA (the Data Encryption Algorithm). When
spoken, "DES" is either spelled out (dee-ee-ess) or pronounced as a single syllable (dez).
History of DES
The origins of DES go back to the early 1970s. In 1972, the US government's standards body, NBS (now renamed NIST), started a project with the aim of improving computer and communications
security. A central requirement was a standard encryption algorithm. Accordingly, on 15
May 1973, NBS solicited proposals for a cipher that would meet rigorous design
criteria. None of the submissions, however, were suitable. A second request was issued on the 27 August 1974. This time, IBM submitted a candidate which was deemed acceptable, a cipher developed during the
period 1973—1974 based on an earlier algorithm,
Horst Feistel's Lucifer cipher. The team involved in the design and analysis included Walter Tuchman, Don Coppersmith, Alan Konheim, Carl Meyer and Mike Matyas.
In 1975 public comments were requested, and in the following year two open workshops
were held to discuss the proposed standard. There was some criticism, particularly from Martin Hellman and Whitfield Diffie, citing a
shortened key length and the mysterious "S-boxes" as evidence of improper interference from the NSA. The suspicion was
that the algorithm had been deliberately weakened by the intelligence agency so that they would be able to easily read encrypted
messages. Regardless, DES was approved as a federal standard in November 1976, and
published in January 1977 as FIPS PUB 46, authorised for use on all
unclassified data. It was subsequently reaffirmed as the standard in 1983, 1988, 1993, and again in 1998, but in an incarnation known as "Triple DES". In 2001, DES was finally superseded by AES, the Advanced
Encryption Standard, following a public competition (see AES process). Even
as of 2004, however, DES remains in widespread use.
The overall Feistel structure of DES
In 1990, with the independent discovery and open publication by Biham and Shamir of differential cryptanalysis, it turned out that at least
some of the suspicions about the algorithm were unfounded. Differential cryptanalysis is a general method breaking block ciphers,
and the S-boxes of DES were much more resistant to the attack than if they had been chosen at random, strongly suggesting that
IBM knew about the technique back in the 1970s. This was indeed the case — in
1994, Don Coppersmith published the original design criteria for the S-boxes. IBM had
discovered differential cryptanalysis in the 1970s and, after securing DES, had been
instructed to keep the technique secret by the NSA. Coppersmith explains, "that was because [differential cryptanalysis] can
be a very powerful tool, used against many schemes, and there was concern that such information in the public domain could
adversely affect national security."
Another theoretical attack, linear cryptanalysis, was
published in 1994, but it was a brute force attack in 1997 that demonstrated that DES could be
attacked very practically, and highlighted the need for a replacement algorithm. These and other methods of cryptanalysis are discussed in more detail later in the article.
The introduction of DES is considered to have been a catalyst for the academic study of cryptography, particularly of methods
to crack block ciphers. Bruce Schneier writes:
- "Off the record, NSA has characterized DES as one of their biggest mistakes. If they knew the details would be released
so that people could write software, they would never have agreed to it. DES did more to galvanize the field of cryptanalysis
than anything else. Now there was an algorithm to study: one that the NSA said was secure."
Description
DES is the archetypal block cipher — an algorithm that takes a
fixed-length string of plaintext bits and transforms it through a series of
complicated operations into another ciphertext bitstring of the same length. In
the case of DES, the block size is 64 bits.
DES also uses a key to customise the transformation, so
that decryption can only be performed by those who know the particular key used to encrypt. The key ostensibly consists of 64
bits; however, only 56 of these are actually used by the algorithm. Eight bits are used solely for checking parity, and are thereafter discarded. Hence the effective key length is 56 bits, and it is usually quoted as such.
The "F-function" of DES
The algorithm's overall structure can be seen in the first diagram: there are 16 identical stages of processing, termed
rounds. There is also an initial and final permutation, termed
IP and FP, which are inverses (IP
"undoes" the action of FP, and vice versa). Before the main rounds, the block is divided into two 32-bit halves and processed
alternately; this criss-crossing is known as the Feistel scheme. The
red "⊕" symbol denotes the exclusive-OR (XOR) operation. The F-function
scrambles half a block together with some of the key.
The F-function takes half a block (32 bits), and expands it to 48 bits using the expansion permutation, denoted
E in the diagram. This simply involves duplicating some of the bits. Next, the result is combined using XOR with a
subkey. Sixteen 48-bit subkeys — one for each round — are derived from the main key using the key schedule which will be described shortly. After combining with the subkey,
the block is divided into 6-bit pieces before processing by the S-boxes, or
substitution box. Each of the eight S-boxes replace its six input bits with four output bits according to a non-linear
transformation, provided in the form of a lookup table. The S-boxes provide
the core of the security of DES — without them, the cipher would be linear, and trivially breakable. Finally, the 32
outputs from the S-boxes are rearranged according a fixed permutation, the
P-box.
The key schedule is the algorithm which generates the subkeys.
Initially, 56 bits of the key are selected from the initial 64 by Permuted Choice 1 (PC-1). Then the 56 bits
are divided into two 28-bit halves. Each half is thereafter treated separately. In successive rounds, each half is rotated left
by one or two bits, and then the 32 subkey bits are selected by Permuted Choice 2 (PC-2).
The benefit of the Feistel structure is that decryption and encryption are very similar processes — the only difference
is that the subkeys are applied in the reverse order when decrypting. The rest of the algorithm is identical. This greatly
simplifies implementation, particularly in hardware, as there is no need for separate encryption and decryption algorithms.
The key-schedule of DES
The DES algorithm lends itself to integrated circuit
implementation. By 1984 the Bureau of Standards had certified over 35 LSI- and VLSI-chip implementations of the DES, most on single 40-pin chips, some of which operate at speeds
of several million bits per second.
Vulnerabilities
For any cipher, the most basic method of attack is brute
force — trying every possible key in turn. The key length determines the feasibility of this approach, and the 56 bits
used by DES are too few for increasingly many applications. It is known that the NSA persuaded IBM to reduce the key size from
128 to 64 bits, and then 56 bits, and it is believed that this is evidence that the NSA possessed enough computer power to brute
force break keys of this length even in the mid-1970s. In the years since, computer
hardware progress has been such that many now have the capability to break the cipher, not just major governments.
The EFF, a cyberspace civil rights
group did it in a little more than 2 days' search at about the same time at least one attorney from the US Justice Department was
publicly announcing that DES was and would remain unbreakable. The EFF group, spending 250 thousand US dollars, accomplished the
feat in 1999. Moore's law, combined
with the far lesser per-unit costs of ordering great numbers of microchips, suggests that a corporation willing to spend 10
million dollars to build a similar device today might break DES dozens if not hundreds of times per hour.
DES's short key length is not its only problem — it also has weak keys
(see article for more details).
Replacement algorithms
Many former DES users now use Triple DES (3DES) which was described and
analyzed by one of DES's patentees (see FIPS Pub 46-3); it involves applying DES three
times with different keys. 3DES is widely regarded as adequately secure for now, though it is quite slow. A less computationally
expensive alternative is DES-X, which increases the key size by XORing extra key material
before and after DES. GDES was a DES variant proposed as a way to speed up encryption, but
it was shown to be susceptible to differential cryptanalysis.
After much delay (DES was to have been a standard for only five years), and after another, widely respected, competition, NIST
has selected a new cipher, the Advanced
Encryption Standard (AES) to replace DES late in 2001. The algorithm which was selected as the AES was submitted by its
designers under the name Rijndael. Other finalists in the NIST AES competition included RC6, Serpent, MARS, and Twofish.
It should be noted that no encryption algorithm is ideally suited for all uses. Algorithms suitable for low-throughput use on
general-purpose machines (eg, SSH, or various forms of email encyption) are not always suited
to embedded systems or smart cards, and so on.
See also
References
- Eli Biham, Adi Shamir, Differential Cryptanalysis of the Data Encryption Standard, Springer Verlag, 1993. ISBN 0-387-97930-1, ISBN 3-540-97930-1.
- Coppersmith, Don. (1994). The data encryption standard (DES) and its strength against attacks. IBM Journal of Research
and Development, 38(3), 243–250. [1]
- John Gilmore, "Cracking DES: Secrets of Encryption Research, Wiretap
Politics and Chip Design", 1998, O'Reilly, ISBN 1565925203.
- Steven Levy, Crypto: How the Code Rebels Beat the
Government Saving Privacy in the Digital Age (ISBN 0140244328)
- Matsui, M. (1993). Linear cryptanalysis method for DES cipher. EUROCRYPT 1993.
- National Bureau of Standards, Data Encryption Standard, FIPS-Pub.46. National Bureau of Standards, U.S. Department of
Commerce, Washington D.C., January 1977.
External links
|