Section 7.3. The Data Encryption Standard
7.3. The Data Encryption StandardDuring the 1960s, with the burgeoning of computer technology and concerns about the secrecy and privacy of communications, interest in a national encryption standard began to build. The idea of this standard was that it could be used by the many different types of government computer systems and networks, as well as in the systems used by government contractors, and potentially in commercial systems as well. The drive toward a national cryptographic standard culminated in the development of the Data Encryption Standard (DES). Since 1965, when the Brooks Act was passed, the National Bureau of Standards (NBS, now known as NIST) had held the authority to research and develop standards for the protection of computer systems. The NBS study of government computing security needs, spanning the years 1968-1971, touched upon the need for an encryption standard. Development of the standard was clearly in NBS's bailiwick, and, with the cooperation of NSA, NBS initiated a cryptography program. The goal from the beginning was to develop a single public standard for protecting unclassified government or sensitive private-sector informationa standard that would be viable for approximately 10-15 years (a goal the DES far exceeded) and that would be able to be used on different types of systems (interoperability). NSA already had its own encryption algorithms used for the protection of classified military and intelligence information. NSA lent a lot of technical support to NBS, including the evaluation of proposed encryption standards. However, for national defense reasons, NSA never intended either to share its own secret algorithms with the public or to use the public standard to encrypt classified communications. In the Federal Register of May 1973, NBS invited vendors to submit data encryption techniques that might be used as the basis of a high-quality public cryptographic standard. Only a few responses were received, and these were unacceptable to the NSA evaluators. In August of 1974, NBS tried again. This time, with the prodding of NSA, IBM submitted an algorithm, which proved acceptable to NSA. At IBM, work had been proceeding for some time on the development of several encryption algorithms. One was a 64-bit algorithm used to protect financial transactions. Another was a 128-bit algorithm known as Lucifer. IBM was particularly interested in the protection of automated funds transfers, especially those involving communication between online terminals. There have been charges that NSA deliberately weakened the Lucifer algorithm before accepting it as the basis for a national cryptographic standardsome say to allow the agency to crack encrypted communications. These charges were fueled by the fact that NSA urged IBM to submit its algorithm, and by the modifications made in the Lucifer algorithm (the shortening of the key from 128 bits to 56 bits and changes in the algorithm's substitution functions, or S-boxes). A U.S. Senate panel has investigated these charges and upheld the integrity of DES. NBS solicited comments about the DES in the Federal Register of March and August, 1975, and in a letter sent to Federal Information Processing Standards (FIPS) contacts in federal agencies. In an effort to be responsive to comments and to the controversy brewing around NSA's involvement in the algorithm, NBS sponsored two workshops. One examined the feasibilityboth technical and financialof cracking the DES through computational brute force. The other examined the mathematical basis of the DES. In addition, NBS discussed with the Department of Justice issues regarding competition. The approval of the DES by the Department of Commerce in 1976, and its publication in 1977 as the Data Encryption Standard (FIPS PUB 46, updated and revised as FIPS PUB 46-1 in 1988) as the official method for protecting unclassified data in the computers of U.S. government agencies was a landmark in the history of cryptography. The approval included a provision that NBS review the algorithm every five years to determine whether it should be reaffirmed as a public standard. The DES was subsequently adopted as an ANSI standard. The following FIPS PUBs and ANSI X3 (Information Processing) Committee publications contain standards for the DES and its use:
ANSI's X9 (Financial Services) Committee has also published standards related to the use of DES in the banking community. 7.3.1. What Is the DES?FIPS PUB 46 describes the DES as follows:
FIPS PUB 46 recommends that certain kinds of data be protected by the DES:
Federal Standard 1027, Telecommunications for Use in the DES, in the Physical Layer of Data Communications, published by the General Services Administration in 1982, is a standard for how the DES algorithm should be built into cryptographic hardware or firmwarefor example, in unclassified link encryption, voice encryption, and satellite systems. Equipment bought by the government for unclassified use must meet the 1027 standard. The DES consists of two components: an algorithm and a key. The published DES algorithm involves a number of iterations of a simple transformation, which uses both transposition and substitution techniques applied alternately. This algorithm uses a single key to encode and decode messages. DES is a so-called private key cipher. As you may recall from earlier in this chapter, with this type of cipher, data is encrypted and decrypted with the same key. Both the sender and the receiver must keep the key a secret from others. Because the DES algorithm itself is publicly known, learning the encryption key would allow an encrypted message to be read by anyone. The DES key is a sequence of eight bytes, each containing eight bits (seven key bits and a parity bit). During encryption, the DES algorithm divides a message into blocks of 64 bits (plaintext). It operates on a single block at a time, dividing the block in half and encrypting the characters one after another. The characters are scrambled 16 times, under control of the key, resulting in 64 bits of encrypted text (ciphertext). The key has 56 meaningful bits (the eight parity bits are discarded by the first permutation). Figure 7-11 (adapted from a diagram included in FIPS PUB 46-1) shows the basic processing performed during DES encryption. If you are interested in the details, you can consult that publication for an explanation of DES processing. Figure 7-11. How DES works It must be noted that the government's own acceptance of DES was halfhearted at best. It never was allowed to be used in sensitive government communications, but only for sensitive but nonclassified materials. At the very time that politicians and government agency officials were making speeches about its strength (usually including references to its not being able to be cracked for multiples of the known age of the universe), a determined group of researchers working for the Electronic Freedom Foundation developed a specialized device named Deep Crack out of Field Programmable Gate Arrays (FPGAs) that demonstrated an uncanny knack of sawing through supposedly uncrackable DES ciphertext. Also, in 1997, a cooperative effort on the Internet using over 14,000 computers, deciphered a test message after using 18 quadrillion of the 72 quadrillion possible DES keys. There were three immediate effects. First the industry stopped listening for a time to almost anything the government said about privacy. Second, successive government initiatives to provide "free encryption for all," such as the "clipper chip," were laughed back into oblivion. Third, it was discovered that DES cracks did not really matter. In most transactions, there is a time window in which information must be kept absolutely secret. After that window expires, disclosure doesn't much matter, especially in financial transactions. Whatever information was urgent will be old news, and its effect will already have been discussed in the newspapers. Because DES has fallen, many organizations use triple DES (3DES), which is essentially DES repeated three times. This effectively increases the key length, boosting security, but no one is under the illusion 3DES will forever be adequately secure. Estimates of the length of key required to offer true privacy grow larger with each increase in computer power. In the early 2000s, math coprocessors began to appear in some personal computers again, along with dual-core architectures, drastically multiplying decryption power while lowering its costs. DES lives on, curiously, because everybody can use it, and it can keep secrets for a little while, which is enough for many applications. For material that has to be kept absolutely confidential, or kept confidential over the long term, DES is not the best choice. Look to its replacement, the Advanced Encryption System (AES) or one of its siblings. (AES will be discussed later in this chapter.) For many applications, however, including telecommunications and mobile radios, DES will do fine. Analyzing DES is highly instructive. Understanding it makes it easier to understand its successors. The DES provides four distinct modes of operation that differ in complexity and use. The following summarizes these modes very briefly. For a description of how the modes work, and an explanation of chaining and other technical terms, see FIPS PUB 81.
The CBC and CFB modes perform message authentication as well as encryption. Message authentication ensures that the information received matches the information sent. During encryption by the DES, the blocks of text are linked; in CBC and CFB modes, the encryption of each block depends on the results of encoding the block that preceded it. Because of this link, the final encrypted block is changed if a single character is altered anywhere in the message. The final block serves as a message authentication codea cryptographic checksum used to check the accuracy of the transmission and to detect whether there's been any tampering with the message. See the discussion in the section "Message Authentication" later in this chapter. 7.3.2. Application of the DESDES technology has been embedded in many commercial products and remains a popular choice for applications requiring fast and continuous processing, such as stream ciphers and has been used for devices such as police radios or secure telephones. One example of a DES-based product would be a mobile radio that uses a chip built on the DES algorithm to encrypt voice communications. Other DES products include encryption boxes for use with microwave, satellite, and other types of communications. Although the government cannot use the DES to protect classified or extremely sensitive unclassified information, DES products have been very popular in all but the most secret government agencies. For example, DES is found in applications in the Department of Energy communications systems. The DES was also the basis of the Department of the Treasury's electronic funds transfer program, and the Federal Reserve used DES to encrypt connections between Depository Financial Institutions and Federal Reserve banks. Off the shelf military communications systems are often built on DES. Historically, NSA has supported the DES through the Government Endorsed Data Encryption Standard Equipment Program. Through this program, NSA evaluates DES-based products, places successfully evaluated products on the NSA Endorsed Data Encryption Standard Products List (NEDESPL), and publishes this list in the Information Systems Security Services and Products Catalogue, available from the Government Printing Office. In some cases, this role is now delegated to approved independent laboratories. In 1986, the agency surprised the industry by announcing that as of January 1988, it would not endorse DES-based products as complying with Federal Standard 1027. In addition, the agency said that it would recommend that NIST not reaffirm the DES when the standard next came up for review (in 1988). NSA did say that products already endorsed would continue to be available and would continue to be listed, and that NSA would continue to provide keys as needed for these products for a time. (NSA historically provided keys to owners of DES equipment.) In addition, the agency would continue to evaluate modifications to previously endorsed products, as long as the modifications did not affect the security of the products. What's the alternative to the DES? NSA for a time tried to get both government and industry to use its own classified algorithms. Through the Commercial Communications Security Endorsement Program (CCEP), described in the later section "Government Cryptographic Programs," qualified vendors may be allowed access to these algorithms, embedded in tamperproof integrated circuit modules, that could be used in in their products. There was a sizable reactionmuch of it negativeto NSA's decision to drop DES endorsement. In 1987, in the wake of NSA's announcement, when NIST published a request for comments, 31 of 33 responding organizations (including federal agencies, the American Bankers Association, and the Computer and Business Equipment Manufacturers Association) supported reaffirmation of the standard. (Of the other two, one did not oppose reaffirmation, and the other supported reaffirmation for financial encryption.[*]) Respondents pointed out that the DES was used extensively in existing products and applications, and that there was no clear and currently available alternative. Without the DES, information might be left unprotected while organizations waited for an appropriate alternative algorithm.
Vendors had other concerns about losing the DES. They were worried about the future market for existing DES-based products. There was also concern about using government-supplied or -mandated encryption chips, for fear that this would somehow help government agencies such as NSA to more easily penetrate messages sent using the vendors' equipment, decreasing its attractiveness to buyers. (Revelations about a global monitoring network called Echelon eventually made it plain that this concern may have been valid.) Finally, because the classified algorithms have more stringent export restrictions than DES-based products, companies that use these products in their U.S. and foreign offices (and in communications between these offices) could be seriously affected. There was a time in which versions of software with built-in encryption were not approved for export. Industry complaints, many coordinated by the American Bankers Association on behalf of banks and financial institutions (prime users of the DES for encryption of financial transactions), led NSA to reconsider its decision. NSA eventually announced that it would continue to support the DES for the encryption of financial datafor example, for FedWire transactions"until transition to a new cryptographic technology is possible." The government also eased export restrictions in the late 1990s, to all but a few nations considered hostile to the United States. This was very helpful to businesses with worldwide operations. Overwhelming support for the DES, caused NIST to recommend to the Secretary of Commerce that the DES be reaffirmed for five more years, until 1992, and the cycle for creating a new encryption algorithm was begun in earnest within a few years after that. Realizing the DES is no longer secure for many applications, and suspicious of how long 3DES may last, those who are concerned about real security cast about for other algorithms that may allow them to continue in reasonable confidentiality. The government, through NIST, was heavily involved in the selection process. 7.3.3. The Advanced Encryption StandardThe government, via NIST, determined that the next nationwide algorithm should be called the Advanced Encryption Algorithm, to be used in the Advanced Encryption Standard (AES). Several rounds of competition were held to determine the algorithm that should be the basis of AES. From five semifinalists, the winning algorithm was selected to be the Rijndael algorithm, created by Joan Daemen and Vincent Rijmen. NIST announced the approval of the Federal Information Processing Standard (FIPS) for the Advanced Encryption Standard, in FIPS-197. This standard specifies the Rijndael algorithm as a FIPS-approved symmetric encryption algorithm that may be used by U.S. government organizations (and others) to protect sensitive information. Because of the difficulty of proving that an algorithm is truly secure, many nations and entities besides the United States have joined in supporting the AES. The more people there are to test an algorithm, and problems are not found, the more likely it is that people will gain confidence that it is secure. 7.3.4. Overview of the AES Development EffortNIST worked for years with the cryptographic community to develop an Advanced Encryption Standard. The overall goal was to develop a FIPS that specifies an encryption algorithm(s) capable of protecting sensitive government information for a decade or more (into the early decades of this century). The algorithm or algorithms were expected to be used by the U.S. Government and, on a voluntary basis, by the private sector. NIST announced the initiation of the AES development effort in January 1997, with a formal call for algorithms in September 1997. NIST listed the following requirements:
In August 1998, NIST announced that 15 algorithms, submitted by cryptographers worldwide, had been chosen as the first candidate group. NIST requested public comments on the candidate algorithms. Candidates met to review and discuss the various algorithms and the analysis in March 1999, two weeks after the period for comments closed. Based on the review, NIST selected 5 finalists from the 15 algorithms. The AES finalist candidate algorithms were MARS, RC6, Rijndael, Serpent, and Twofish. NIST then solicited public comments on the remaining algorithms, including but not limited to cryptanalysis, reviews of the intellectual property involved, and overall recommendations and implementation issues. NIST also provided a discussion forum for interested parties to discuss the AES finalists and relevant AES issues. In April 2000, NIST sponsored a third meetingan open, public forum for discussion of the analyses of the AES finalists. Submitters of the AES finalist algorithms were invited to attend and engage in discussions regarding comments on their algorithms, deliver papers, and make presentations. After studying all available information, NIST announced that it had selected Rijndael as the proposed AES algorithm. After another comment period, a draft FIP was published for public comment in February 2001. After a review, the standard was at last implemented in the summer of 2001. 7.3.5. How AES WorksRijndael works on a byte-by-byte basis, matching up the input cleartext to the cipher key in a matrix of 16 bytes (4 x 4 matrix). The key is divided, or scheduled, so as to be injected in several repetitive rounds a little bit at a time. The first part of the key is added in before beginning 10 processing rounds. In each of these rounds, bytes are substituted, rows are shifted, and columns are mixed. (See Figure 7-12.) Figure 7-12. Operation of AES 7.3.5.1. SubBytesIn the substitution process, the bytes of the input text are placed into a substitution box (S-box). This is a 16 x 16 matrix with a byte stored at the intersection of each row and column. The correct substitution is achieved by taking the first nibble (hex integer) of a cleartext byte and using it to determine the row of the S-box, and then the second nibble to determine the column. The character stored at the intersection of the selected row and column becomes the substitute byte (SubByte) for the cleartext. This process is repeated for each of the 16 bytes in the matrix. 7.3.5.2. Row shift and mix columnsThe bytes to be encoded, now swapped with replacements, are next subjected to a row shift. Imagine the first row being undisturbed, the second row moved right one space, with the byte that falls out rolling over and assuming the empty spot at the start of the row. The third row shifts two bytes, and the final row three. This is followed by a Mix Columns phase, in which each column of the matrix is multiplied by another matrix to change its position. 7.3.5.3. Round keysNext, a round key is added to each column. Think of the round key as a little bit of the secret key, injected so as to result in further encryption. 7.3.5.4. Do it againThese transforms are applied for nine more rounds. There is no operation to mix columns on the final round. A round key is added to the final result, yielding the ciphertext. The key is shifted and rounded and added to itself as well. The AES algorithm resulted from a multiyear evaluation process led by NIST with submissions and review by an international community of cryptography experts. AES is gradually showing up in many different encryption protocols including IEEE 802.11, IPsec, S/MIME, and TLS. RSA Laboratoriesone of the five finalists in the AES competitionrecently submitted a proposal for using AES to encrypt wireless data packets, a system called AES-CCM. A great deal of information about the AES algorithm is available at the NIST web site: http://csrc.nist.gov/encryption/aes/. |
EAN: 2147483647
Pages: 121