# Data Encryption Standard

559pages on
this wiki

The Data Encryption Standard (DES) is a block cipher that uses shared secret encryption. It was selected by the National Bureau of Standards as an official Federal Information Processing Standard (FIPS) for the United States in 1976 and which has subsequently enjoyed widespread use internationally. It is based on a symmetric-key algorithm that uses a 56-bit key. The algorithm was initially controversial with classified design elements, a relatively short key length, and suspicions about a National Security Agency (NSA) backdoor. DES consequently came under intense academic scrutiny which motivated the modern understanding of block ciphers and their cryptanalysis.

DES is now considered to be insecure for many applications. This is chiefly due to the 56-bit key size being too small; in January, 1999, distributed.net and the Electronic Frontier Foundation collaborated to publicly break a DES key in 22 hours and 15 minutes (see chronology). There are also some analytical results which demonstrate theoretical weaknesses in the cipher, although they are infeasible to mount in practice. The algorithm is believed to be practically secure in the form of Triple DES, although there are theoretical attacks. In recent years, the cipher has been superseded by the Advanced Encryption Standard (AES). Furthermore, DES has been withdrawn as a standard by the National Institute of Standards and Technology (formerly the National Bureau of Standards).

In some documentation, a distinction is made between DES as a standard and DES the algorithm which is referred to as the DEA (the Data Encryption Algorithm). When spoken, "DES" is either spelled out as an abbreviation (Template:IPA-en), or pronounced as a one-syllable acronym (Template:IPA-en).

## History of DES Edit

The origins of DES go back to the early 1970s. In 1972, after concluding a study on the US government's computer security needs, the US standards body NBS (National Bureau of Standards) — now named NIST (National Institute of Standards and Technology) — identified a need for a government-wide standard for encrypting unclassified, sensitive information.[1] Accordingly, on 15 May 1973, after consulting with the NSA, NBS solicited proposals for a cipher that would meet rigorous design criteria. None of the submissions, however, turned out to be suitable. A second request was issued on 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 at IBM involved in cipher design and analysis included Feistel, Walter Tuchman, Don Coppersmith, Alan Konheim, Carl Meyer, Mike Matyas, Roy Adler, Edna Grossman, Bill Notz, Lynn Smith, and Bryant Tuckerman.

### The algorithm as a standard Edit

Despite the criticisms, DES was approved as a federal standard in November 1976, and published on 15 January 1977 as FIPS PUB 46, authorized for use on all unclassified data. It was subsequently reaffirmed as the standard in 1983, 1988 (revised as FIPS-46-1), 1993 (FIPS-46-2), and again in 1999 (FIPS-46-3), the latter prescribing "Triple DES" (see below). On 26 May 2002, DES was finally superseded by the Advanced Encryption Standard (AES), following a public competition. On 19 May 2005, FIPS 46-3 was officially withdrawn, but NIST has approved Triple DES through the year 2030 for sensitive government information.[8]

The algorithm is also specified in ANSI X3.92,[9] NIST SP 800-67[8] and ISO/IEC 18033-3[10] (as a component of TDEA).

Another theoretical attack, linear cryptanalysis, was published in 1994, but it was a brute force attack in 1998 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. According to a NIST retrospective about DES,

The DES can be said to have "jump started" the nonmilitary study and development of encryption algorithms. In the 1970s there were very few cryptographers, except for those in military or intelligence organizations, and little academic study of cryptography. There are now many active academic cryptologists, mathematics departments with strong programs in cryptography, and commercial information security companies and consultants. A generation of cryptanalysts has cut its teeth analyzing (that is trying to "crack") the DES algorithm. In the words of cryptographer Bruce Schneier,[11] "DES did more to galvanize the field of cryptanalysis than anything else. Now there was an algorithm to study." An astonishing share of the open literature in cryptography in the 1970s and 1980s dealt with the DES, and the DES is the standard against which every symmetric key algorithm since has been compared.[12]

### Chronology Edit

Date Year Event
15 May 1973 NBS publishes a first request for a standard encryption algorithm
27 August 1974 NBS publishes a second request for encryption algorithms
17 March 1975 DES is published in the Federal Register for comment
August 1976 First workshop on DES
September 1976 Second workshop, discussing mathematical foundation of DES
November 1976 DES is approved as a standard
15 January 1977 DES is published as a FIPS standard FIPS PUB 46
1983 DES is reaffirmed for the first time
1986 Videocipher II, a TV satellite scrambling system based upon DES begins use by HBO
22 January 1988 DES is reaffirmed for the second time as FIPS 46-1, superseding FIPS PUB 46
July 1990 Biham and Shamir rediscover differential cryptanalysis, and apply it to a 15-round DES-like cryptosystem.
1992 Biham and Shamir report the first theoretical attack with less complexity than brute force: differential cryptanalysis. However, it requires an unrealistic 247 chosen plaintexts.
30 December 1993 DES is reaffirmed for the third time as FIPS 46-2
1994 The first experimental cryptanalysis of DES is performed using linear cryptanalysis (Matsui, 1994).
June 1997 The DESCHALL Project breaks a message encrypted with DES for the first time in public.
July 1998 The EFF's DES cracker (Deep Crack) breaks a DES key in 56 hours.
January 1999 Together, Deep Crack and distributed.net break a DES key in 22 hours and 15 minutes.
25 October 1999 DES is reaffirmed for the fourth time as FIPS 46-3, which specifies the preferred use of Triple DES, with single DES permitted only in legacy systems.
26 November 2001 The Advanced Encryption Standard is published in FIPS 197
26 May 2002 The AES standard becomes effective
26 July 2004 The withdrawal of FIPS 46-3 (and a couple of related standards) is proposed in the Federal Register[13]
19 May 2005 NIST withdraws FIPS 46-3 (see Federal Register vol 70, number 96)

### Attacks faster than brute-force Edit

There are three attacks known that can break the full sixteen rounds of DES with less complexity than a brute-force search: differential cryptanalysis (DC), linear cryptanalysis (LC), and Davies' attack. However, the attacks are theoretical and are unfeasible to mount in practiceTemplate:Citation needed; these types of attack are sometimes termed certificational weaknesses.

• Differential cryptanalysis was rediscovered in the late 1980s by Eli Biham and Adi Shamir; it was known earlier to both IBM and the NSA and kept secret. To break the full 16 rounds, differential cryptanalysis requires 247 chosen plaintexts.Template:Citation needed DES was designed to be resistant to DC.
• Linear cryptanalysis was discovered by Mitsuru Matsui, and needs 243 known plaintexts (Matsui, 1993); the method was implemented (Matsui, 1994), and was the first experimental cryptanalysis of DES to be reported. There is no evidence that DES was tailored to be resistant to this type of attack. A generalisation of LC — multiple linear cryptanalysis — was suggested in 1994 (Kaliski and Robshaw), and was further refined by Biryukov et al. (2004); their analysis suggests that multiple linear approximations could be used to reduce the data requirements of the attack by at least a factor of 4 (i.e. 241 instead of 243). A similar reduction in data complexity can be obtained in a chosen-plaintext variant of linear cryptanalysis (Knudsen and Mathiassen, 2000). Junod (2001) performed several experiments to determine the actual time complexity of linear cryptanalysis, and reported that it was somewhat faster than predicted, requiring time equivalent to 239–241 DES evaluations.
• Improved Davies' attack: while linear and differential cryptanalysis are general techniques and can be applied to a number of schemes, Davies' attack is a specialised technique for DES, first suggested by Donald Davies in the eighties, and improved by Biham and Biryukov (1997). The most powerful form of the attack requires 250 known plaintexts, has a computational complexity of 250, and has a 51% success rate.

There have also been attacks proposed against reduced-round versions of the cipher, i.e. versions of DES with fewer than sixteen rounds. Such analysis gives an insight into how many rounds are needed for safety, and how much of a "security margin" the full version retains. Differential-linear cryptanalysis was proposed by Langford and Hellman in 1994, and combines differential and linear cryptanalysis into a single attack. An enhanced version of the attack can break 9-round DES with 215.8 known plaintexts and has a 229.2 time complexity (Biham et al., 2002).

### Minor cryptanalytic properties Edit

DES exhibits the complementation property, namely that

Failed to parse (PNG conversion failed; check for correct installation of latex and dvipng (or dvips + gs + convert)): E_K(P)=C \Leftrightarrow E_\overline{K}(\overline{P})=\overline{C}

where $\overline{x}$ is the bitwise complement of $x.$ $E_K$ denotes encryption with key $K.$ $P$ and $C$ denote plaintext and ciphertext blocks respectively. The complementation property means that the work for a brute force attack could be reduced by a factor of 2 (or a single bit) under a chosen-plaintext assumption.

DES also has four so-called weak keys. Encryption (E) and decryption (D) under a weak key have the same effect (see involution):

$E_K(E_K(P)) = P$ or equivalently, $E_K = D_K$

There are also six pairs of semi-weak keys. Encryption with one of the pair of semiweak keys, $K_1$, operates identically to decryption with the other, $K_2$:

$E_{K_1}(E_{K_2}(P)) = P$ or equivalently, $E_{K_2} = D_{K_1}.$

It is easy enough to avoid the weak and semiweak keys in an implementation, either by testing for them explicitly, or simply by choosing keys randomly; the odds of picking a weak or semiweak key by chance are negligible. The keys are not really any weaker than any other keys anyway, as they do not give an attack any advantage.

DES has also been proved not to be a group, or more precisely, the set $\{E_K\}$ (for all possible keys $K$) under functional composition is not a group, nor "close" to being a group (Campbell and Wiener, 1992). This was an open question for some time, and if it had been the case, it would have been possible to break DES, and multiple encryption modes such as Triple DES would not increase the security.

It is known that the maximum cryptographic security of DES is limited to about 64 bits, even when independently choosing all round subkeys instead of deriving them from a key, which would otherwise permit a security of 768 bits.

## Notes Edit

1. Template:Cite conference
2. Template:Cite web
3. Template:Cite book
4. Template:Cite journal
5. Template:Cite book
6. 6.0 6.1 Levy, Crypto, p. 55
7. Template:Cite news
8. 8.0 8.1
9. American National Standards Institute, ANSI X3.92-1981 American National Standard, Data Encryption Algorithm
10. Template:Cite web
11. Bruce Schneier, Applied Cryptography, Protocols, Algorithms, and Source Code in C, Second edition, John Wiley and Sons, New York (1996) p. 267
12. William E. Burr, "Data Encryption Standard", in NIST's anthology "A Century of Excellence in Measurements, Standards, and Technology: A Chronicle of Selected NBS/NIST Publications, 1901–2000. HTML PDF
13. Template:Cite web
14. S. Kumar, C. Paar, J. Pelzl, G. Pfeiffer, A. Rupp, M. Schimmler, "How to Break DES for Euro 8,980". 2nd Workshop on Special-purpose Hardware for Attacking Cryptographic Systems — SHARCS 2006, Cologne, Germany, April 3–4, 2006.
15. Template:Cite web
16. Template:Cite web
17. Stallings, W. Cryptography and network security: principles and practice. Prentice Hall, 2006. p. 73
18. Break DES in less than a single day [Press release of Firm, demonstrated on 2009 Workshop]