Data Encryption Standard

The Data Encryption Standard (DES) is a widely used symmetric encryption algorithm.

The DES algorithm has been as an official standard for the U.S. government ( see FIPS 46) in 1976 and has since been confirmed in many cases internationally. Its history has repeatedly given rise to speculation about his safety because of the involvement of NSA in the design of the algorithm. Today, DES is considered not safe enough for many applications due to the used key length of only 56 bits.

The key length can be easily increased by multiple application of DES, however. As a Triple-DES, also known as TDES, 3DES or DESede referred, the DES is still the most common, for example by banks in smart card applications used, although the TDES was replaced as the official standard for the United States by the Advanced Encryption Standard (AES).

• 2.1 operating Modes

• 3.1 The expansion
• 3.2 The substitution

• 4.1 Deep Crack
• 4.2 COPACOBANA
• 4.3 Minor weaknesses

• 6.1 Triple-DES
• 6.2 AES

History

At the beginning of the 1970s was indeed the military cryptology at a high level, however, were hardly useful products available for non-military applications. The National Bureau of Standards (NBS ) in the USA - now the National Institute of Standards and Technology (NIST ) - saw a need for a uniform standard for the inter-agency encrypting sensitive data. After consulting with the NSA published on 15 May 1973 at the American " Federal Register " a tender. In particular, the security of the algorithm according to Kerckhoffs ' principle should depend only on the secrecy of the key, but not on the secrecy of the algorithm. However, none of the candidates submitted met the conditions imposed, which led to a renewed call for tenders on 27 August 1974.

IBM delivered a promising proposal, which was based on a further development of the developed few years earlier with the assistance of Horst Feistel algorithm "Lucifer ". This algorithm was distinguished by the fact that he took advantage of simple logic operations on small groups of bits, and thus was easily implemented in hardware. Besides Feistel even Walter Tuchman, Don Coppersmith, Alan Konheim, Carl Meyer, Mike Matyas, Roy Adler, Edna Grossman, Bill Notz, Lynn Smith and Bryant Tuckerman were 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 does the NSA had on the development of the algorithm, is controversial. Above all, the key length of 56 bits and the design of the relevant substitution for " S-boxes " gave rise to speculation about possible backdoors that may have been introduced by the NSA. According to information from the NSA strengthened the S-boxes to differential cryptanalysis, but simultaneously wanted to limit the key length to 48 bits, while IBM was 64 bits. As a compromise to 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 comment. The following year, two workshops were held on the proposed standard. Due to the unclear role of the NSA, the changes of the algorithm from different sides criticism attracted to itself, among other things, of the pioneers of asymmetric cryptosystems Martin Hellman and Whitfield Diffie. It has been speculated that the NSA had a backdoor, which weakens the process in such a way that they were able to read encrypted messages. Alan Konheim, one of the DES- developers stated to have sent the S-boxes to Washington and get back greatly changed.

An intelligence committee of the U.S. Senate investigated the influence of the NSA. In the not handled as classified summary of the report they gave in 1978:

"In the development of DES, NSA Convinced IBM did a Reduced key size what Sufficient; Indirectly assisted in the development of the S -box structures; certified and did the final DES algorithm which, 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 did the Agreed upon key size which more than adequate for all commercial applications For Which the DES which Intended. "

"During the development of DES, the NSA IBM convinced them that a reduced key size was sufficient; indirectly helped in the construction of S-boxes; and certified the resulting DES algorithm as in all conscience free from statistical and mathematical weaknesses. [ ... ] The NSA changed the design of the algorithm in any way. IBM designed and developed this met all relevant decisions and agreed that the shortened key length is more than adequate for the intended commercial uses. "

Walter Tuchman, another DES- developer, with the words "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 from the NSA did not dictate a single line. "! ) Quotes.

Through the publication of differential cryptanalysis by Adi Shamir and Eli Biham in 1990 some of the fears of a back door were out of the way. DES showed significantly more resistant to this generic attack method, as this would have been the case with a random arrangement through the design of S-boxes. Published in 1994, Don Coppersmith, the original design criteria for the S-boxes. It turned out that IBM had discovered the differential cryptanalysis already in the 1970s and had been instructed by transformation of the S-boxes of the NSA to secrecy.

Copper Smith said "that what Because [ differential cryptanalysis ] can be a very powerful tool, used against many schemes, and there what concern did seeking 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 compromised by disclosure. ").

Shamir himself commented " I would say that, contrary to what some people believe, there is no evidence of tampering with the DES so did the basic design which Weakened. " ( German: "Different than some people think, I see no evidence of self- manipulation of DES, which has weakened the basic design. " )

However, the criticism of the length of the key remained and was the justification for the NSA, 8 of the 64 key bits could be used as parity bits, further supported. It is widely believed that the reduction of the NSA should create the possibility of an attack with the brute- force method.

Today, the DES is no longer considered secure enough due to its small key size. A "problem", but which can be easily solved by the multiple application of the DES with different keys such as the TDES.

Scientific research has now proven that DES safer despite its key length of only 56 bits is known as the Lucifer algorithm with its 128 bits.

Standardization

DES was approved as a standard for all U.S. federal and published on 15 January 1977 as FIPS PUB 46; mandatory for them he was six months later. The standard contained the condition that must be re- confirmed every five years. Furthermore, the International Organization for Standardization ( ISO ) dealt with the algorithm under the name Data Encipherment No. 1 ( DEA1 ).

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

In the early 1990s, expressed cryptographers first doubts whether the DES algorithm is still to be regarded as safe. Firstly, the hardware compared to 1970 had evolved considerably, on the other hand was believed to identify weaknesses in the algorithm. In 1994, a theoretical attack by means of linear cryptanalysis has been published. Mid- 1998, the Electronic Frontier Foundation (EFF) by a successful attack from the brute- force method. The company built a special purpose hardware with a total of over 1800 microprocessors and was with this break a key in less than three days. Work on the successor standard AES had already begun at this time. On May 26, 2002 OF was eventually replaced by AES.

The introduction of DES is considered to trigger a variety of cryptographic studies, particularly those that deal with the attack on block ciphers. Bruce Schneier writes in his book " Applied Cryptography ":

Chronology

Operation

When DES is a symmetric algorithm, that is used to encrypt and decrypt the same key is used. THE functions as block cipher, each block is encrypted separately so using the key, said data in 16 iterations, or rounds of substitutions and transpositions ( permutation ) of the scheme of Feistel are " scrambled ." The block size is 64 bits, that is, a 64-bit block of plain text is transformed into a 64-bit block of ciphertext. Also the key that controls this transformation, has 64 bits. However, the user of these 64 bits are only 56 bits are available; the remaining 8 bits ( one bit from each byte ) are required for parity check. Therefore, the effective key length is only 56 bits. The decryption is performed with the same algorithm, where the individual round keys can be used in the reverse order.

On the 64 bit block an initial permutation is applied. Thereafter, the block is divided into two parts and each part is stored in a 32 bit register. The two block halves are in a row as left and right halves (see sketch) respectively. On the right half of the block Feistel function is applied. After that, the right half is associated with the left half of XOR and the result is stored in the next round for the right half register. In the left register of the next round of the original right half of the block is copied. After the last round, the two halves are reunited and performed a final permutation. It is the inverse permutation to the initial permutation.

Modes of operation

The DES algorithm is described initially only as a data block of 64 bits will be processed. For processing a message of arbitrary length to the DES as well as any other block cipher can be used in different operating modes. For certain operating modes, such as ECB or CBC, the plaintext is a filling up to a multiple of full block length required ( padding). This is done by the bit sequence 1000 ... is added.

The Feistel function

The F- function of DES operates on half- blocks of 32 bits and is composed of four phases:

This combination of permutations and substitutions corresponds to the format established by Claude Shannon principle of diffusion and confusion.

The expansion

To enhance the half- block in the Feistel function of 32 bits to 48 bits, the half-block in the 4- bit group is divided. The bits at the edge of each 4 -bit group to be forward, backward or attached to the adjacent 4-bit groups.

The substitution

The substitution boxes ( S-boxes ) in the DES are standardized. To get from the following tables the output value, the input value is split. Thus, the first and last bit together the row, and the column results from the remaining bits ( see example). A change in these boxes reduces the security drastically! Therefore, the following table should be used for the substitution boxes:

Weaken

Because the key length is only 56 bits, DES has already been broken by brute force attacks by systematically engaging all possible keys ( 256 = about 72 quadrillion ) were tested. There is a presumption that this small key length was deliberately chosen because the NSA already had enough computer capacity in the 1970s to break this encryption.

Deep Crack

The EFF built in 1998 a 250,000 dollar machine named " Deep Crack ". This supercomputer containing 1536 special crypto chips and was able to test about 88 billion keys per second. In July 1998, it was possible with this machine to crack a DES code in 56 hours, and thus the "DES Challenge II-2 " to win, which had been announced by the company RSA Security. 1999 won the same machine, the "DES Challenge III "; this, she worked with the worldwide network of distributed.net, consisting of about 100,000 computers together. The DES key was found in 22 hours and 15 minutes, more than 245 billion keys per second were tested.

COPACOBANA

The only other publicly known machine for breaking DES is COPACOBANA. It was built in 2006 by two research groups at the Universities of Bochum and Kiel. Unlike Deep Crack is a COPACOBANA of reconfigurable hardware modules, so-called FPGAs. 120 FPGAs of type Xilinx Spartan3 -1000 are summarized in a machine to 20 DIMM modules, each module contains six DIMM FPGAs. COPACOBANA can test 65 billion DES keys per second, with the result an average seek time of 6.4 days for a DES attack. By using reconfigurable hardware COPACOBANA can also be used for crushing of other ciphers such as A5. The material and manufacturing costs of COPACOBANA amount to about $ 10,000. The cost advantage over Deep Crack by a factor of 25 is an impressive example of Moore's Law. Hereinafter, a cost advantage of about 32 = 25 would have been expected since eight years have elapsed between the construction of the two machines ( Moore's law predicts a halving of the cost of digital ICs every 1.5 years ahead, so that when eight years about 5 halvings should have taken place).

The current record was set in 2008 by the company SciEngines GmbH set up ( a spin-off of 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 is

With the bitwise complement of designated. This can be a chosen- plaintext attack with a full key search, the search space to 255 keys cut in half.

There are four low- key with the property that

Furthermore, there are six semi- weak keys pairs with the property that

In practice, however, this is not a problem since the probability of a (semi-) weak keys with random selection of a key is only 16:256. In addition, the use of these keys can be easily avoided by being explicitly ignored in the generation.

Applications

Width applies the DES algorithm in ATMs: With the help of the DES algorithm and a secret key called a PAC is already calculated in the keyboard. This is sent along with the data from the magnetic stripe (account number, routing number, validity period, ...) to the host of the account-holding institution, where the PIN is decrypted and verified.

In the early days of ATMs ( bank account number, routing number, validity period, ...) and the secret key was derived from the data of the magnetic stripe calculates the PIN and the result is compared with the user's input. This so-called offline PIN verification is no longer used for several years.

To this day, DES is used for voice encryption of safety-critical radio transmissions. In Germany to the users include various police special units as well as the constitutional protection authorities of the Federation and the Länder. Spreads are for this purpose, two-way radios from Motorola processors in the MX3000 and MTS2000. The language is digitized by means of delta modulation and funneled through a certified plug-in module inside the radio device for encryption. The module is protected against manipulation, the key can not be read and will be deleted at tampering attempts. Even when using repeaters to extend the range, the concept is such that inside the relay station, the signal is never present unencrypted. The key management is done either locally in direct access to the device with a so-called key variable loader ( KVL ), or by radio from a central key management center via OTAR, " Over The Air Rekeying ". For this application, also DES is more than sufficiently secure given the current state of technology, provided for each use event (or regularly during longer operations ), the keys are changed, since the spoken word is only current for the opposite side of importance in such applications. A possible decryption after hours or days is irrelevant to use in the rule, since then " everything has gone " already. Both the technically relatively high cost and the expertise required, which also lowers the probability that is actually trying to decipher the radio communication afterwards.

Until recently the applicable U.S. export restrictions for the DES with full 56-bit key length has now been lifted.

Replacement algorithms

Due to its short key length DES was soon no longer safe enough and it had to find a replacement.

Triple-DES

The first replacement for DES was (also called 3DES or DESede ) Triple-DES. The idea of ​​multiple execution of DES with two different keys, a method, which has been described and analyzed by co-developer OF Walter Tuchman ( see FIPS 46-3 ). Ralph Merkle and Martin Hellman proposed after further analysis before 1981, the triple encryption with three independent, mutually different keys.

In this case, each data block is encrypted using a DES key, then decrypts encrypted with and comprising:

The key, and each can be a simple long DES key, and or the left half of a double-length DES key and the right half. In a three- fold long keys, and the respective shares of the key. This process is referred to as EDE ( Encrypt- Decrypt- Encrypt ). A simple DES encryption is thus a special case of 3DES:

A key for the encryption strength of 3DES mathematical problem was the question of whether the sequential execution of DES operations increases security, ie whether DES is a group. Campbell and Wiener found that the amount of DES encryption is not closed under sequential execution. This means that it is and the key, so that for all the keys. In other words, the number of permutations of the mold is significantly greater than the number of permutations. This allows the effective key length actually increase. However, this was not shown until 1992.

The key length of 3DES is three times as large as that of DES ( 56 bits ), whereby the key complexity is increased by a factor of 168 bits. The effective key length is 112 bits but only due to the possibility of the so-called meet-in -the -middle attack: If the attacker is in possession of a pair of plaintext and ciphertext, he can attack the encryption of both sides. The plaintext is with all possible keys for level 1 encrypted ( 256 possibilities ). The texts thus produced are also out with all possible keys for level 2 encoded ( 2112 possibilities ). Their results are compared with the results of the decryption of the ciphertext with all keys ( 256Möglichkeiten ). So have a total of only 2112 256 encryption and decryption are performed, rather than 2168 when using the brute force method.

3DES is currently considered as similar to modern encryption at 128 bits key length. However, it is relatively slow, since the computational effort by the three-time encryption is high. It should be noted, moreover, that there are several methods to use DES three times; Tuchman's 3DES is just one of them.

AES

Through a competition of NIST 's Advanced Encryption Standard ( AES) was chosen to officially replace DES in October 2000. The time now as AES designated encryption method that won the contest was filed by his Belgian developers Vincent Rijmen and Joan Daemen under the name Rijndael for this competition.

3DESE - Triple DES in PPPs

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