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 < r14 < r13 < r12 < r11
[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 14)

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)

Technical Overview

Figure 1: Feistel encryption Figure 2: DES encryption function
DES is a symmetric key Feistel block cipher. A symmetric key means that the same key used for encrypting the data is the same used to decrypt it, analogous to how you lock and unlock most doors with the same key. The key, in this case, is a random string of 64 bits (only 7 in 8 are used for encryption, hence a 56-bit encryption). A Feistel block cipher uses a publicly-known list of functions, (f1 f2 ... f2k), a secret key (k) and a message broken into smaller fixed-length pieces called blocks (m1 ... mn) to create a symmetric-key encryption. Each block is cut in half, into a left and right side. These sides are iteratively run through the functions, then combined with an exclusive-or function. The left side only passes through the odd-numbered functions, likewise with the right and even-numbered functions. At the end, the sides exchange position, and are recombined. Figure 1 illustrates this process.

The effect of this is that the original message has been obfuscated, and can be sent securely: it is impossible to decode it without the secret key, and guessing the key (in the 1970's) was prohibitively time-consuming. The message can be decoded by applying the Feistel cipher again with the order of the functions reversed (f2k, f2k-1 ... f1) with the same secret key (k).

In the case of DES, there are 8 S-boxes that serve as the Feistel function (Figure 2). The 32-bit half of the block is partitioned into eight 4-bit pieces, mixed with the key using exclusive-or, and then run through the S-box functions, which take in 6 bits and output 4 bits. An additional, fixed permutation function after the S-boxes scrambles the bits further. This particular Feistel function was later revealed to be resistant to a certain statistical attack, improving the security of DES.(2)

Development of DES

DES grew out of an IBM project (code-named Lucifer) to develop a secure encryption system for Automatic Teller 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.(3)

As Lucifer neared completion at IBM, the NBS made a request for proposals for a national standard for commercial cryptography. Subsequently IBM directed Tuchman, Meyer, and the rest of the Lucifer team to work on what became DES. Beginning in 1971, the team worked for six years on the algorithm and its implementation. The basic idea was that two users who wanted to communicate would each have an encryption device connected between their modem and their computer. One user would pick an encryption key that would 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 securely share data or messages. 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 to expose a weakness. The validation process can be lengthy because it is difficult to 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 to perform an analysis of DES, during which the NSA told Tuchman and Meyer that their work had duplicated some NSA efforts, and that parts of it would therefore need to be classified. The NSA probably asked Tuchman and Meyer to reduce their 128-bit key to 56 bits, as alleged by several computer scientists at Bell Laboratories and further suggested by a Senate Select Intelligence Committee report.(4) 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."(5)(6)(7)

Controversy

The NSA's involvement with DES and the perceived weakness of its 56-bit key led to significant controversy. Computer scientists, primarily at Stanford University, the Massachusetts Institute of Technology, and Bell Laboratories, strongly criticized the way that DES had been developed and the security of the algorithm itself. Two particular criticisms were repeatedly voiced. The first was that the 56-bit key was too short to be considered secure. Furthermore, the secrecy of the development documentation meant there was no way to tell whether 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, intelligence agencies such as the NSA would have both the means and the motive to build such a computer. Furthermore, the cost of building such a machine would certainly decrease, so 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 was limited to 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 readily read DES-encoded messages.(8)(9)

Supporters of DES, particulalry IBM's Tuchman, responded vigorously to such criticisms. In response to the concerns, the NBS held two workshops in August and September 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 -- 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.(10)

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 users could simply encode messages, twice, to effectively double the key length to 112 bits.(11)

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 got federal research grants for cryptographic work.(12)(13)

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 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 it was not recorded how Tuchman responded.(14)(15)(16)

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 Senate report also found no collusion between IBM and the NSA. (17)(18)

Dickie George, technical director of NSA’s information assurance directorate, explained the agency's role in DES during a presentation to the RSA Security Conference in 2011. At the time, NSA asked IBM to make certain changes in the Substitution boxes, or S-boxes, that the algorithm uses for security. “We had to change the S-boxes,” to make them able to withstand practical attacks, George stated. “We didn’t see any need to change anything else.” (19)

The presence or non-presence of such government-installed trap doors is not easy to resolve. A controversy in 2010 developed over the FBI's allegedly having installing back-door access to the Unix-based OpenBSD operating system. A former FBI consultant stated that a backdoor was installed in the open-source software -- specifically in the IPSEC stack that supports VPNs so that an eavesdropper might decipher VPN traffic -- although the person named as the responsible programmer strongly denied having done so.(20)

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 warning that computer scientists who published cryptographic research might be violating the Munitions Control Act. 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.(21)(22)

DES and Public Key Cryptography

Despite the controversy, 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 implemented DES using inexpensive and easily-installed hardware, thus ensuring the economic feasibility of the system. Diffie, Hellman, Rivest and others continued to develop public key cryptography, which would eventually become a major competitor to DES.(23)

DES survived for many years as a security standard, in the modified form of Triple DES, until 2001 when it was replaced by by the Advanced Encryption Standard.

-- ThomasMisa - 30 May 2014

Notes

1 , 6 , 18 : 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 : Images and DES details: Ross Anderson, Security Engineering, 2nd Edition: http://www.cl.cam.ac.uk/~rja14/Papers/SEv2-c05.pdf

3 , 11 , 16 , 17 : P Kinnucan, “Data Encryption Gurus: Tuchman and Meyer,” Cryptologia 2 no. 4 (1978): 371–381.

4 : http://www.intelligence.senate.gov/pdfs/95nsa.pdf

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

7 : P Kinnucan, “Data Encryption Gurus: Tuchman and Meyer,” Cryptologia 2 no. 4 (1978): 371–381.

8 : 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.

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

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

15 : 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.

19 : William Jackson, "NSA reveals its secret: No backdoor in encryption standard," Government Computing News Feb 16, 2011 http://gcn.com/articles/2011/02/16/rsa-11-nsa--no-des-backdoor.aspx

20 : William Jackson, "FBI accused of installing backdoor in OpenBSD operating system," Government Computing News Dec 15, 2010 http://gcn.com/articles/2010/12/15/openbsd-backdoors-fbi.aspx

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

23 : 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.


Topic attachments
I Attachment Action Size Date Who Comment
pngpng DES-S-Box.png manage 39.9 K 12 Mar 2015 - 13:28 UnknownUser DES S-Box Encryption function
pngpng Feistel.png manage 43.8 K 12 Mar 2015 - 13:02 UnknownUser Feistel cipher image
pdfpdf NIST-on-economic-impact-DES_report01-2.pdf manage 689.5 K 21 Jul 2014 - 16:15 ThomasMisa NIST report on positive economic impact of DES
Edit | WYSIWYG | Attach |  PDF |  History: r15 < r14 < r13 < r12 < r11 |  Backlinks |  Raw View | More topic actions...
Topic revision: r14 - 12 Mar 2015 - 13:33:03 - sever408
 
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