Data Encryption Standard

The Data Encryption Standard, or DES, is among the the best known and most thoroughly analyzed block ciphers. It was invented by IBM, and was made a US government standard for non-classified government data and for regulated industries such as banking, in the late 70s. From then until about the turn of the century, it was very widely used. DES operates on 64-bit blocks and takes a 56-bit key.

The definition of DES itself was issued as Federal Standard 1026 (FED-STD-1026) in 1976, and simultaneously as Federal Information Processing Standard (FIPS) 46, for which several updates and enhancements were issued. It is less well known that FED-STD-1027, which was openly written by the National Security Agency, was issued simultaneously, and specified secure physical packaging for DES encryptors; those mechanical and electrical standards still are useful for stronger methods of encryption.

DES is now considered obsolete; its small key size makes it vulnerable to a brute force attack , given modern computers. However, these attacks are sufficiently expensive, for messages of ephemeral value, that much of the financial industry depends on a strengthened implementation of DES. Even when used in some stronger implementations such as triple DES, it still has a vulnerability against the technique of differential cryptanalysis, although its practical use against commercial traffic may not be a matter of enormous concern.

In 2002, DES was replaced as a US government standard by the Advanced Encryption Standard which uses 128-bit blocks and takes 128, 192 or 256-bit keys. While DES was never intended for classified information, although it was approved for such use in some specific cases, AES, with keys produced by NSA, may be used for classified traffic, as well as unclassified traffic. AES was selected in an open process, and its algorithm is public.

Every new cryptanalytic technique invented since DES became a standard has been tested against DES. None of them have broken it completely, but two — differential cryptanalysis and linear cryptanalysis — give attacks theoretically significantly better than brute force. This does not appear to have much practical importance since both require enormous numbers of known or chosen plaintexts and DES can be broken by brute force with one known plaintext. All the older publicly known cryptanalytic techniques have also been tried, or at least considered, for use against DES; none of them work.

Internals

DES operates on 64-bit blocks and takes a 56-bit key. It is a Feistel cipher with 16 rounds and a 48-bit round key for each round, To generate the round keys, the 56-bit key is split into two 28-bit halves and those halves are circularly shifted after each round by one or two bits. Then 48 bits from them are selected and permuted to form the round key.

DES uses eight S-boxes, each 6 bits in and 4 out. The F function works as follows:

expand the 32-bit input to 48 bits, simply by copying some bits twice

XOR with the 48-bit round key

split the result into 8 6-bit chunks

pass each chunk through a different S-box, giving 32 output bits

permute the output bits

The permutation ensures rapid avalanche; a one-bit change in key affects one S-box; a one-bit change in the input block affects one or two S-boxes. With the permutation, changing the output of one S-box affects several S-boxes in the next round. After a few rounds, the effect spreads to the entire output.

DES was originally designed for hardware implementation and includes some operations, such as the bit permutations used in both key scheduling and the F function, which are inconvenient to do in software. There have been many software implementations of DES, many of them provide acceptable performance, and some have been widely used, but later ciphers designed with software implementation in mind are generally faster.

DES's Achilles' heel: key length

DES can no longer be considered secure in any application where there is significant risk that an adversary will deploy large resources.

DES uses a 56-bit key. That is simply too small to resist a brute force attack, an exhaustive search in which the enemy just tries keys until he finds the right one. If an enemy either has money to spend on specialised hardware or has access to many general-purpose computers, then DES is not secure against that enemy. Of course this also applies to any other cipher with a small key.

There have been a long series of papers on the difficulty of cracking DES by brute force; see this literature review . In 1977, Whitfield Diffie and Martin Hellman proposed a $20,000,000 machine that would find a DES key in 12 hours. According to Quisquater and Standaert , "They argued that this was out of reach for almost everybody, excepted organizations like the National Security Agency (NSA), but that by the 1990s, the DES would be totally insecure." There is an online transcript of them talking to NSA and NBS about this in 1976. In 1993, Weiner published a design for a $1 million machine that would find a key in 3.5 hours.

Actual machines have also been built. In 1998, the Electronic Frontier Foundation built a $200,000 machine that finds a DES key in a few days; details are in Cracking DES . In 2006, two German universities built a €9,000 "Cost-Optimized Parallel COde Breaker" or Copacobana machine based on Field programmable gate arrays that breaks DES in just under a week on average. That machine is commercially available.

Many computing tasks are quite difficult to parallelize. Cipher-cracking is one of the few exceptions; adding more hardware just makes it faster without raising any tricky communication problems. One Copacobana machine breaks DES in a week, so an attacker using seven of them can do it in a day and so on. On an intelligence agency budget, using 168 of them to crack a key an hour, or 10,000 to crack a key a minute, would be feasible if any worthwhile target still used DES.

DES has also been cracked by people using many general-purpose computers. In 1998 RSA Laboratories ran a "DES Challenge" offering a cash prize to crack a DES key. The winners used many machines connected by the Internet, "a peak of about 14,000 unique hosts within a single 24-hour period"; it took them three months to find one key. Today, the machines are much faster, according to Moore's Law roughly 100 times faster. Presumably a network of comparable size today could break DES in about a day and a smaller network could do it in a few weeks or months. Many large organisations — business, government, criminal, ... — have enough computing power for this. Some botnets (collections of compromised machines taken over for nefarious purposes) include hundreds of thousands of machines; one of those could easily crack a DES key.

Even today, it would still take decades for an attacker with a single machine to find a DES key. However, a lone attacker might be able to do it fairly quickly by using machines at an employer or a university.

Despite this, DES is still moderately widely deployed in legacy applications. In some cases — depending on the value of the information, the threats, the costs of changing to a stronger cipher, and the risks of changing a working system — keeping it in service may be reasonable. However, against serious threats it must be considered insecure; certainly there is no reason to even consider it for new applications.

DES history and controversy

The DES standard was quite controversial. The standard was based on a block cipher invented by IBM Corporation researchers, with the code name "Lucifer". However, the National Security Agency, serving as advisers to the National Bureau of Standards in the process, made some changes and those were quite controversial.

The original Lucifer had a 128-bit key. In the submission of proposals to the U.S. government, IBM proposed a 64-bit key, but, on NSA recommendation, in the actual standard 8 of those bits were used for parity error-checking so the effective key length was reduced to 56 bits. The NSA said error-checking was a useful precaution and 56 bits was all that was required to meet the design goals, providing adequate security for commercial applications and non-classified government applications. Others claimed the NSA wanted a short key so that they could break the cipher at need.

NSA also required that the mathematical theory used to design the DES S-boxes be classified. The reasons for this became clear a few decades later when the technique of differential cryptanalysis was (re)invented and published in the open cryptographic literature . It was then clear that NSA had known the differential technique at the time of DES design, and had designed the S-boxes for resistance against it. The NSA did have a good reason for keeping the S-box criteria secret: they were protecting technique of differential cryptanalysis, considered much more sensitive than DES itself.

When linear cryptanalysis came along, however, it became apparent that NSA had not known of it when they designed the DES S-boxes.

The U.S. Senate Intelligence Committee arranged for a team of independent experts to review the DES standards process. They concluded that NSA was not creating a back door.

NIST have a page on the history of DES.

The AES competition to choose a successor for DES was a very open process, perhaps partly because of criticisms of the DES process.

Variations on DES

DES is vulnerable to a brute force attack because of its small key. However, it has withstood decades of intensive analysis with no catastrophic flaws found, so it appears to be basically a remarkably solid design. Various people have therefore sought ways to achieve larger key size while retaining the basic DES algorithm.

The most widely used variation is Triple DES, applying the basic DES algorithm three times with two or three different keys. This is still (as of 2010) quite widely deployed, though it is gradually being replaced by the newer and faster standard cipher, AES.

Ron Rivest proposed DESX or DES-X, essentially DES with whitening. 64 bits of key material are XOR-ed into the plaintext before encryption, and 64 more into the ciphertext afterward. With the 56 bits of DES key, the gives 184 total keys bits so the cipher is safe from brute force attacks. Encryption overheads are only a tiny bit more than DES; the cost of the XORs. Analysis of resistance to linear cryptanalysis and differential cryptanalysis shows that it is better than DES against these attacks, but not hugely so.

Biham and Biryukov proposed techniques in which additional key bits are used to alter the S-boxes before encryption. This increases setup cost somewhat, but the overheads per block encrypted or decrypted are identical to those for DES. It is resistant to brute force and somewhat better than DES against other attacks. The technique can be used with some hardware encryption devices that DESX could not be used on.

Another approach is to use independent round keys. DES has 16 48-bit round keys, a total of 768 bits of keying material, but in normal DES they are all derived from the 56-bit main key. Use 768 independent key bits and the cipher is obviously resistant to brute force, one proposal was G-DES or Generalised DES . However, Schneier at al. demonstrate that the technique has weaknesses.

The Data Encryption Algorithm with Larger Blocks or DEAL was an AES candidate cipher, a Feistel cipher with 128-bit blocks using DES as the round function. It did not become one of the finalists; it was slower than most other candidates and some weaknesses were found.