EditWYSIWYGAttach PDF Raw View►More Actions▼More Actions


Restore topic to revision: You will be able to review the topic before saving it to a new revision

Copy text and form data to a new topic (no attachments will be copied though).
Name of copy:
You will be able to review the copied topic before saving

Rename/move topic... scans links in all public webs (recommended)
Rename/move topic... scans links in CBI_ComputerSecurity web only
Delete topic... scans links in all public webs (recommended)
Delete topic... scans links in CBI_ComputerSecurity web only

Revision Date Username Comment
1502 Apr 2015 - 16:46sever408? 
1412 Mar 2015 - 13:33sever408? 
1312 Mar 2015 - 13:28sever408?Attached file Feistel.png

Attached file DES-S-Box.png 
1212 Nov 2014 - 22:59ThomasMisa 
1112 Nov 2014 - 22:56ThomasMisa 
1021 Jul 2014 - 16:15ThomasMisaAttached file NIST-on-economic-impact-DES_report01-2.pdf 
919 Jul 2014 - 22:02ThomasMisa 
819 Jul 2014 - 21:58ThomasMisa 
730 May 2014 - 18:02ThomasMisa 
630 May 2014 - 17:12ThomasMisa 
earlier first

Render style:     Context:


 History: r15 | r7 < r6 < r5 < r4
[X] Hide this message.
Notice: On June 30, 2016, UMWiki service will be decommissioned. If you have information in UMWIki that needs to be preserved, you should make plans to move it before that date. Google Sites is anticipated to be the most popular and appropriate alternative for users because it offers a more modern and user-friendly interface and unlimited capacity. To learn more about the features of Google Sites and other alternatives, and to identify which one best fits your needs, see the University’s Website Solution Selection Guide. If you have concerns or would like help regarding this change and your options, please contact Technology Help at help@umn.edu
You are here: UMWiki>CBI_ComputerSecurity Web>Mechanisms>MechanismsDataEncryptionStandard (revision 5)

Current Activitieslock Who is Who?lock People Programs Publications CSHW_2014 Systems Events Mechanisms

CONTENTS

Data Encryption Standard (DES)

The Data Encryption Standard (DES) is a 56-bit encryption system that was developed by IBM and adopted by the National Bureau of Standards (NBS) for commercial use in 1977. Walter Tuchman and Carl Meyer were the primary developers of the algorithm, though there was a larger team that worked on the hardware implementation of the algorithm. During the NBS adoption process there was a great deal of debate over the involvement of the National Security Agency (NSA) in DES development as well as concerns over whether 56 bits were enough to ensure security.(1)

Development of DES

DES grew out of an IBM project (code-named Lucifer) to develop a secure encryption system for Automatic Tellerm Machines, commissioned by Lloyd's Bank. Neither Tuchman not Meyer had any direct experience with cryptography when they started the project, so they spent several years reading cryptography literature and attempting to break various algorithms. "You can't design good ciphers unless you have had experience in breaking them," noted Meyer.(2)

As Lucifer neared completion the NBS made a request for proposals for a national standard for commercial cryptography. Tuchman, Meyer, and the rest of the Lucifer team were thus re-tasked with creating DES. Beginning in 1971, the team worked on the algorithm and its implementation for six years. The basic idea of the system was that two users who wanted to communicate would each have an encryption device connected between their modem and their computer. Then one user would pick an encryption key that would then be sent to the other user via some secure method such as courier or registered mail. Then both users could enter the key into the encryption devices at either end of the connection and share data or messages securely. Tuchman and Meyer developed an algorithm that they felt was secure, then moved on to the "validation" process, which involved a series of attempts to attack the cipher in various ways in an attempt to find a weakness. The validation process can be lengthy because it can never prove conclusively that an encryption method is secure. Tuchman and Meyer spent several years on the validation of DES, while also working on implementing the system in hardware that could be connected between a modem and computer or terminal. The NBS asked the NSA perform an analysis of DES, during which the NSA told Tuchman and Meyer that their work had duplicated NSA efforts in some ways, and that parts of it would therefore need to be classified. The NSA may have also asked Tuchman and Meyer to reduce their 128-bit key to 56 bits, as alleged by several computer scientists at Bell Laboratories and corroborated by a Senate Select Intelligence Committee report. Based on the NSA's recommendation, the NBS then officially adopted DES as the standard that all private companies contracted with the U.S. government would be expected to meet. Tuchman proudly declared "The DES algorithm is for all practical purposes unbreakable, yet it is easy to implement... and it performs at high speed."(3)(4)(5)

Controversy

The NSA's involvement and the perceived weakness of the 56-bit key led to significant controversy when it became clear that the NBS would adopt DES as its standard. Computer scientists, primarily at Stanford University, the Massachusetts Institute of Technology, and Bell Laboratories, began to fiercely criticize the way that DES had been developed and the security of the algorithm itself. Two particular criticisms were voiced repeatedly. The first was that the 56-bit key was too short to be considered secure. The second criticism was that the secrecy of the development documentation meant that there was no way to tell if the NSA had installed a secret key or method in DES that would bypass the user-created security key and thus ensure the agency's ability to read any DES-encrypted messages.

Perceived Weakness of the 56-bit Key

The size of the key seemed to critics like an easily fixed and obvious problem. After studying the DES standard, Martin Hellman and Whitfield Diffie, researchers at Stanford who had developed a (still theoretical) method of public-key cryptography, concluded that for $20 million a machine could be built that could crack a DES-encoded message in 12 hours of computing time. They added that if the machine worked at breaking codes for five years, the equivalent cost per solution would be $5,000. While such cost might be prohibitive to private companies trying to steal one-another's secrets, major intelligence agencies such as the NSA would have both the resources and the interest to build such a computer. Furthermore, as computing costs decreased the cost of building such a machine would decrease as well, such that in 10 years the machine's cost would be in the range of $200,000 and the cost per solution would be around $50. Under the right conditions, such as if the original uncoded message used standard ASCII characters, both the time and expense necessary would decrease substantially. Hellman, along with others, further alleged that the 56-bit key length had been pushed by the NSA specifically so that the NSA could read DES-encoded messages should the need arise.(6)(7)

Supporters of DES at the NBS and IBM, particulalry Tuchman, responded vigorously to such criticisms. In response to the concerns, the NBS held two workshops August and September in 1976 and invited all interested cryptographers and computer scientists. At the first workshop some computer manufacturers stated that the code-breaking machine described by Hellman and Diffie would not be feasible until 1990. At the second workshop Tuchman cited an internal IBM study that stated that the machine would cost $200 million in 1981, and not the $20 million quoted by Hellman and Diffie. IBM officials also stated that the 56-bit key size was not dictated by the NSA, but rather was chosen for technical and economic reasons. They also cited their own failed attempts to break the DES through various shortcuts, but did not release any details.(8)

In interviews and letters to the editor, Tuchman personally took several different approaches to countering criticism of the key length. He argued that the controversy had been sensationalized by the media, was "more academic than real," and was a carryover from the the distrustful Watergate era, when anyone working with national defense agencies was "automatically considered guilty of hanky-panky until proven innocent." He further argued that the 56-bit key length was only supposed to last five to ten years in the first place and that when it was no longer secure users could simply encode messages twice to effectively double the key length to 112 bits.(9)

Such arguments did not appease critics, who pointed out that the NSA had to approve DES for sale abroad, had a history of balking at large encryption key sizes in such circumstances, and would not have approved truly secure encryption for sale abroad. Critics such as Ron Rivest, a computer scientist at MIT who developed the first working version of Diffie and Hellman's public key concept, argued that the 56-bit key could be doubled to 128-bit at little or no extra cost. The Senate Select Committee on Intelligence heard testimony on the controversy and reported that the NSA had "convinced I.B.M. that a reduced key size was sufficient," lending further credence to the concerns of Hellman, Rivest and others. It should be noted, however, that in the same report the Senate committee exonerated the NSA of any wrongdoing and, furthermore, recommended that the agency be given a formal role in helping the National Science Foundation to select which scientists and institutions get federal research grants for cryptographic work.(10)(11)

The Alleged Secret Key

The second major criticism, put forward primarily by Hellman and Diffie, was that the NSA had classified documents on the development process to disguise a secret key or method that would allow the agency to read DES-encoded messages. The two Stanford researchers argued that there could be no "secret structures" if a public security standard was to be considered in any way valid. If a cryptography system somehow depended on "secret design principles" in order to work, then it was not truly secure. At one of the 1976 workshops Hellman apparently confronted Tuchman with his concerns, though how Tuchman responded was not recorded.(12)(13)(14)

Tuchman vehemently denied these charges, arguing that the development of DES was wholly the work of IBM, and that "the NSA did not dictate a single wire!" Tuchman later said that he had no idea how such a secret key could even be installed in the system. The aforementioned Senate report also concluded that there had been no collusion between IBM and the NSA. (15)(16)

Alleged NSA Targeting of Cryptographers

Compounding the controversy over the security of DES were allegations that the NSA had harassed or threatened private researchers who published cryptographic work. Though the agency issued no public statements, NSA officials apparently leaked that the they were worried that private institutions would publish unbreakable coding schemes that would be used by foreign governments to block NSA eavesdropping. Joseph A. Meyer, an NSA employee, sent a letter to a professional journal in which he warned that computer scientists who published cryptographic research might be violating the Munitions Control Act, and therefore illegal. Some researchers took this letter as a threat from the NSA. The Senate committee, however, concluded that Meyer had written the letter on his own and not under any instructions from his superiors at the NSA. The committee also concluded that the NSA was not guilty of any kind of harassment.(17)(18)

DES and Public Key Cryptography

Despite concerns over the possible lack of security, many companies adopted DES as instructed by the NBS. A few did not, including Bell Telephone Company, whose own researchers found it too unsecure. Tuchman and Meyer's team at IBM had worked hard to implement DES in inexpensive and easily-installed hardware, thus ensuring the economic feasability of the system. Diffie, Hellman, Rivest and others continued to develop public key cryptography, which would eventually become a major competitor to DES.(19)


Development of DES

Initially, the goal of the DES project was to develop an encryption system for Automated Teller Machines for Lloyd's Bank. While DES was still in development, however, the NBS published a request for proposals for a national standard for commercial cryptography. The NBS selected DES and asked that Tuchman and his team talk to the NSA in order to make sure that they were complying with laws barring the sale of weapons to foreign countries (this included codes). NSA officers explained that parts of the DES algorithms duplicated some of the NSA's own work, and so some of the mathematics would have to remain classified and unpublished. Tuchman and Meyer agreed not to publish parts of the algorithm, which raised objections from the academic community, including Martin Hellman, when the NBS held a seminar to discuss DES before officially making it a standard. Hellman and others objected to the confidentiality of DES as it prevented them from knowing if a mathematical "trapdoor" that bypassed the security algorithm had been included in the algorithm. They also argued that 56 bits was too few to ensure adequate security (Hellman calculated that it would cost $10,000 in hardware and computing time to break the encryption). A series of articles in major newspapers about the DES expressed concerns over collusion between IBM and the intelligence community and what that might mean for privacy. Tuchman argued against the allegations, and pointed out that the Senate Oversight Committee for the intelligence agencies investigated and found these charges to be false. As far as the trapdoor fears went, Tuchman later wrote that not only was there no trapdoor, but that he did not even understand how one could make a trapdoor in the encryption algorithms. As for the 56-bit key issue, Tuchman and Meyer examined exhaustion attacks from commercial computer and determined that no commercial attack would be feasible. This perhaps was a difference in opinion over the standards of commercial cryptography, as Tuchman also argued that commercial cryptography did not need to be held to as high a standard as military cryptography.(20)(21)

-- ThomasMisa - 30 May 2014

Notes

1 : Walter Tuchman, "A Brief History of the Data Encryption Standard" in Dorothy E. Denning and Peter J. Denning, eds., Internet Besieged: Countering Cyberspace Scofflaws (New York: ACM Press, 1998), 275-280.

2 , 5 , 9 , 14 , 15 : P Kinnucan, “Data Encryption Gurus: Tuchman and Meyer,” CRYPTOLOGIA 2, no. 4 (1978): 371–381.

3 , 7 , 8 , 10 , 12 : Gina Bari Kolata, “Computer Encryption and the National Security Agency Connection,” Science 197, no. 4302 (1977): 438–440

4 , 16 , 20 : Walter Tuchman, "A Brief History of the Data Encryption Standard" in Dorothy E. Denning and Peter J. Denning, eds., Internet Besieged: Countering Cyberspace Scofflaws, ACM Press New York (1998), 275-280

6 , 13 : W. Diffie and M.E. Hellman, “Special Feature Exhaustive Cryptanalysis of the NBS Data Encryption Standard,” Computer 10, no. 6 (1977): 74–84, doi:10.1109/C-M.1977.217750.

11 , 17 : Malcolm W. Browne, “Senate Panel Asks Role for Security Agency in Cryptography Grants,” New York Times, April 13, 1978

18 : Malcolm W. Browne, “Cryptography Is Too Good For Anyone’s Comfort,” New York Times, June 04, 1978

19 : Ernest Volkman, “Spying Motive Seen in U.S. Rule on Computer Security: Agency Reportedly Pushed for Inferior Standards to Get Capability to Tap Into Domestic System,” Los Angeles Times, October 26, 1977.

21 : Martin Hellman, OH 375. Oral history interview by Jeffrey R. Yost, 22 November 2004, Palo Alto, California. Charles Babbage Institute, University of Minnesota, Minneapolis.


Edit | WYSIWYG | Attach |  PDF |  History: r15 | r7 < r6 < r5 < r4 |  Backlinks |  Raw View | More topic actions...
Topic revision: r5 - 30 May 2014 - 16:43:15 - ThomasMisa
 
Signed in as lewi0740 (NicLewis) | Sign out
UMWiki UMWiki
This site is powered by FoswikiCopyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding UMWiki? Send feedback