  |
DES |
 Feistle |
Phill |
|||||||||
|
The Data Encryption Standard (DES) cryptographic algorithm was approved in the 1970s as a US federal standard for use on unclassified government communications. Although it has since been superseded for official use, it remains widely used and can be regarded for many purposes as the de facto standard for modern encryption. Although the algorithm is commonly called "DES", this is in fact the name of the Standard, which also covers specifications for implementation and operation
The DES algorithm is based on a 128-bit block algorithm developed in the 1960s by IBM. This algorithm, "LUCIFER", was part of an experimental cryptographic system. In technical terms, LUCIFER is an iterative block cipher, using Feistel rounds - a block of data is encrypted a number of several times, each time applying the key to half of the block and then XOR'ing with the other half of the block. LUCIFER was vulnerable to attacks from differential cryptanalysis, so work was carried out to strengthen it. The improved algorithm was adopted in 1976 as the standard for securing data on computer or telecommunications systems, and all US Federal agencies (and other organizations that process information on behalf of the Federal Government) were required to use DES to secure sensitive data.
DES was designed to use a 64-bit key to encrypt and decrypt 64-bit blocks of data using a cycle of permutations, swaps, and substitutions. Encryption and decryption use the same key. A block to be encrypted is subjected to an initial permutation, then to a complex key-dependent computation, and then to a final permutation. The initial and final permutations take the 64-bit block and change the position of each bit in a pre-determined manner. The final permutation is the reverse of the initial permutation. For the key-dependent computation, a key schedule function takes the 64-bit key and from it creates a set of sixteen 48-bit key blocks. Each of these is used in turn at each of the 16 rounds of the cipher function, which alters the plaintext in accordance with the specifications of an S-Box. The S-Box definitions were specified by the US Government, and has been the subject of considerable controversy because they are crucial to the strength of the algorithm.
A DES key consists of 64 binary digits of which 56 bits are randomly generated and used directly by the algorithm. The other 8 bits, which are not used by the algorithm, are used for error detection. The 8 error detecting bits are set to make the parity of each 8-bit byte of the key odd, i.e., there is an odd number of "1"s in each 8-bit byte.
DES was not only the Federal Standard, but was also widely used as the algorithm of choice for many years. However, it also became the focus of much dissent because the US imposed controls over its export. Furthermore, the academic cryptographic community argued that DES's 56-bit key was too short to withstand a brute-force attack from modern computers. (Moore's Law states that computer power doubles every 18 months, so a key that could withstand a brute-force guessing attack in 1975 could hardly be expected to withstand the same attack a quarter of a century later.) DES is even more vulnerable to a brute-force attack because it is often used to encrypt words. In effect, the amount of work needed to recover a message is reduced because predictions can be made about the underlying plaintext. If we are encrypting random bit streams, then a given byte might contain any one of 28 (256) possible values and the entire 64-bit block has 264, or about 18.5 quintillion, possible values. If we are encrypting words, however, we are most likely to find a limited set of bit patterns; perhaps 70 or so if we account for upper and lower case letters, the numbers, space, and some punctuation. This means that only about ¼ of the bit combinations of a given byte are likely to occur. Nevertheless, the US government maintained throughout the mid-1990s that 56-bit DES was secure if appropriate precautions were taken. In January 1997, RSA Inc issued a challenge, with a prize of $10,000, to "crack" DES. Computers participating in the challenge aimed to try every possible decryption key to crack DES - over 72 quadrillion (72,057,594,037,927,936). The winning DESCHALL effort, led by computer programmer Rocke Verser, linked thousands of computers via the Internet to mount a brute force attack and solved the encrypted message in 84 days - "Strong cryptography makes the world a safer place." From February 1997, DESCHALL searched nearly 18 quadrillion keys at rates of up to 601 trillion keys per day. At the time the winning key was reported to RSA, DESCHALL had searched almost 25 percent of the total. At its peak, the DESCHALL effort was testing nearly seven billion keys per second. The actual computer that found the winning key was a 90 MHz Pentium desktop machine with 16 megabytes of memory. In a follow up activity in July 1998, the Electronic Freedom Front built the first unclassified hardware for cracking DES-encoded messages. The EFF DES Cracker, which was built for less than $250,000, took less than 3 days to complete the RSA DES Challenge II. The DES III challenge was launched in January 1999 and confirmed that DES was no longer adequate to withstand modern computing power. "Deep Crack" launched a brute-force attack by guessing every possible key and looking for any shortcuts and clues. they could find. By assuming that some recognizable plaintext would appear in the decrypted string, only a very low proportion of the total possible keys needed to be investigated fully. If a decrypted 8-byte block contained an "interesting" alphanumeric string, the key was applied to the next block; if not, the key was abandoned. Looking for 16 consecutive bytes that were "interesting" meant that only 224, or 16 million, keys needed to be examined further. This further examination was primarily to see if the text made any sense. Possible "interesting" blocks might be 1hJ5&aB7 or DEPOSITS; the latter is more likely to produce a better result. Moreover, if the key is changed frequently, the risk of this event is greatly diminished. However, users should be aware that it is theoretically possible to derive the key in fewer trials (with a correspondingly lower probability of success depending on the number of keys tried) and should be cautioned to change the key as often as practical. Users must change the key and provide it a high level of protection in order to minimize the potential risks of its unauthorized computation or acquisition. The feasibility of computing the correct key may change with advances in technology. |
Development and Adoption of DES
|
|||||||||||
