DES (Data Encryption Standard)

DES (Data Encryption Standard) is a commonly used method for encrypting data using a secret or private key. The strength of the DES encryption standard was previously considered to be strong enough that the United States government placed restrictions on the export of the technology to other countries. Conceptually, there are more than 72 quadrillion possible encryption keys that can be used with DES. When encrypting a message or data using the algorithm, the key is chosen at random from the pool of possible keys. Similar to other PKI methods, both the sending and receiving person or computer must use the same private key in order to encrypt and decrypt the desired information.

DES Background

DES (Data Encryption Standard) was once the most used algorithm for encrypting electronic data in industry. The algorithm would have significant impact on the advancements in modern cryptography in both the academic and commercial worlds. DES was originally created in the 1970s at IBM and was based on a design by Horst Feistel. In 1976 the DES standard was selected by the National Bureau of Standards (NBS) as a FIPS (Federal Information Processing Standard) for the U.S. in 1977. Combined with the publication by the NSA of an approved DES standard, DES quickly became adopted internationally.

Today, DES is considered to be too insecure for a number of transactions primarily due to the 56-bit key size being too small for modern technology. In January of 1999, the Electronic Frontier Foundation and distributed.net were able to collaborate to break a DES key in less than 24 hours (22 hours and 15 minutes). In the form of Triple DES, the algorithm is believed to be secure; however, in recent use the cipher has been superseded by AES (Advanced Encryption Standard). Additionally, NIST (National Institute of Standards and Technology) has withdrawn DES as a standard. The DES algorithm can also be referred to as the Data Encryption Algorithm (DEA).

DES Operational Overview

At the high level, the DES algorithm takes a 56-bit key and applies it to the data queued for encryption in 64 bit data blocks. There are a number of modes that the DES algorithm can be run, and there are typically 16 rounds of operation. Single DES provides a “strong” level of encryption, while many organizations that still use DES will employ Triple DES. In Triple DES, there are three keys applied in succession making the information harder to decrypt by those who do not have the secret or private key.

The History of DES

The DES algorithm’s history dates to the early 1970s. In 1972, the United States National Bureau of Standards (since rebranded or renamed to NIST (National Institute of Standards and Technology)) published a need for the U.S. government to have a standard for encrypting unclassified, but sensitive information. On May 15^th, 1973, the National Bureau of Standards published a solicitation for proposals for a cipher algorithm that could be rigorously defined criteria that had been vetted by the U.S. National Security Agency. Of the submissions provided in the 1973 call for applications; however, none proved to be suitable for the U.S. government’s needs.

On August 27^th, 1974, another solicitation by the NBS was made. During this round, IBM provided a cipher algorithm that proved suitable which was based on previous work by Horst Feistel (Lucifer algorithm). The IBM project team for the cipher work included Feistel, Walter Tuchman, Don Coppersmith, Alan Konheim, Carl Meyer, Mike Matyas, Roy Adler, Edna Grossman, Bill Notz, Lynn Smith, and Bryant Tuckerman.

NSA’s Involvement with the Design of DES

Once the IBM team’s proposal was accepted, the DES algorithm was published in the U.S. Federal Registrar on March 17^th, 1975. There were public comments and discussion requested regarding the standard, and over the next year the government held two open working groups to discuss the work. During this time, there was a fair amount of criticism by noted cryptography pioneers Whitfield Diffie and Martin Hellman alleging potential interference by the NSA.

Their suspicions came from the shortened key length of DES and the “S Boxes” included in the algorithm. Their and other academics feedback was that it seemed as though the NSA had covertly weakened the algorithm to ensure that they would be able to decrypt messages in the future. To add fire to the “conspiracy theory,” Alan Konheim who helped designed DES stated that, “ We sent the S-boxes off to Washington. They came back and were all different.” In findings published in 1978, the United States Senate Select Committee on Intelligence found that the NSA’s actions had not been improper in the development of DES and certified that the final algorithm was free from any mathematical or statistical weakness. The NSA was also cleared of allegations of tampering with the DES algorithm in any way.

It wouldn’t be until the early 1990s, that Don Coppersmith would publish some of the original DES design plans for the S-boxes. After this publication, it became evident that the S boxes of the algorithm were more resistant to the block cipher attack method published by Shamir and Biham than if they were selected at random. It would take almost 20 years for the academic community to discover and understand that the NSA tweaking of DES improved the overall security of the algorithm.

Adopting DES as a Standard

Despite the widespread, public criticism of the NSA’s role in the development of DES, the algorithm was approved as a U.S. federal standard in November of 1976 and later published on January 15^th, 1977. DES was authorized for use on all U.S. government labeled unclassified information and subsequently reaffirmed as the government standard in 1983, 1988, and as “Triple DES” in 1999. The U.S. government superseded DES as the government standard with AES (Advanced Encryption Standard) following a public competition on May 26^th, 2002. Although the Triple DES standard was officially removed on May 19^th, 2005, NIST did approve Triple DES for use on sensitive governmental information through the year 2030.

DES Development Timeline

Date                      Event
15 May 1973       NBS (National Bureau of Standards) published an initial request for a standard encryption algorithm.
27 August 1974  NBS published a second request for an encryption algorithm.
17 March 1975   DES is published in the Federal Register for comment.
August  1976      First public working group on DES is held
September 1976    Second public working group is held to discuss the mathematical foundation of DES.
November 1976     DES is approved as a standard.
15 January 1977   DES is published as a FIPS standard, FIPS PUB 46.
1983      DES is reaffirmed for the first time as the U.S. government standard for encryption.
1986       Videocipher II, a TV satellite scrambling system based upon DES, begins use by HBO.
22 January 1988   DES is reaffirmed for the second time,  FIPS 46-1, superseding FIPS PUB 46.
July        1991  Biham and Shamir discover a differential cryptanalysis of DES, and apply it to a 15-round DES-like cryptosystem.
1992       Biham and Shamir report the first theoretical attack with less complexity than brute force: differential cryptanalysis. However, the technique requires an unrealistic 247 chosen plaintexts.
30 December 1993  DES is reaffirmed for the third time by the United States, as FIPS 46-2
1994        The first experimental cryptanalysis of DES is performed using linear cryptanalysis.
June  1997        The DESCHALL Project breaks a message encrypted with DES for the first time in public.
July 1998        The EFF’s DES cracker (Deep Crack) breaks a DES key in 56 hours.
January 1999      Together, Deep Crack and distributed.net break a DES key in 22 hours and 15 minutes.
25 October 1999 DES is reaffirmed for the fourth time as FIPS 46-3,which includes the preference for “Triple DES” over the legacy “Single DES.”
26 November 2001  The Advanced Encryption Standard (AES) is published in FIPS 197.
26 May 2002       AES Standard becomes effective.
26 July 2004      The withdrawal of FIPS 46-3(Triple DES and legacy DES) (and a couple of related standards) is proposed in the Federal Register.
19 May 2005       NIST withdraws FIPS 46-3, DES and Triple DES.
April 2006       The FPGA based parallel machine COPACOBANA of the Universities of Bochum and Kiel, Germany, breaks DES in 9 days at $10,000 hardware cost. Within a year software improvements reduced the average time to 6.4 days.
Nov 2008        The successor of COPACOBANA, the RIVYERA machine reduced the average time to less than one single day to break DES encryption.

How Does DES Work?

DES is the original block cipher used throughout industry. It is designed to take a fixed-length string of plaintext and convert or transform it into ciphertext after conducting a series of operations. Once transformed, the resulting text is the same length as the input text to the cipher. DES is designed to work on text in 64 bit blocks. Additionally, the DES key is also 64 bits in length; however, 56 of the bits are used by the algorithm with the remaining 8 bits reserved for parity checking and then discarded making the effective key length of the algorithm 56 bits.

Structure of DES

In the DES algorithm, there are 16 stages of processing that are referred to as “rounds.” Additionally, there is an initial (IP) and final permutation (FP) that are inverses of each other. Although these steps do not add any cryptographic value to the algorithm, there were included in the original standard to help load blocks of information into 8-bit based computer hardware in the mid-1970s.

Prior to the primary rounds of operation of the algorithm, the cipher block is divided into two, 23 bit halves. Once divided, the blocks are processed alternatively in a crisscross fashion. This method is referred to as the Feistel scheme and helps ensure that both decryption and encryption follow very similar processes. The only difference in the two processes in DES are that the various subkeys are used in the reverse order when decrypting data. The remainder of the DES algorithm is identical which helps simplify implementation in hardware by eliminating the need for separate encryption and decryption algorithms.

During the operation of DES, the F-function will scramble half of a block of text with some of the key. The output of the F function is combined with the output of the other half of the block. The two halves will be swapped prior to the next round of encryption. After the final round of the encryption, the halves are swapped one final time.

How Does the Feistel Function Work?

The Feistel Function (or F function) of DES works on 32 bits of data (half a block) at one time. The function uses a four stage operation:

Stage 1 – Expansion. The Feistel function starts by expanding the 32 bit half block to 48 bits using an expansion permutation by duplicating half of the bits. The output consists of 8 x 6 bit pieces (48 bits total) that contain a copy of four corresponding input bits in addition to a copy of the immediately adjacent bit from each of the input pieces to either side.

Stage 2 – Key mixing. The result of stage 1 is combined with a subkey using an XOR operation. Then, 16 x 48 bit subkeys (one is used for each round) are then derived from the primary or main key using the DES key scheduler.

Stage 3 – Substitution. Once the subkey is mixed in, the block is then divided into 8 x six bit pieces before processing is conducted by the S boxes (substitution boxes). Each of the 8 x S-boxes will replace its six input bits with four output bits based on a non-linear transformation provided in lookup table form. The S boxes are what provide the primary core of DES’s security. Without the substitutions, the cipher would be linear and easily cracked or broken.

Step 4 – Permutation. The final stage of DES is permutation. The 32 bit outputs from the S boxes are rearranged according to the P box, or fixed permutation. DES is designed so that after the permutation, each of the S box output bits will be spread across six different S boxes in the next round.

How Secure is DES?

There has been a significant amount of information published regarding the cryptanalysis of DES over the past several decades. The most straight-forward method used to attack DES discovered to-date is the brute force attack. There are three theoretical attacks possible based on cryptanalytic properties of the algorithm; however, require an unrealistic number of known plaintexts to carry out the attacks and are not practical to carry out in a speedy or usable manner.

Brute Force Attacks Against DES

For all known ciphers, the most basic attack method is brute force. This consists of attempting every possible key against an encoded text. The overall length of the key determines the total number of possible keys and feasibility of cracking the key. Since the overall key size for single DES is relatively small at 56 bits, there have been successful brute force attacks against the algorithm over the past two decades. As a result, any practical use of DES in industry today typically requires “Triple DES” in order to keep potentially sensitive information guarded against most attacks.

In the EFF DES cracking computer, there were 1,856 custom chips (the computer cost approximately $250,000 USD), and a DES key could be cracked in a few days. The COPACOBANA computer build in 2006 by teams at the Universities of Kiel and Bochum in Germany used commercially available integrated circuits that were capable of cracking DES in less than one day.