The Data Encryption Standard (DES)

The Data Encryption Standard (DES) was the world's standard cipher for a quarter of a century. IBM designed it, the US government adopted it in 1977, and it protected bank transfers, cash machines and government data. It has a 64-bit block and a 56-bit key, which was marginal in the 1970s. By 1998 a machine built for $250,000 could find a key in 56 hours. DES itself is retired, but its design, the Feistel network, shaped a generation of ciphers, and Triple DES carried it for another twenty years.

How it works

DES encrypts a 64-bit block in 16 rounds of a Feistel network. The block is split into two 32-bit halves, L and R. In each round the right half goes through a function f together with a 48-bit subkey, the result is XORed into the left half, and the halves swap.

The beauty of the structure is that f never has to be inverted. To decrypt, run exactly the same 16 rounds with the subkeys in reverse order, and the XORs cancel one by one. The code listing on this page shows a Feistel network in a few lines, and the project's tests check that it decrypts even when f is a one-way function.

Inside f, the 32-bit half is expanded to 48 bits by repeating some bits, XORed with the 48-bit subkey, cut into eight 6-bit pieces, and each piece is replaced by a 4-bit value from one of eight S-boxes. The 32 bits that come out are permuted. The S-boxes are the only non-linear part of DES, and their design is what made it hold. The subkeys come from a key schedule that selects 48 of the 56 key bits for each round, with rotations in between. A fixed bit permutation before the first round and after the last adds nothing to the security. You can check the arithmetic yourself: our library runs the standard worked example, key 133457799BBCDFF1 and plaintext 0123456789ABCDEF, to the ciphertext 85E813540F0AB405, and its first-round subkey is 1B02EFFC7072, as in every textbook.

History

In the early 1970s the US National Bureau of Standards (now NIST) asked for proposals for a standard cipher, on 15 May 1973 and again on 27 August 1974. IBM's entry, based on Horst Feistel's earlier cipher Lucifer, was accepted. It appeared in the Federal Register on 17 March 1975, was approved in November 1976 and was published as FIPS 46 on 15 January 1977.

The design was controversial from the start, mainly for two reasons. First, the key had been shortened. IBM's earlier design had used a longer key, and DES ended up with 64 bits of which 8 are parity, leaving 56. A 1978 Senate committee found that the NSA had shortened the key and helped with the S-boxes but hadn't tampered with the algorithm. The NSA's declassified history says the agency pushed for a shorter key and that the two sides compromised on 56 bits. Second, critics feared the S-boxes hid a back door. In 1990 Eli Biham and Adi Shamir published differential cryptanalysis, and it emerged that IBM and the NSA had known of the technique in the 1970s and had chosen the S-boxes to resist it. The suspected trapdoor turned out to be a defense.

How it was broken

• Brute force. 2⁵⁶ is 72,057,594,037,927,936 keys. At a billion a second that's a little over two years on one machine, but a machine with many chips in parallel does far better. In July 1998 the Electronic Frontier Foundation's Deep Crack found a DES key in 56 hours, for about $250,000. In January 1999, together with distributed.net, it took 22 hours and 15 minutes. In 2006 the COPACOBANA machine did it in about 9 days with roughly $10,000 of hardware. Deep Crack was a political statement. It showed that a key length the US government had approved as the national standard wasn't safe.
• Differential cryptanalysis (Biham and Shamir, published around 1990–1991) breaks full 16-round DES with about 2⁴⁷ chosen plaintexts. That's less than brute force, but it takes a spectacular number of plaintexts.
• Linear cryptanalysis (Mitsuru Matsui, 1993) needs about 2⁴³ known plaintexts and was first run in practice in 1994.
• Weak keys. DES has four weak keys, for which encryption and decryption are the same operation, so encrypting twice returns the plaintext (our library confirms it for 0101010101010101, FEFEFEFEFEFEFEFE, E0E0E0E0F1F1F1F1 and 1F1F1F1F0E0E0E0E). There are also six pairs of semi-weak keys. Random keys almost never land on those.
• The complementation property. Encrypting the bitwise complement of the plaintext with the complement of the key gives the complement of the ciphertext. That halves a brute-force search, and our tests confirm it on the standard example.

The end of DES, and what replaced it

FIPS 46-3, in October 1999, made Triple DES the preferred form and allowed single DES only in legacy systems. AES was published as FIPS 197 on 26 November 2001, and NIST withdrew the DES standard on 19 May 2005. The 64-bit block, a limit for the larger ciphers of that generation too, came back as a weakness in the 2016 Sweet32 attack on Triple DES and Blowfish.

DES left behind the Feistel network, used in Blowfish, Twofish, Camellia and many others, and the idea that a cipher can be made of simple rounds repeated, which AES carries on in a different form.

The code

// A Feistel network: split the block in two halves; each round XORs a function of the right half (and a subkey) into the left half, then swaps.
// f can be anything at all, even a function that cannot be inverted: decryption runs the same rounds with the subkeys in reverse order.
function feistel(left, right, subkeys, f) {
  subkeys.forEach(function (k) {
    var next = left ^ f(right, k);        // the only place the secret goes in
    left = right; right = next;
  });
  return [right, left];                   // undo the last swap, so that the same code decrypts
}

Common questions