Data Encryption Standard
|Certification||as FIPS PUB 46 through NBS|
|Key length||56 bits|
|Block size||64 bit|
|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).
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.
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. "
|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's “ Deep 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|
|March||2006||The FPGA-based parallel computer COPACOBANA costs less than $ 10,000 (material costs) and breaks DES in less than 9 days|
|Nov||2008||The further development of the FPGA-based parallel computer COPACOBANA, the RIVYERA, breaks DES for the first time in less than a day|
DES is a symmetrical algorithm , which means that the same key is used for encryption and decryption. DES works as a block cipher , so each block is individually encrypted using the key, with the data being "scrambled" in 16 iterations or rounds of substitutions and transpositions ( permutation ) according to Feistel's scheme . The block size is 64 bits, i.e. a 64-bit block of plain text is transformed into a 64-bit block of ciphertext . The key that controls this transformation also has 64 bits. However, of these 64 bits, only 56 bits are available to the user; the remaining 8 bits (one bit from each byte ) are required for the parity check . The effective key length is therefore only 56 bits. The decryption is carried out with the same algorithm, with the individual round keys being used in reverse order.
An initial permutation is applied to the 64-bit block. Then the block is divided into two parts and each part is stored in a 32-bit register. The two halves of the block are referred to as the left and right halves (see sketch). The Feistel function is applied to the right half of the block . Then the right half is XORed with the left half and the result is saved in the register of the next round for the right half. The original right half of the block is copied into the left register of the next round. After the end of the last round, the two halves are merged and a final permutation is carried out. This is the inverse permutation to the initial permutation.
The DES algorithm initially only describes how a data block with 64 bits is processed. Like any other block cipher, the DES can be used in various operating modes to process a message of any length . For certain operating modes, such as ECB or CBC , the plain text must be filled up to a multiple of the full block length ( padding ). This is done by adding the bit sequence 1000….
The Feistel function
The DES F function works on half-blocks of 32 bits each and consists of four phases:
- The R blocks are expanded to a length of 48 bits by means of a suitable permutation E ( expansion ) by using individual bits several times.
- The result is XOR-linked with a partial key. For each round, a different 48-bit partial key is generated from the main key according to a fixed rule.
- The resulting blocks are divided into eight 6-bit pieces and these are compressed to a length of 4 bits by substituting S-boxes. This non-linear transformation in the S-boxes represents the heart of the security of DES, without it it would be linear and trivial to break DES.
- The 32 bits output of the S-boxes are rearranged using a fixed permutation P.
This combination of permutations and substitutions corresponds to the principle of diffusion and confusion established by Claude Shannon .
In order to expand the half-block in the Feistel function from 32 bits to 48 bits, the half-block is divided into 4-bit groups. The bits at the edge of each 4-bit group are appended to the front or back of the neighboring 4-bit group.
The substitution boxes ( S-boxes ) at DES are standardized. To get the output value from the following tables, the input value is split. The first and last bit together form the row, and the column is made up of the remaining bits (see example ). Changing these boxes drastically reduces security! Therefore, the following tables should be used for the substitution boxes:
|S 1||Middle 4 bits of the input value|
|S 2||Middle 4 bits of the input value|
|S 3||Middle 4 bits of the input value|
|S 4||Middle 4 bits of the input value|
|S 5||Middle 4 bits of the input value|
|S 6||Middle 4 bits of the input value|
|S 7||Middle 4 bits of the input value|
|S 8||Middle 4 bits of the input value|
Because the key length is only 56 bits, DES has already been broken by brute force attacks by systematically testing all possible keys (2 56 = approx. 72 quadrillion ). There is the assumption that this small key length was chosen on purpose because the NSA already had enough computing capacity in the 1970s to break this encryption.
In 1998, the EFF built a machine called "Deep Crack" that cost around $ 250,000. This supercomputer contained 1,536 special crypto chips and could test around 88 billion keys per second. In July 1998 this machine succeeded in cracking a DES code in 56 hours and thus winning the "DES Challenge II-2", which was advertised by the company RSA Security . In 1999 the same machine won the "DES Challenge III"; To do this, she worked with the worldwide network of distributed.net , consisting of around 100,000 computers . The DES key was found in 22 hours and 15 minutes, with more than 245 billion keys being tested per second.
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.
DES has a complement property, that is, it holds
- for all keys and all plain texts ,
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.
There are four weak keys with the property that
- for all plaintexts .
There are also six semi-weak key pairs with the property that
- for all plaintexts .
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.
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.
To this day, DES is used for the voice encryption of security-critical radio broadcasts. In Germany, users include various special police units as well as the federal and state authorities for the protection of the constitution. For this purpose, two-way radios from Motorola from the MX3000 and MTS2000 series are widespread. The speech is digitized by means of delta modulation and passed through a certified plug-in module inside the radio for encryption. The module is protected against manipulation, the key cannot be read out and is deleted if manipulation attempts. Even when using relay points to increase the range, the concept is such that the signal is never unencrypted inside the relay point. The key management is either decentralized with direct access to the device with a so-called key variable loader (KVL), or via radio centrally from a key management center via OTAR, "Over The Air Rekeying". For this application, DES is more than sufficiently secure according to the current state of the art, provided that the keys are changed for every incident (or regularly during longer missions), since the spoken word is only relevant for the other side in such cases. A possible decryption after hours or days is usually irrelevant for the application, since then "everything is already running". Both the relatively high technical effort and the required specialist knowledge also reduce the likelihood that an attempt will actually be made to decrypt the radio communication later.
The US export restriction for the DES with full 56-bit key length has been lifted.
Due to its short key length, DES was soon no longer sufficiently secure and a replacement had to be found.
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 :
This procedure is also known as EDE (Encrypt-Decrypt-Encrypt). A simple DES encryption is therefore a special case of 3DES:
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.
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.
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).
- 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.
- DES and TripleDES specification of the NIST (English, PDF; 179 kB)
- Simple description of DES with graphics
- Detailed representation of DES
- COPACOBANA - A cost-optimized special hardware for code cracking from the Universities of Bochum and Kiel (English)
- Standard Cryptographic Algorithm Naming to DES
- ^ 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
- ↑ 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 .
- ↑ 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.
- ↑ 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.
- ^ 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 .
- ^ 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 archives ) Info: The link was automatically marked as defective. Please check the link according to the instructions and then remove this notice.
- ^ 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 archives ) Info: The link was automatically marked as defective. Please check the link according to the instructions and then remove this notice.
- ↑ 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 .
- ↑ cryptography.com
↑ 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.
- ^ Alfred H. Menezes, Paul C. van Oorschot, Scott A. Vanstone, "Handbook of Applied Cryptography", CRC Press, 1996, ISBN 0-8493-8523-7 .
- ↑ 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 .
- ^ 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 .
- ↑ 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.
- ^ RC Merkle, ME Hellman, "On the Security of Multiple Encryption," Communications of the ACM, Vol. 24, No. 7, July 1981.
- ↑ KW Campbell, MJ Wiener: "DES is not a group", Advances in Cryptology - CRYPTO '92 (LNCS 740), Springer-Verlag, 1993, pages 512-520.
- ↑ 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.
- ↑ 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)).