Data Encryption Standard

OF
A Feistel lap (F function)
developer IBM
Released 1975
Derived from Lucifer
Certification as FIPS PUB 46 through NBS
Key length 56 bits
Block size 64 bit
structure Feistel cipher
Round 16
Best known cryptanalysis
The best analytical attack is the linear cryptanalysis with 2 43 known plaintext blocks. Brute force attacks find the key used after a few hours.

The Data Encryption Standard ( DES ; German  "data encryption standard " ) is a widely used symmetrical encryption algorithm .

The DES algorithm was confirmed as the official standard for the US government (see FIPS 46) in 1977 and has been widely used internationally since then. Its history has repeatedly given rise to speculation about its security due to the involvement of the NSA in the design of the algorithm . Today DES is not considered to be sufficiently secure for many applications due to the key length of only 56  bits used .

However, the key length can easily be increased by using the DES multiple times. As Triple-DES, also known as TDES, 3DES or DESede, the DES is still most frequently used, for example by banks in chip card applications, although the TDES has been replaced as the official standard for the USA by the Advanced Encryption Standard (AES).

history

At the beginning of the 1970s, military cryptology was at a high level, but hardly any useful products were available for non-military applications. The US National Bureau of Standards (NBS) - now the National Institute of Standards and Technology (NIST) - saw a need for a uniform standard for the encryption of confidential data across all agencies. After consulting with the NSA, on May 15, 1973, it published a tender in the Federal Register . In particular, the security of the algorithm according to Kerckhoffs' principle should only depend on the secrecy of the key , but not on the secrecy of the algorithm. However, none of the submitted candidates met the requirements, which led to a new call on August 27, 1974.

IBM made a promising proposal based on a further development of the “ Lucifer ” algorithm developed a few years earlier with the collaboration of Horst Feistel . This algorithm was characterized by the fact that it used simple logical operations on small groups of bits and was therefore easy to implement in hardware. In addition to Feistel himself, Walter Tuchman , Don Coppersmith , Alan Konheim , Carl Meyer, Mike Matyas, Roy Adler, Edna Grossman , Bill Notz, Lynn Smith and Bryant Tuckerman were also members of the IBM development team.

The role of the NSA

NBS and IBM decided to cooperate with the support of the National Security Agency (NSA). What influence the NSA had on the development of the algorithm is controversial. Above all, the key length of 56 bits and the design of the " S-boxes " responsible for substitution gave rise to speculation about possible back doors that the NSA might introduce. According to its own information, the NSA strengthened the S-boxes against differential cryptanalysis , but at the same time wanted to limit the key length to 48 bits, while IBM wanted 64 bits. As a compromise, NSA and IBM agreed on a key length of 56 bits.

On March 17, 1975, the algorithm was published in the Federal Register. The NBS also asked for public opinion. The following year two workshops were held on the proposed standard. Due to the unclear role of the NSA, the changes to the algorithm drew criticism from various sides, including from the pioneers of asymmetric cryptosystems Martin Hellman and Whitfield Diffie . It was speculated that the NSA had built in a back door that weakened the process in such a way that it could read encrypted messages with it. Alan Konheim, one of the DES developers, stated that he had sent the S-boxes to Washington and received them back in a greatly modified form.

A Senate intelligence committee investigated the NSA's influence. In the not as classified information handled summary of the report they gave in 1978 to:

“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. [...]
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. "

“During the development of DES, the NSA convinced IBM that a reduced key length was sufficient; indirectly helped with the construction of the S-boxes; and certified the resulting DES algorithm as free of statistical and mathematical weaknesses to the best of our knowledge. […]
The NSA did not change the design of the algorithm in any way. IBM designed and developed it, made all relevant decisions, and agreed that the shortened key length was more than adequate for its intended commercial uses. "

Walter Tuchman, another DES developer, is quoted as saying “We developed the DES algorithm entirely within IBM using IBMers. The NSA did not dictate a single wire! " (German: "We developed the DES algorithm entirely within IBM using IBMers. The NSA did not dictate a single memo!").

The publication of Differential Cryptanalysis by Adi Shamir and Eli Biham in 1990 dispelled some of the backdoor fears. DES proved to be significantly more resistant to this generic attack method due to the design of the S-boxes than would have been the case with a random arrangement. In 1994 Don Coppersmith published the original design criteria for the S-boxes. It turned out that IBM had already discovered differential cryptanalysis in the 1970s and had been instructed by the NSA to maintain secrecy after the S-boxes were redesigned.

Coppersmith stated "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." (German: "this happened because the [differential cryptanalysis] can be a powerful tool against many procedures and there were concerns that national security could be endangered by its publication.").

Shamir himself commented "I would say that, contrary to what some people believe, there is no evidence of tampering with the DES so that the basic design was weakened." (German: "Contrary to what some believe, I myself see no evidence of manipulation of DES, which has weakened the basic design." )

The criticism of the length of the key persisted, however, and was further supported by the NSA's reasoning that 8 of the 64 key bits could be used as parity bits . It is widely believed that the reduction in NSAs was intended to create the possibility of a brute force attack.

Today, the DES is no longer considered secure enough due to its short key length. Multiple use of DES with different keys, such as TDES, can increase the effective key length.

Scientific studies have meanwhile shown that DES, despite its key length of only 56 bits, is more secure than the Lucifer algorithm with its 128 bits.

standardization

DES was approved as a standard for all American federal agencies and published as FIPS PUB 46 on January 15, 1977 ; it became mandatory for them six months later. The standard contained the requirement to have to be reconfirmed every five years. The International Organization for Standardization (ISO) also dealt with the algorithm under the name Data Encipherment No. 1 (DEA1).

In 1981 the American National Standards Institute (ANSI) recognized the DES algorithm as the standard for the private sector.

As early as the early 1990s, cryptographers expressed their first doubts as to whether the DES algorithm could still be viewed as secure. On the one hand, the hardware had developed a lot compared to 1970; on the other hand, it was believed that weaknesses in the algorithm were also recognized. In 1994 a theoretical attack using linear cryptanalysis was published. In mid-1998 the Electronic Frontier Foundation (EFF) carried out a successful attack using the brute force method . The company built special hardware for this with a total of over 1,800 microprocessors and was able to break a key in less than three days. Work on the successor standard AES had already started at this point. On May 26, 2002, DES was finally replaced by AES.

The introduction of DES is considered to have triggered a large number of cryptographic studies, especially those that deal with the attack on block ciphers. Bruce Schneier writes in his book "Applied Cryptography":

“Unofficially, the NSA identified DES as one of its biggest mistakes. Had the agency known the details were out and software implementations were possible, they would never have approved. DES revolutionized all cryptanalysis more than anything else. Now there was an algorithm to investigate - even one that the NSA called safe. "

chronology

date event
May 15 1973 The NBS publishes a first call for tenders for a standardized encryption method
August 27 1974 The NBS publishes a second invitation to tender for a standardized encryption method
17. March 1975 DES is published in the Federal Register
August 1976 First workshop on DES
September 1976 Second workshop, which deals with the mathematical basics of DES
November 1976 DES is approved as a standard
15. January 1977 DES is published as the FIPS standard “FIPS PUB 46”
1983 DES is reconfirmed for the first time
1986 VideoCipher II, a system based on DES encryption system for television satellites from the HBO used
22nd of January 1988 DES is being revalidated as "FIPS 46-1", which replaces FIPS PUB 46
1992 Biham and Shamir publish the first theoretical attack with reduced complexity compared to the brute force method : differential cryptanalysis. However, this attack requires unrealistic 2 47 freely chosen plaintexts.
30th of December 1993 DES is confirmed a third time, this time as "FIPS 46-2"
1994 The first experimental cryptanalysis of DES is carried out using linear cryptanalysis (Matsui, 1994)
June 1997 The DESCHALL project publicly breaks a message encrypted with DES for the first time
July 1998 The Electronic Frontier Foundation'sDeep Crack ” DES cracker breaks a DES key within 56 hours
January 1999 Deep Crack and distributed.net work together to break a DES key in 22 hours and 15 minutes
October 25 1999 DES is confirmed a fourth time in the form of "FIPS 46-3". This specifies 3DES as the preferred application and allows DES itself only for use in outdated systems
November 26th 2001 The Advanced Encryption Standard (AES) is published as "FIPS 197"
May 26 2002 The AES comes into force
July 26th 2004 The "Federal Register" recommends the removal of FIPS 46-3 and related standards
May 19th 2005 NIST is overriding FIPS 46-3

COPACOBANA

The only other publicly known machine for breaking DES is COPACOBANA . It was built in 2006 by two working groups at the Universities of Bochum and Kiel . In contrast to Deep Crack, a COPACOBANA consists of reconfigurable hardware components, so-called FPGAs . 120 XILINX Spartan3-1000 FPGAs are combined in a machine on 20 DIMM modules, each DIMM module containing six FPGAs. COPACOBANA can test 65 billion DES keys per second, resulting in an average search time of 6.4 days for a DES attack. By using reconfigurable hardware, COPACOBANA can also be used to break other ciphers such as A5 . COPACOBANA's material and manufacturing costs are approximately \$ 10,000. The cost advantage over Deep Crack by a factor of 25 is an impressive example of Moore's Law . According to this, a cost advantage of around 32 = 2 5 would have been expected, since eight years have passed between the construction of the two machines (Moore's law predicts that the cost of digital ICs will halve every 1.5 years, so that with eight years around 5 Halving should have taken place).

The current record was set in 2008 by SciEngines GmbH (a spin-off of the COPACOBANA working groups) and improved again at a workshop in 2009. With 128 Xilinx FPGAs, the throughput was over 292 billion keys per second.

Minor weaknesses

DES has a complement property, that is, it holds

${\ displaystyle \ operatorname {DES} _ {K} (m) = {\ overline {\ operatorname {DES} _ {\ overline {K}} ({\ overline {m}})}}}$for all keys and all plain texts ,${\ displaystyle K}$${\ displaystyle m}$

where denotes the bitwise complement of . This can be a chosen-plaintext attack at a complete key search, the search space on 2 55 key halved. ${\ displaystyle {\ overline {x}}}$${\ displaystyle x}$

There are four weak keys with the property that ${\ displaystyle K}$

${\ displaystyle \ operatorname {DES} _ {K} (\ operatorname {DES} _ {K} (m)) = m}$for all plaintexts .${\ displaystyle m}$

There are also six semi-weak key pairs with the property that ${\ displaystyle (K_ {1}, K_ {2})}$

${\ displaystyle \ operatorname {DES} _ {K_ {1}} (\ operatorname {DES} _ {K_ {2}} (m)) = m}$for all plaintexts .${\ displaystyle m}$

In practice, however, this is not a problem, since the probability of a (semi-) weak key if a key is selected at random is only 16: 2 56 . In addition, the use of these keys can easily be avoided by explicitly ignoring them during generation.

Applications

The DES algorithm is widely used in ATMs : With the help of the DES algorithm and a secret key , a so-called PAC is calculated on the keyboard . This is sent together with the data on the magnetic stripe ( account number , bank code , period of validity, ...) to the host of the bank holding the account, where the PIN is decrypted and verified.

In the early days of ATMs, the PIN was calculated from the data on the magnetic strip (account number, bank code, validity period, ...) and the secret key and the result was compared with the user's input. This so-called offline PIN check has not been used for several years.

The US export restriction for the DES with full 56-bit key length has been lifted.

Replacement algorithms

Due to its short key length, DES was soon no longer sufficiently secure and a replacement had to be found.

Triple DES

The first replacement for DES was Triple-DES (also called 3DES or DESede ). The idea of ​​executing DES multiple times with two different keys is a procedure that was described and analyzed by DES co-developer Walter Tuchman (see FIPS 46-3). After a further analysis, Ralph Merkle and Martin Hellman proposed triple encryption with three independent, different keys in 1981.

In the most common method, each block of data is encrypted with a DES key , then decrypted with and encrypted with : ${\ displaystyle K_ {1}}$${\ displaystyle K_ {2}}$${\ displaystyle K_ {3}}$

${\ displaystyle \ operatorname {3DES} _ {(K_ {1}, K_ {2}, K_ {3})}: = \ operatorname {DES} _ {K_ {3}} \ circ \ operatorname {DES} _ { K_ {2}} ^ {- 1} \ circ \ operatorname {DES} _ {K_ {1}}}$

This procedure is also known as EDE (Encrypt-Decrypt-Encrypt). A simple DES encryption is therefore a special case of 3DES:

${\ displaystyle \ operatorname {3DES} _ {(K, K, K)} = \ operatorname {DES} _ {K}}$

An important mathematical problem for the encryption strength of 3DES was the question of whether the sequential execution of DES operations increases the security; this would not be the case if DES is a group . Campell and Wiener found that the set of DES ciphers is not complete under sequential execution . This means that key and is so for all keys . In other words, the number of permutations of the shape is significantly greater than the number of permutations. This actually increases the effective key length. However, this could only be shown in 1992. ${\ displaystyle \ operatorname {DES} _ {K}}$${\ displaystyle K_ {1}}$${\ displaystyle K_ {2}}$${\ displaystyle \ operatorname {DES} _ {K_ {2}} \ circ \ operatorname {DES} _ {K_ {1}} \ neq \ operatorname {DES} _ {K}}$${\ displaystyle K}$${\ displaystyle \ operatorname {DES} _ {K_ {2}} \ circ \ operatorname {DES} _ {K_ {1}}}$${\ displaystyle \ operatorname {DES} _ {K}}$

The key length of 3DES is 168 bits, three times as long as DES (56 bits), but the effective key length is only 112 bits. This is due to the possibility of a so-called meet-in-the-middle attack : If the attacker is in possession of a pair of plain text and cipher, he can attack the encryption from both sides. The plain text is encrypted with all possible keys for level 1 (2 56 possibilities). The texts created in this way are also decrypted with all possible keys for level 2 (2 112 possibilities). The results are compared with the results of the decryption of the ciphertext with all keys (2 56 possibilities). In total, only 2 112 +2 56 encryption or decryption must be carried out, instead of 2 168 when using the brute force method.

Because of this mismatch between key length and effective security level, a choice is often made . For a key length of 112 bits, this provides a theoretical security level of 112 bits, since no meet-in-the-middle attack is possible. However, other attacks exist, so two-key 3DES is rated by the National Institute of Standards and Technology with a security level of 80 bits. ${\ displaystyle K_ {1} = K_ {3}}$

AES

In a competition organized by NIST in October 2000, the Advanced Encryption Standard (AES) was chosen to officially replace DES. The encryption method now known as AES, which won the competition, had been submitted to this competition by its Belgian developers Vincent Rijmen and Joan Daemen under the name Rijndael .

3DESE - Triple DES in the field of PPP

The protocol extension 3DESE (Triple-DES Encryption Protocol Extension) defined in RFC 2420 enables the usual Triple-DES encryption via PPP (Point-to-Point Protocol).

literature

• Bruce Schneier : Applied Cryptography. Protocols, Algorithms, and Source Code in C. 2nd edition. John Wiley and Sons, New York NY 1996, ISBN 0-471-11709-9 .
• Bruce Schneier: Applied Cryptography. Protocols, algorithms and source code in C. Addison-Wesley, Bonn a. a. 1996, ISBN 3-89319-854-7 , p. 267 ( information security ).
• Klaus Schmeh : Code breakers versus code makers. The fascinating story of encryption. 2nd Edition. W3l-Verlag, Herdecke u. a. 2008, ISBN 978-3-937137-89-6 , pp. 263-274.
• Dossier cryptography. In: Spectrum of Science . 24, 4, 2001, pp. 42-47.

Individual evidence

1. ^ Tom R. Johnson: American Cryptology during the Cold War, 1945-1989 . Book III: Retrenchment and Reform, p. 232. NSA , DOCID 3417193, FOIA publication on cryptome.org, December 18, 2009; Retrieved January 2, 2010
2. Bruce Schneier: Applied Cryptography . Protocols, Algorithms and Source Code in C. 2nd edition. John Wiley & Sons, New York 1996, ISBN 0-471-11709-9 , pp. 280 .
3. Unclassified Summary: Involvement of NSA in the Development of the Data Encryption Standard (PDF) United States Senate Select Committee on Intelligence. S. 55. November 1978. Archived from the original on December 18, 2015. Info: The archive link was automatically inserted and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. Retrieved August 6, 2010.
4. Paul Kinnucan: Data encryption gurus: Tuchman and Meyer . (PDF) In: Cryptologia . 2, No. 4, October 1978, pp. 371-381. doi : 10.1080 / 0161-117891853270 . Retrieved August 6, 2010.
5. ^ Eli Biham, Adi Shamir: Differential cryptanalysis of DES-like cryptosystems . (PDF) In: Journal of Cryptology . 4, No. 1, January 1991, pp. 3-72. doi : 10.1007 / BF00630563 .
6. ^ Don Coppersmith: The Data Encryption Standard (DES) and its strength against attacks . (PDF) In: IBM Journal of Research and Development . 38, No. 3, May 1994, p. 243.  ( Page no longer available , search in web archivesInfo: The link was automatically marked as defective. Please check the link according to the instructions and then remove this notice.
7. ^ Don Coppersmith: The Data Encryption Standard (DES) and its strength against attacks . (PDF) In: IBM Journal of Research and Development . 38, No. 3, May 1994, p. 247.  ( Page no longer available , search in web archivesInfo: The link was automatically marked as defective. Please check the link according to the instructions and then remove this notice.
8. Ishai Ben-Aroya, Eli Biham: Differential cryptanalysis of Lucifer . In: Journal of Cryptology . 9, No. 1, March 1996, pp. 21-34. doi : 10.1007 / BF02254790 .
9. cryptography.com
10. Bruce Schneier: Applied Cryptography, Protocols, Algorithms, and Source Code in C . 2nd Edition. John Wiley and Sons, New York 1996, p. 267
Applied cryptography, protocols, algorithms and source code in C, Pearson Studium, 2006.
11. ^ Alfred H. Menezes, Paul C. van Oorschot, Scott A. Vanstone, "Handbook of Applied Cryptography", CRC Press, 1996, ISBN 0-8493-8523-7 .
12. Bruce Schneier: Applied Cryptography . Protocols, Algorithms and Source Code in C. 2nd edition. John Wiley & Sons, New York 1996, ISBN 0-471-11709-9 , pp. 274 .
13. ^ Klaus Irmscher: DES - Data Encryption Standard. (PDF; 42 kB) University of Leipzig, 2009, archived from the original on November 4, 2009 ; Retrieved March 18, 2010 .
14. Break DES in less than a single day ( Memento of the original from April 24, 2010 in the Internet Archive ) Info: The archive link was automatically inserted and not yet checked. Please check the original and archive link according to the instructions and then remove this notice. Press website of the company on the workshop results 2009.
15. ^ RC Merkle, ME Hellman, "On the Security of Multiple Encryption," Communications of the ACM, Vol. 24, No. 7, July 1981.
16. KW Campbell, MJ Wiener: "DES is not a group", Advances in Cryptology - CRYPTO '92 (LNCS 740), Springer-Verlag, 1993, pages 512-520.
17. Eli Biham : How to Forge DES-Encrypted Messages in 2 28 Steps ( Memento of the original from December 10, 2005 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. ( PostScript ), 1996.
18. Elaine Barker, William Barker, William Burr, William Polk, Miles Smid: NIST Special Publication 800-57 . Recommendation for Key Management - Part 1: General (Revision 3). Ed .: National Institute of Standards and Technology (=  NIST Special Publications ). 2012, Section 5.6.1 Comparable Algorithm Strengths, p. 64 ( nist.gov (PDF)).