An Interactive Guide to DES

DES, the Data Encryption Standard, is where modern block ciphers start. IBM designed it in the early 1970s, the NSA reviewed it, and NIST standardized it in 1977. For nearly 20 years it was the default choice for encrypting sensitive data in banking, government, and early internet protocols.

Below I’ll walk through how DES scrambles a block using a structure called a Feistel network, the same structure that later showed up in Blowfish, Twofish, and plenty of other ciphers.

# The block and the key

DES encrypts data 8 bytes (64 bits) at a time, using a 64-bit key. That key isn’t really 64 bits of secret though. 1 bit in every byte is a parity bit, left over from a time when hardware needed a cheap way to detect transmission errors. So the real key space is 56 bits, 8 bytes with the low bit of each byte dropped.

Enter a plaintext block and a key below, both as hex. The key is hidden by default since it must stay secret. Click the eye icon to reveal it.

# The Feistel structure

DES doesn’t transform its whole block at once. It splits the 64-bit block into 2 halves, L and R, each 32 bits, and only ever transforms 1 half per round.

In each round, the left and right halves are evolved as follows:

New left half is the old right half. New right half is the old left half $\text{XOR}$ed with a function $f$ applied to the old right half and the round’s subkey.

This is a Feistel network, named after Horst Feistel, who developed the structure at IBM. Its appeal is that $f$ doesn’t need to be reversible at all. Whatever $f$ computes, decryption just runs the same rounds in reverse order with the same subkeys, and the XOR undoes itself. That freed the designers to make $f$ as messy and nonlinear as they wanted, without worrying about inverting it.

Before any of that, the block passes through an initial permutation (IP), which just reorders the 64 bits according to a fixed table. It has no cryptographic purpose. It exists to make the bit layout convenient for the hardware DES was designed to run on in the 1970s. At the end, an inverse permutation (FP) undoes it.

# The Feistel function

Everything that gives DES its security happens inside $f$. It takes the 32-bit right half and that round’s 48-bit subkey, and produces a new 32-bit value in 4 steps.

# Expansion

The 32 bits of $R$ are expanded to 48 bits by duplicating some bits, using a fixed table $E$. This is done to align $R$ with the 48-bit subkey for $\text{XOR}$. And it also means each output bit depends on more than 1 input bit, an early step toward spreading influence across the block.

# XOR with subkey

Expanded 48 bits are $\text{XOR}$ed with the round’s subkey. This is where the secret enters, the only place in $f$ that touches the key.

# Substitution

A substitution box (aka. S-box) is a fixed lookup table that maps a small input to a small output with no formula connecting the two. DES has 8 S-boxes. Each takes 6 input bits and produces 4 output bits. The first and last input bit select a row, the middle 4 bits select a column, and the value at that row and column is the output. The S-box is a lookup table of 4 rows and 16 columns with 4 bits per entry. The behavior of a single S-box is not linear and cannot be described by simple algebra.

The 48 bits coming out of the XOR step are split into 8 groups, 1 group per S-box. This is the only nonlinear step in the entire cipher. Without it, DES would just be a stack of XORs and permutations, solvable with linear algebra.

# Permutation

The 32 bits coming out of the S-boxes are shuffled by a fixed table called $P$, spreading each S-box’s output bits across the positions the next round’s expansion will pick up.

Click a 6-bit group below to see exactly how its row and column pick a value out of that S-box.

# The key schedule

A single 56-bit key isn’t used directly. DES expands it into 16 subkeys, 1 per round, each 48 bits.

The 56-bit key (parity bits already dropped) splits into two 28-bit halves, $C$ and $D$. Before each round, both halves rotate left by 1 or 2 bits, following a fixed schedule. The rotated halves are then combined and squeezed from 56 bits down to 48 through a second fixed table, $PC\text{-}2$, which also drops some bits permanently.

Because the rotation amounts are small and mostly 2, adjacent round keys share most of their bits. That’s a real weakness, and it’s part of why differential cryptanalysis, discovered publicly in the late 1980s, could be pointed at DES at all.

# Putting it together

Run all 16 rounds and watch $L$ and $R$ evolve. After round 16, the halves are swapped back and passed through $FP$ to produce the ciphertext.

# Small changes, big effect

A well-designed block cipher should turn a single flipped input bit into a completely different output. Flip 1 bit of the plaintext below and see how much of the 64-bit ciphertext changes.

# Why it stopped being safe

Nothing about the Feistel structure or the S-boxes was ever broken outright, but 2 academic attacks came close enough to matter, and a third, more boring problem is what actually finished DES off.

# Differential cryptanalysis

Published by Eli Biham and Adi Shamir in 1990, this attack takes pairs of plaintexts with a fixed difference between them. Encrypting both and tracking how that difference moves through each round exposes a bias in DES’s S-boxes, since some output differences occur more than 50% of the time. An attacker who knows the bias can work backward from enough ciphertext pairs to recover key bits. The method cuts the effective key search from $2^{56}$ down to $2^{47}$.

# Linear cryptanalysis

Published by Mitsuru Matsui in 1993, this attack works differently. It builds a single linear equation, using only $\text{XOR}$, over certain plaintext bits, ciphertext bits, and key bits. Across all 16 rounds combined, that equation holds true slightly more or less than half the time. That small bias, multiplied over enough samples, lets an attacker guess key bits faster than random guessing. This method cuts the search space to $2^{43}$.

Neither attack ever broke DES in practice. Differential cryptanalysis needs about $2^{47}$ chosen plaintexts encrypted under the same key, and linear cryptanalysis needs about $2^{43}$ known plaintexts under the same key. Real systems don’t encrypt anywhere near that much data with 1 key. Still, DES is vulnerable to both, since both reduced the key space well below the 56 bits it was supposed to offer, and that mattered even before brute force became feasible on its own.

# Brute force

56 bits means $2^{56}$ possible keys, about 72 quadrillion. In 1977 that was outside anyone’s budget. By the 1990s, it wasn’t.

In 1998 the Electronic Frontier Foundation built a machine called Deep Crack, purpose-built hardware that did nothing but try DES keys. It cost about $250,000 and found a key in 56 hours. A year later, combined with a distributed network of computers, the same search took under 24 hours. Once a key search fits in a day on hardware anyone could plausibly build, the cipher is done, regardless of how sound its internal design is.

# The replacement

The stopgap was Triple DES (3DES), which runs the DES algorithm 3 times in a row, typically encrypt, decrypt, encrypt, with either 2 or 3 independent keys. That pushes the effective key strength up to 112 or 168 bits, and it bought the industry another decade. But it’s slow. Running the same cipher 3 times costs 3 times the compute, and DES’s 64-bit block size (shared with 3DES) has its own weaknesses at the volumes of data modern systems handle.

NIST ran an open competition in the late 1990s specifically to find a replacement, drawing on 20 years of cryptanalysis of DES to demand a bigger block, a bigger key, and a structure less prone to the weaknesses DES had accumulated. That competition ended in 2001 with a new standard.

DES is retired now. NIST withdrew its approval in 2005, and even 3DES is being phased out. But the Feistel network it introduced didn’t retire with it. Blowfish, Twofish, and large parts of modern block cipher design still lean on the same idea Horst Feistel had at IBM, that a function doesn’t need to be reversible if you’re clever about how you use it.