(DATA ENCRYPTION STANDARD)
Data Encryption Standard (DES) is an encryption algorithm, ie a method for encrypting information, FIPS chosen as in the United States in 1976, and whose use is widespread throughout the world. The algorithm was initially controversial with classified design elements, a relatively short key length, and the continuing suspicions about the existence of a backdoor for the National Security Agency (NSA). DES was subsequently subjected to intense academic analysis led to the modern concept of block ciphers and their cryptanalysis.
Today, DES is considered unsafe for many applications. This is mainly due to the size of 56-bit key is short DES keys are broken in less than 24 hours. Analytical results also exist that show theoretical weaknesses in encryption, but are unfeasible in practice. It is believed that the algorithm is safe in practice variant of Triple DES, although there are theoretical attacks.
In recent years, the algorithm has been replaced by the new AES (Advanced Encryption Standard). In some instances, DES is also known as DEA (Data Encryption Algorithm).
The History of DES - Encryption
The origins of DES go back to the early 70's. In 1972, after completing a study on the needs of government computer security, the authority of U.S. standards NBS (National Bureau of Standards) - now renamed NIST (National Institute of Standards and Technology) - concluded on the need for a standard at government level to encrypt sensitive information. Accordingly, the May 15, 1973, after consultation with the NSA, NBS solicited proposals for an algorithm that meets stringent design criteria. Nevertheless, none of which appeared to be adequate. A second request was made on August 27, 1974. At that time, IBM submitted a candidate who was considered acceptable, an algorithm developed during the period 1973-1974 based on a previous one, the algorithm Horst Feistel's Lucifer. The IBM team dedicated to the design and analysis of the algorithm consisted of Feistel, Walter Tuchman, Don Coppersmith, Alan Conheim, Carl Meyer, Mike Matyas, Roy Adler, Edna Grossman, Bill Notz, Lynn Smith, and Bryant Tuckerman.NSA's role in the design - Encryption
On March 17, 1975, the proposed DES was published in the Federal Register. Comments were sought from the public, and the following year opened two free workshops to discuss the proposed standard. There was some criticism from certain sectors, including symmetric cryptography pioneers Martin Hellman and Whitfield Diffie, citing the short key length and the mysterious S-boxes as evidence of improper interference from the NSA. The suspicion was that the algorithm had been weakened so secret intelligence agency so that they - and anyone else - could easily read encrypted messages. Alan Konheim (one of the designers of DES) once said "the S-boxes sent to Washington. When they were totally different." The Senate Intelligence Committee of the United States reviewed the actions of the NSA to determine whether there had been some inappropriate behavior.
In the unclassified summary of its findings, published in 1978, the Committee wrote: "In the development of DES, NSA convinced IBM that a reduced key size was sufficient, participated indirectly in the development of structures S-boxes, and certified that, as far as they knew, were free of any mathematical or statistical weakness. ". Anyway, also concluded that "the NSA did not exert pressure on the design of the algorithm in any way. IBM invented and designed the algorithm, all decisions made about him, and agreed that the key size was more than adequate for all commercial applications for which DES was intended. " Another team member DES, Walter Tuchman also said, "We developed all the DES algorithm on IBM and IBM people. The NSA did not issue even a single step".
Some of the suspicions about hidden weaknesses in the S-boxes were discarded in 1990 with the independent discovery and the free publication by Eli Biham and Adi Shamir of differential cryptanalysis, a general method for breaking block ciphers. The S-boxes of DES were much more resistant to attack than if they had been chosen at random, suggesting that IBM knew the art back in the 70. This was indeed the case - in 1994, Don Coppersmith published the original design criteria for S-boxes. IBM had discovered differential cryptanalysis in 70 and, after stating DES, the NSA were ordered to keep secret the art. Coppersmith said: "This was because the differential cryptanalysis can be a powerful tool against many different schemes, and there is concern that public domain information that could adversely affect national security." Shamir also said "I would say, contrary to what some believe, no evidence of any influence on the design of DES for their basic structure is weakened."
The other criticism - on the key length was too short - were based on the fact that the reason given by the NSA to reduce the key length of 64 bits to 56 bits was that the 8 remaining bits could serve as parity, which was somewhat suspect. It is widely accepted that the decision of the NSA was motivated by the possibility that they could perform a brute force attack against a 56-bit key for several years before the rest of the world.
The standard algorithm - Encryption
Despite the controversy, DES was approved as a federal standard in November 1976 and published on January 15, 1977 as FIPS PUB 46, licensed for use unclassified data. It was later confirmed as a standard in 1983, 1988 (revised as FIPS-46-1), 1993 (FIPS-46-2), and again in 1998 (FIPS-46-3), the latter defining "TripleDES" (see below). On May 26, 2002, DES was finally replaced by AES (Advanced Encryption Standard), following a public competition (see Process Advanced Encryption Standard). To date (2006), DES is still widely used.
Another theoretical attack, linear cryptanalysis, was published in 1994, but was a brute force attack in 1998 which showed that DES could be attacked in practice, and emphasized the need for a replacement algorithm. These and other methods of cryptanalysis are discussed in more detail later in this article.
The introduction of DES is considered a trigger for the academic study of cryptography, including methods to break block ciphers. Bruce Schneierescribe: "From door to the inside, the NSA has been to DES as one of its big mistakes. If they had known that the details would be published so that people could write software, I never would have agreed. DES did more to galvanize field of cryptography that nothing ever before. Now there was an algorithm that study: one that the NSA said it was safe. "
Replacement algorithms - Encryption
Many former DES users now use Triple DES (3DES), which was described and analyzed in a patent DES (see FIPS PUB 46-3), consists of applying DES three times consecutively using two (2TDES, the first key in steps 1 and 3) or three (3TDES) keys. 3DES is widely recognized as safe by now it is quite slow. A cheaper alternative is computationally DES-X, which increases the key size by a logical XOR of the key additional elements before and after DES. GDES was a variant of DES proposal to accelerate the encryption process, but it proved to be capable of being subjected to differential cryptanalysis.
In 2001, following an international competition, NIST chose a new algorithm: AES (Advanced Encryption Standard), to replace DES. The algorithm chosen to be the AES was proposed by its designers under the name Rijndael. Other finalists in the competition were RC6 NIST AES, Serpent, MARS and Twofish.
In general, there is no algorithm that adapts perfectly to all uses. An algorithm for use in general purpose machines (eg, SSH, or some types of email encryption), does not always work well in embedded systems or smart cards, and vice versa.
Description For brevity, the description below omits the exact transformations and permutations specifies the algorithm, for more information see DES additional material. DES algorithm is the prototype of the block cipher - an algorithm that takes a plaintext of a fixed length of bits and transforms through a series of complicated operations into another ciphertext of the same length. In the case of DES block size is 64 bits. DES uses a cryptographic key to also modify the transformation, so that decryption can be performed only by those who know the specific key used for encryption. The key is 64 bits, but in reality, only 56 of them are employed by the algorithm. The remaining eight bits are used only for parity check, and then are discarded. Therefore, the effective key length of DES is 56 bits, and this is how it usually specified. As with other block ciphers, DES must be used in the encryption mode of block if applied to a message longer than 64 bits. FIPS-81 specific number of modes for use with DES, including one for authentication. More documents are available on the use of DES in FIPS-74.
Basic structure - Encryption
The basic structure of the algorithm depicted in Figure 1: there are 16 identical stages of the process, called rounds. There is also a known initial and final permutation IP and PF, which are inverse functions to each other (IP "undoes" the action of PF, and vice versa). PI and PF are not cryptographically significant but presumably included for easy loading and unloading of hardware blocks on the mid 70's. Before rounds, the block is divided into two halves of 32 bits and processed alternately. This crosslinking is known comoesquema Feistel.
The Feistel structure ensures that encryption and decryption processes are very similar - the only difference is that the subkeys are applied in reverse order when deciphered. The rest of the algorithm is identical. This greatly simplifies the implementation, especially on hardware, not having need of different algorithms for encryption and decryption.
The red symbol "⊕" represents the exclusive OR operation (XOR). The function F mix half-block with some of the key. The output of the function-F is then combined with the other half of the block and the blocks are exchanged before the next round. After the last round, the halves are not swapped, this is a property of the Feistel structure which makes encryption and decryption processes are similar.
Expansion - half the block of 32 bits to 48 bits is expanded by the expansion permutation, called E in the diagram, doubling some of the bits.
Mix - the result is combined with a subkey using an XOR. Sixteen subkeys - one for each round - resulting from the initial key by generating subkeys described below.
Substitution - after mixing with the subkey, the block is divided into eight 6-bit pieces before being processed by the S-boxes, ocajas replacement. Each of the eight S-boxes replaces its six input bits with four output bits in accordance with a nonlinear transformation specified by a lookup table The S-boxes form the core of the security of DES - without them, encryption would be linear, and easy to break.
Permutation - finally the 32 outputs of the S-boxes are rearranged according to a fixed permutation, the P-box
Alternating the replacement of the S-boxes, and permutation of bits of the P-box-E expansion and provide so-called "confusion and diffusion", respectively, a concept identified by Claude Shannon in the 40 as a necessary condition for an encryption safe and practical.
Key Generation - Encryption
Key generation for encryption - the algorithm that is responsible for providing the subkeys. First, you select 56-bit key of the initial 64 by Permuted Choice 1 (PC-1) - the eight remaining bits can be discarded or used as parity check bits. The 56 bits are then divided into two 28-bit halves, and then each half is treated independently. In successive rounds, both halves are moved to the left one or two bits (depending on each round), and then 48 bits are selected by subkey permuted choice 2 (PC-2) - 24 bits of the left half and 24 the right. The displacements (indicated by "<<<" in the diagram) imply that uses a different set of bits in each subkey, each bit is used in approximately 14 of the 16 subkeys.
The generation of keys for decryption is similar - to generate keys in reverse order.
Security and cryptanalysis - Encryption
Although published more information on the cryptanalysis of DES than any other block cipher, the more practical attack today remains brute force. Cryptanalytic known under several properties, and are three types of possible attacks theoretical even a theoretical complexity requiring less than a brute-force attack, they require a quantity unrealistic oescogidos plaintexts known to take place, and not taken into account in practice.
Brute force attack - Encryption
For any type of encryption, the simplest method of attack is the brute force - trying one by one every possible clue. TheLen key determines the number of possible keys, and therefore the feasibility of the attack. In the case of DES, and in their early questions were raised about the key length, even before being adopted as standard, was its small key size, rather than theoretical cryptanalysis, which caused the need for replacement. It is known that the NSA encouraged, or even persuaded IBM to reduce the key size of 128 bits to 64, and then to 56 bits, often this has been interpreted as evidence that the NSA had enough computing power to break keys of this size even in the mid 70's.
Academically, came forward several proposals for a machine to break DES. In 1977, Diffie and Hellman proposed a machine with an estimated cost of $ 20 million that could find a DES key in one day. By 1993, Wiener proposed a key search machine costing a million dollars to find a key in 7 hours. The vulnerability of DES was demonstrated in practice in 1998 when the Electronic Frontier Foundation (EFF), a group dedicated to civil rights in cyberspace, built as a machine to break DES, with an approximate cost of $ 250,000 (see EFF DES cracker). His motivation was to demonstrate that DES could be broken both in theory and in practice: "Many people will not believe the truth until they can see for yourself. Show them a physical machine that can break DES in a few days is the only way to convince some people that really can not trust their security to DES. " The machine broke a key by brute force in a search that lasted just over 2 days, more or less the same time, a Justice Department lawyer in the United States claimed that DES was unbreakable.
Attacks faster than brute force - Encryption
There are three known attacks that can break the full sixteen rounds of DES with less complexity than a brute force attack: differential cryptanalysis (DC), linear cryptanalysis (LC) and the attack of Davies. However, these attacks are only theoretical and can not implement them, these types of attacks are sometimes called certificacionales weaknesses.
Differential cryptanalysis was discovered in the late 80's by Eli Biham and Adi Shamir, though both previously known as IBM NSA and kept secret. To break the 16 full rounds, differential cryptanalysis requires 247textos planes chosen. DES was designed to be resistant CD.
The linear cryptanalysis was discovered by Mitsuru Matsui, and requires 243 known plaintexts (Matsui, 1993), the method was implemented (Matsui, 1994), and was the first experimental cryptanalysis of DES that was released. There is no evidence that DES was adapted to be resistant to this type of attack. A generalization of CL - Multiple linear cryptanalysis - was suggested in 1994 Kaliski and Robshaw) and was improved by Biryukov and others (2004), his analysis suggests that could be used multiple linear approximations to reduce the data requirements of the attack on the least a factor of 4 (ie, 241 instead of 243). A similar reduction in the complexity of data can be obtained with a variant of linear cryptanalysis chosen plaintexts (Knudsen and Mathiassen, 2000). Junod (2001) conducted several experiments to determine the real complexity of linear cryptanalysis, and found it was slightly faster than predicted, requiring time equivalent to 239-241comprobaciones in DES.
Davies improved the attack: while the linear and differential analysis techniques are general and apply to many different schemes, the attack of Davies is a specialized technique for DES. First proposed by Davies in the 80, and improved by Biham and Biryukov (1997). The most powerful attack requires 250 known plaintexts, has a computational complexity of 250, and has a 51% chance of success.
There are also attacks designed to versions of the algorithm with fewer rounds, ie versions of DES under sixteen rounds. These analyzes provide insight on how many rounds are needed to achieve security, and how much "safety margin" provides the full version. The differential-linear cryptanalysis was proposed by Langford and Hellman in 1994, combining differential and linear cryptanalysis in the same attack. An improved version of the attack can break a DES 215.8 9 rounds with known plaintexts and has a time complexity of 229.2 (Biham et al, 2002).
Cryptanalytic properties - Encryption
DES has the additional property, as where is the complement bit of x. EK is encrypted with the key K. P and C are the plaintext and ciphertext respectively. The complementary property implies that the duty cycle for a brute force attack could be reduced by a factor of 2 (or a single bit) assuming a chosen plaintext attack.
DES also has four weak keys. The encryption (E) and decryption (D) with a weak key has the same effect (see involution): EK (EK (P)) = P or what is the same, EK = DK. There are also six pairs of semi-weak keys. The encryption key with a key pair of a semi-weak, K1, works the same way as the decryption with the other, K2: or what is the same.
It's pretty easy to avoid the semi-weak keys and weak implementation, testing them either explicitly, or simply picking them randomly, the odds of picking a weak key or semidébil are negligible.
It has also shown that DES has no group structure, or more specifically, the set {EK} (for all possible keys K) is not a group, not even "close" to being a group (Campbell and Wiener, 1992 .) This was an open question for some time, and if it had been the case, it would be possible to break DES, and multiple encryption methods as Triple DES have not increased security.
Comentarios