Data Encryption Standard

Data Encryption Standard (DES), an early data encryption standard endorsed by the U.S. National Bureau of Standards (NBS; now the National Institute of Standards and Technology). It was phased out at the start of the 21st century by a more secure encryption standard, known as the Advanced Encryption Standard (AES), which was better suited for securing commercial transactions over the Internet.

In 1973 the NBS issued a public request for proposals for a cryptoalgorithm to be considered for a new cryptographic standard. No viable submissions were received. A second request was issued in 1974, and International Business Machines Corporation (IBM) submitted the patented Lucifer algorithm that had been devised by one of the company’s researchers, Horst Feistel, a few years earlier. The Lucifer algorithm was evaluated in secret consultations between the NBS and the U.S. National Security Agency (NSA). After some modifications to the internal functions and a shortening of the code key size from 112 bits to 56 bits, the full details of the algorithm that was to become the Data Encryption Standard were published in the Federal Register in 1975. Following almost two years of public evaluation and comment, the standard itself was adopted at the end of 1976 and published at the beginning of 1977. As a consequence of certification of the standard by the NBS and its commitment to evaluate and certify implementations, it was mandated that the DES be used in unclassified U.S. government applications for the protection of binary-coded data during transmission and storage in computer systems and networks and on a case-by-case basis for the protection of classified information.

The use of the DES algorithm was made mandatory for all financial transactions of the U.S. government involving electronic fund transfer, including those conducted by member banks of the Federal Reserve System. Subsequent adoption of the DES by standards organizations worldwide caused the DES to become a de facto international standard for business and commercial data security as well.

The DES is a product block cipher in which 16 iterations, or rounds, of substitution and transposition (permutation) process are cascaded. The block size is 64 bits. The key, which controls the transformation, also consists of 64 bits; however, only 56 of these can be chosen by the user and are actually key bits. The remaining 8 are parity check bits and hence totally redundant. The figure is a functional schematic of the sequence of events that occurs in one round of the DES encryption (or decryption) transformation. At each intermediate stage of the transformation process, the cipher output from the preceding stage is partitioned into the 32 left-most bits, L_i, and the 32 right-most bits, R_i. R_i is transposed to become the left-hand part of the next higher intermediate cipher, L_i + 1. The right-hand half of the next cipher, R_i + 1, however, is a complex function, L_i + f(R_i, K_i + 1), of a subset of the key bits, K_i + 1, and of the entire preceding intermediate cipher. The essential feature to the security of the DES is that f involves a very special nonlinear substitution—i.e., f(A) + f(B) ≠ f(A + B)—specified by the Bureau of Standards in tabulated functions known as S boxes. This process is repeated 16 times. This basic structure, in which at each iteration the cipher output from the preceding step is divided in half and the halves transposed with a complex function controlled by the key being performed on the right half and the result combined with the left half using the “exclusive-or” from logic (true or “1” only when exactly one of the cases is true) to form the new right half, is called a Feistel cipher and is widely used—and not just in the DES. One of the attractive things about Feistel ciphers—in addition to their security—is that if the key subsets are used in reverse order, repeating the “encryption” decrypts a ciphertext to recover the plaintext.

The security of the DES is no greater than its work factor—the brute-force effort required to search 2⁵⁶ keys. That is a search for a needle in a haystack of 72 quadrillion straws. In 1977 that was considered an impossible computational task. In 1999 a special-purpose DES search engine combined with 100,000 personal computers on the Internet to find a DES challenge key in 22 hours. An earlier challenge key was found by distributed computing over the Internet in 39 days and by the special-purpose search engine alone in 3 days. For some time it had been apparent that the DES, though never broken in the usual cryptanalytic sense, was no longer secure. A way was devised that effectively gave the DES a 112-bit key—ironically, the key size of the Lucifer algorithm originally proposed by IBM in 1974. This is known as “triple DES” and involves using two normal DES keys. As proposed by Walter Tuchman of the Amperif Corporation, the encryption operation would be E₁D₂E₁ while decryption would be D₁E₂D₁. Since E_kD_k = D_kE_k = I for all keys k, this triple encryption uses an inverse pair of operations. There are many ways to choose the three operations so that the resultant will be such a pair; Tuchman suggested this scheme since if the two keys are both the same, it becomes an ordinary single-key DES. Thus, equipment with triple DES could be interoperable with equipment that only implemented the older single DES. Banking standards adopted this scheme for security.

Cryptology has traditionally been a secretive science, so much so that it was only at the end of the 20th century that the principles on which the cryptanalysis of the Japanese and German cipher machines of World War II were based were declassified and released. What was different about the DES was that it was a totally public cryptographic algorithm. Every detail of its operations—enough to permit anyone who wished to program it on a microcomputer—was widely available in published form and on the Internet. The paradoxical result was that what was generally conceded to have been one of the best cryptographic systems in the history of cryptology was also the least secret.