Editing Data Encryption Standard (section)

== History ==
The origins of DES date to 1972, when a [[National Bureau of Standards]] study of US government [[computer security]] identified a need for a government-wide standard for encrypting unclassified, sensitive information.<ref>{{cite conference|author=Walter Tuchman|title=A brief history of the data encryption standard|book-title=Internet besieged: countering cyberspace scofflaws|publisher=ACM Press/Addison-Wesley Publishing Co. New York, NY, USA|pages=275–280|year=1997}}</ref>

Around the same time, engineer [[Mohamed Atalla]] in 1972 founded [[Atalla Corporation]] and developed the first [[hardware security module]] (HSM), the so-called "Atalla Box" which was commercialized in 1973. It protected offline devices with a secure [[Personal identification number|PIN]] generating key, and was a commercial success. Banks and credit card companies were fearful that Atalla would dominate the market, which spurred the development of an international encryption standard.<ref name="Lazo">{{cite book |last1=Bátiz-Lazo |first1=Bernardo |title=Cash and Dash: How ATMs and Computers Changed Banking |date=2018 |publisher=[[Oxford University Press]] |isbn=9780191085574 |pages=284 & 311 |url=https://books.google.com/books?id=rWhiDwAAQBAJ&pg=PA284}}</ref> Atalla was an early competitor to [[IBM]] in the banking market, and was cited as an influence by IBM employees who worked on the DES standard.<ref name="nist">{{cite web |title=The Economic Impacts of NIST's Data Encryption Standard (DES) Program |url=https://www.nist.gov/sites/default/files/documents/2017/05/09/report01-2.pdf |website=[[National Institute of Standards and Technology]] |publisher=[[United States Department of Commerce]] |date=October 2001 |access-date=21 August 2019 |archive-date=30 August 2017 |archive-url=https://web.archive.org/web/20170830020822/https://www.nist.gov/sites/default/files/documents/2017/05/09/report01-2.pdf |url-status=dead }}</ref> The [[IBM 3624]] later adopted a similar PIN verification system to the earlier Atalla system.<ref name="Konheim">{{cite journal |last1=Konheim |first1=Alan G. |title=Automated teller machines: their history and authentication protocols |journal=Journal of Cryptographic Engineering |date=1 April 2016 |volume=6 |issue=1 |pages=1–29 |doi=10.1007/s13389-015-0104-3 |s2cid=1706990 |url=https://slideheaven.com/automated-teller-machines-their-history-and-authentication-protocols.html |issn=2190-8516 |access-date=28 August 2019 |archive-url=https://web.archive.org/web/20190722030759/https://slideheaven.com/automated-teller-machines-their-history-and-authentication-protocols.html |archive-date=22 July 2019 |url-status=dead |url-access=subscription }}</ref>

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 was 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)|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]].

=== NSA's involvement in the design ===
On 17 March 1975, the proposed DES was published in the ''[[Federal Register]]''. Public comments were requested, and in the following year two open workshops were held to discuss the proposed standard. There was criticism received from [[public-key cryptography]] pioneers [[Martin Hellman]] and [[Whitfield Diffie]],<ref name="dh-exh">{{cite journal
 |last1=Diffie 
 |first1=Whitfield 
 |last2=Hellman 
 |first2=Martin E. 
 |date=June 1977 
 |title=Exhaustive Cryptanalysis of the NBS Data Encryption Standard 
 |journal=Computer 
 |volume=10 
 |issue=6 
 |pages=74–84 
 |doi=10.1109/C-M.1977.217750 
 |s2cid=2412454 
 |url=http://origin-www.computer.org/csdl/mags/co/1977/06/01646525.pdf 
 |url-status=dead 
 |archive-url=https://web.archive.org/web/20140226205104/http://origin-www.computer.org/csdl/mags/co/1977/06/01646525.pdf 
 |archive-date=2014-02-26 
}}</ref> citing a shortened [[key length]] and the mysterious "[[Substitution box|S-boxes]]" as evidence of improper interference from the NSA. The suspicion was that the algorithm had been covertly weakened by the intelligence agency so that they—but no one else—could easily read encrypted messages.<ref>{{cite web
 |url=http://www.emc.com/emc-plus/rsa-labs/standards-initiatives/has-des-been-broken.htm
 |url-status=dead
 |archive-url=https://web.archive.org/web/20160517015519/http://www.emc.com/emc-plus/rsa-labs/standards-initiatives/has-des-been-broken.htm
 |archive-date=2016-05-17 
 |title=Has DES been broken?|author=RSA Laboratories|access-date=2009-11-08}}</ref> Alan Konheim (one of the designers of DES) commented, "We sent the S-boxes off to Washington. They came back and were all different."<ref>{{Cite book|last=Schneier|title=Applied Cryptography|edition=2nd|page=280}}</ref> The [[United States Senate Select Committee on Intelligence]] reviewed the NSA's actions to determine whether there had been any improper involvement. In the unclassified summary of their findings, published in 1978, the Committee wrote:
{{blockquote|In the development of DES, NSA convinced [[IBM]] that a reduced key size was sufficient; indirectly assisted in the development of the S-box structures; and certified that the final DES algorithm was, to the best of their knowledge, free from any statistical or mathematical weakness.<ref>{{Cite book|first=D.W.|last=Davies|author2=W.L. Price|title=Security for computer networks, 2nd ed.|publisher=John Wiley & Sons|year=1989}}</ref>}}
However, it also found that
{{blockquote|NSA did not tamper with the design of the algorithm in any way. IBM invented and designed the algorithm, made all pertinent decisions regarding it, and concurred that the agreed upon key size was more than adequate for all commercial applications for which the DES was intended.<ref>{{Cite journal|editor=Robert Sugarman |title=On foiling computer crime|journal=IEEE Spectrum|date=July 1979}}</ref>}}
Another member of the DES team, Walter Tuchman, stated "We developed the DES algorithm entirely within IBM using IBMers. The NSA did not dictate a single wire!"<ref>{{Cite journal|author=P. Kinnucan|title=Data Encryption Gurus: Tuchman and Meyer|journal=Cryptologia|volume=2|issue=4|date=October 1978|doi=10.1080/0161-117891853270|page=371}}</ref>
In contrast, a declassified NSA book on cryptologic history states:
{{blockquote|In 1973 NBS solicited private industry for a data encryption standard (DES). The first offerings were disappointing, so NSA began working on its own algorithm. Then Howard Rosenblum, deputy director for research and engineering, discovered that Walter Tuchman of IBM was working on a modification to Lucifer for general use. NSA gave Tuchman a clearance and brought him in to work jointly with the Agency on his Lucifer modification."<ref name=johnson3>{{cite web|url=http://www.nsa.gov/public_info/_files/cryptologic_histories/cold_war_iii.pdf |title=American Cryptology during the Cold War, 1945-1989.Book III: Retrenchment and Reform, 1972-1980, page 232 |author=Thomas R. Johnson |access-date=2014-07-10 |publisher=[[National Security Agency]], DOCID 3417193 (file released on 2009-12-18, hosted at nsa.gov) |date=2009-12-18 |url-status=dead |archive-url=https://web.archive.org/web/20130918020036/http://www.nsa.gov/public_info/_files/cryptologic_histories/cold_war_iii.pdf |archive-date=2013-09-18 }}</ref>}}
and
{{blockquote|NSA worked closely with IBM to strengthen the algorithm against all except brute-force attacks and to strengthen substitution tables, called S-boxes. Conversely, NSA tried to convince IBM to reduce the length of the key from 64 to 48 bits. Ultimately they compromised on a 56-bit key.<ref>{{cite web|url=http://nsarchive.gwu.edu/NSAEBB/NSAEBB260/nsa-5.pdf |archive-url=https://web.archive.org/web/20150425043600/http://nsarchive.gwu.edu/NSAEBB/NSAEBB260/nsa-5.pdf |archive-date=2015-04-25 |url-status=live|title=American Cryptology during the Cold War, 1945-1989.Book III: Retrenchment and Reform, 1972-1980, page 232 |author = Thomas R. Johnson| access-date=2015-07-16 |publisher = [[National Security Agency]]| date= 2009-12-18| via=[[National Security Archive]] FOIA request. This version is differently redacted than the version on the NSA website.}}</ref><ref>{{cite web|url=http://nsarchive.gwu.edu/NSAEBB/NSAEBB260/nsa-6.pdf |archive-url=https://web.archive.org/web/20150425043604/http://nsarchive.gwu.edu/NSAEBB/NSAEBB260/nsa-6.pdf |archive-date=2015-04-25 |url-status=live|title=American Cryptology during the Cold War, 1945-1989.Book III: Retrenchment and Reform, 1972-1980, page 232 |author = Thomas R. Johnson| access-date=2015-07-16 |publisher = [[National Security Agency]]| date= 2009-12-18| via=[[National Security Archive]] FOIA request. This version is differently redacted than the version on the NSA website.}}</ref>}}

Some of the suspicions about hidden weaknesses in the S-boxes were allayed in 1990, with the independent discovery and open publication by [[Eli Biham]] and [[Adi Shamir]] of [[differential cryptanalysis]], a general method for breaking block ciphers. 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 in the 1970s. This was indeed the case; in 1994, Don Coppersmith published some of the original design criteria for the S-boxes.<ref>{{Cite book|last=Konheim|title=Computer Security and Cryptography|page=301}}</ref> According to [[Steven Levy]], IBM Watson researchers discovered differential cryptanalytic attacks in 1974 and were asked by the NSA to keep the technique secret.<ref name=Levy>Levy, ''Crypto'', p. 55</ref> Coppersmith explains IBM's secrecy decision by saying, "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." Levy quotes Walter Tuchman: "[t]hey asked us to stamp all our documents confidential... We actually put a number on each one and locked them up in safes, because they were considered U.S. government classified. They said do it. So I did it".<ref name=Levy/> Bruce Schneier observed that "It took the academic community two decades to figure out that the NSA 'tweaks' actually improved the security of DES."<ref name="schneier20040927">{{Cite news|last=Schneier|first=Bruce|title=Saluting the data encryption legacy|url=http://www.cnet.com/news/saluting-the-data-encryption-legacy/|access-date=2015-07-22|newspaper=CNet|date=2004-09-27}}</ref>

=== The algorithm as a standard ===
Despite the criticisms, DES was approved as a federal standard in November 1976, and published on 15 January 1977 as [[Federal Information Processing Standard|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 [[Advanced Encryption Standard process|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.<ref name=SP800-67>[[National Institute of Standards and Technology]], [http://csrc.nist.gov/publications/nistpubs/800-67-Rev1/SP-800-67-Rev1.pdf NIST Special Publication 800-67 ''Recommendation for the Triple Data Encryption Algorithm (TDEA) Block Cipher'', Version 1.1]</ref>

The algorithm is also specified in [[ANSI]] X3.92 (Today X3 is known as [[INCITS]] and ANSI X3.92 as ANSI [[INCITS]] 92),<ref>[[American National Standards Institute]], ANSI X3.92-1981 (now known as ANSI [[INCITS]] 92-1981)''American National Standard, Data Encryption Algorithm''</ref> NIST SP 800-67<ref name=SP800-67/> and ISO/IEC 18033-3<ref>{{cite web|url=http://www.iso.org/iso/iso_catalogue/catalogue_ics/catalogue_detail_ics.htm?csnumber=54531 |title=ISO/IEC 18033-3:2010 Information technology—Security techniques—Encryption algorithms—Part 3: Block ciphers |publisher=Iso.org |date=2010-12-14 |access-date=2011-10-21}}</ref> (as a component of [[TDEA]]).

Another theoretical attack, linear cryptanalysis, was published in 1994, but it was the [[Electronic Frontier Foundation]]'s [[EFF DES cracker|DES cracker]] 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 this 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]],<ref>Bruce Schneier, Applied Cryptography, Protocols, Algorithms, and Source Code in C, Second edition, John Wiley and Sons, New York (1996) p. 267</ref> "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.<ref>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.  [http://nvl.nist.gov/pub/nistpubs/sp958-lide/html/250-253.html HTML] {{Webarchive|url=https://web.archive.org/web/20090619181704/http://nvl.nist.gov/pub/nistpubs/sp958-lide/html/250-253.html |date=2009-06-19 }} [http://nvl.nist.gov/pub/nistpubs/sp958-lide/250-253.pdf PDF] {{Webarchive|url=https://web.archive.org/web/20060823131553/http://nvl.nist.gov/pub/nistpubs/sp958-lide/250-253.pdf |date=2006-08-23 }}</ref>

=== Chronology ===
{| class="wikitable" style="font-size:85%;"
|-
! 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
|-
| June
| 1977
| [[Whitfield Diffie|Diffie]] and [[Martin Hellman|Hellman]] argue that the DES cipher can be broken by brute force.<ref name="dh-exh"/>
|-
|
| 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
| 1991
| 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 2<sup>47</sup> [[chosen plaintext]]s.
|-
| 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 [[Electronic Frontier Foundation|EFF]]'s [[EFF DES cracker|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 becomes effective
|-
| 26 July
| 2004
| The withdrawal of FIPS 46-3 (and a couple of related standards) is proposed in the ''Federal Register''<ref>{{cite web|url=http://edocket.access.gpo.gov/2004/04-16894.htm |title=FR Doc 04-16894 |publisher=Edocket.access.gpo.gov |access-date=2009-06-02}}</ref>
|-
| 19 May
| 2005
| NIST withdraws FIPS 46-3 (see [https://web.archive.org/web/20080625202735/http://csrc.nist.gov/publications/fips/05-9945-DES-Withdrawl.pdf Federal Register vol 70, number 96])
|-
| April
| 2006
| The [[Field-programmable gate array|FPGA]]-based parallel machine [[Custom hardware attack#History|COPACOBANA]] of the Universities of Bochum and Kiel, Germany, breaks DES in 9 days at a $10,000 hardware cost.<ref name="copacobana-2006">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.</ref> Within a year software improvements reduced the average time to 6.4 days.
|-
| Nov.
| 2008
| The successor of [[Custom hardware attack#History|COPACOBANA]], the RIVYERA machine, reduced the average time to less than a single day.
|-
| August
| 2016
| The Open Source password cracking software [https://hashcat.net/hashcat/ hashcat] added in DES brute force searching on general purpose GPUs. Benchmarking shows a single off the shelf Nvidia [[GeForce 10 series|GeForce GTX 1080 Ti]] GPU costing US$1000 recovers a key in an average of 15 days (full exhaustive search taking 30 days). Systems have been built with eight GTX 1080 Ti GPUs which can recover a key in an average of under 2 days.<ref>{{Cite web | url=https://gist.github.com/epixoip/ace60d09981be09544fdd35005051505 | title=8x1080Ti.md}}</ref>
|-
| July
| 2017
| A [[chosen-plaintext attack]] utilizing a [[rainbow table]] can recover the DES key for a single specific chosen plaintext ''1122334455667788'' in 25 seconds. A new rainbow table has to be calculated per plaintext. A limited set of rainbow tables have been made available for download.<ref>{{Cite web | url=https://crack.sh | title=Crack.sh &#124; the World's Fastest DES Cracker}}</ref>
|}