Data Encryption Standard

Aka. DES. Published in 1975 and standardized in 1977. Superseded by AES (1998/2001). The interactive guide to DES visualizes the Feistel rounds and key schedule.

DES is a Feistel cipher. It splits each block into 2 halves and runs a keyed round function many times, so the same structure encrypts and decrypts.

Design Parameters

• Block length $n = 64$ bits.
• Number of rounds $r = 16$.
• Round function combining substitution and permutation.
• 16 round keys of 48 bits each, from a subkey generation algorithm.
• Secret key length 56 bits.

Permutation Tables

DES is built from fixed lookup tables. Every one is read the same way. Output bit $i$ is copied from the input bit whose position is the $i$-th table entry.

• Reordering
  A table that lists every input position exactly once drops and duplicates nothing. $\text{IP}$, $\text{IP}^{-1}$, and $P$ are of this kind.
• Expansion
  A table longer than its input repeats some input positions. $E$ does this, listing 48 positions over a 32-bit input.
• Compression
  A table shorter than its input omits some positions. $\text{PC-1}$ and $\text{PC-2}$ do this, dropping key bits.

Substitution Boxes

An S-box maps 6 input bits to 4 output bits through a fixed table of 4 rows and 16 columns.

The outer 2 bits (first and last) select 1 of 4 rows. The middle 4 bits select 1 of 16 columns. The table entry at that row and column is the 4-bit output.

In DESm there are 8 S-boxes, and they all are different, fixed, and published in the standard. They are the only non-linear step in DES and the most security-critical component.

S-box 1:

Take input $011011$.

• Outer bits $0$ and $1$ give row $01 = 1$.
• Middle bits $1101$ give column $13$.
• Row $1$, column $13$ holds $5$, so the output is $0101$.

Round Function

The round function $f(R, k_i)$ takes a 32-bit half $R$ and the 48-bit round key $k_i$, returning 32 bits. Round $i$ applies it to the previous round’s right half $R_{i-1}$. It is computed in order.

Expansion Permutation

Expands the 32 input bits to 48 by the expansion table ($E$). Split the 32 input bits into 8 consecutive groups of 4. Output block $j$ is group $j$ plus 1 bit borrowed from each side: the last bit of group $j-1$ in front, the first bit of group $j+1$ behind, wrapping at the ends. Each block is 6 bits and feeds 1 S-box.

Intermediate Steps

• Key mixing
  XOR the 48-bit expanded value with the round key $k_i$.
• Split
  Cut the 48-bit result into 8 blocks of 6 bits, one per S-box.
• Substitution
  Each S-box maps its 6-bit block to 4 bits, by the lookup defined above.
• Combine
  Concatenate the eight 4-bit outputs into 32 bits.

Permutation

Permute the 32 bits by the P-box. Each S-box output bit is scattered to a different S-box’s input group in the next round, so the 4 bits from one S-box never stay together.

Key Schedule

The 64-bit input key has every 8th bit as a parity bit, so the effective key length is 56 bits.

Permuted Choice 1

Selects 56 bits from the 64-bit key, skipping the 8 parity bits, and permutes them. The first 28 outputs form $C_0$, the last 28 form $D_0$.

Rotation

Each round left-rotates $C_{i-1}$ and $D_{i-1}$ by $p_i$ positions to get $C_i, D_i$, where $p_i$ is 1 or 2 as fixed by the schedule below.

$C_i$ and $D_i$ are 28-bit registers. The 16 shifts sum to 28, so a full left-rotation brings $C_{16}, D_{16}$ back to $C_0, D_0$. Decryption uses this to walk the schedule backwards by right-rotating instead.

Permuted Choice 2

Rejoins $C_i, D_i$ into 56 bits, then selects and permutes 48 of them to produce round key $k_i$. The 8 unused positions are 9, 18, 22, 25, 35, 38, 43, and 54.

Encryption

DES encrypts one 64-bit block through 5 stages, using the 16 round keys $k_1, \dots, k_{16}$ from the key schedule and the round function $f$.

Initial Permutation

Apply $\text{IP}$ to the 64-bit input block, reordering all 64 bits.

Split

Take the first 32 permuted bits as $L_0$, the last 32 as $R_0$. Reading the entries, every even-positioned input bit lands in $L_0$ and every odd-positioned bit lands in $R_0$.

Feistel Rounds

Run 16 rounds. Round $i$ sets $L_i = R_{i-1}$ and $R_i = L_{i-1} \oplus f(R_{i-1}, k_i)$.

Rejoin

Concatenate as $R_{16} L_{16}$, halves swapped, into a 64-bit block. The swap makes decryption run the exact same steps as encryption.

Final Permutation

Apply $\text{IP}^{-1}$ to produce the ciphertext block. It is the exact inverse of $\text{IP}$. Input bit 58 sits at position 1 after $\text{IP}$, so $\text{IP}^{-1}$ has 58 as its 40th entry, sending it back. Applying it after the rounds cancels the initial reordering.

Decryption

DES decrypts with the exact same algorithm and tables, feeding the round keys in reverse order $k_{16}, \dots, k_1$.

The Feistel round is invertible no matter what $f$ computes. Given $L_i = R_{i-1}$ and $R_i = L_{i-1} \oplus f(R_{i-1}, k_i)$, the previous half is recovered as $L_{i-1} = R_i \oplus f(L_i, k_i)$. The final half-swap on the encryption side lines the ciphertext up so the same round formula runs unchanged.

The round keys in reverse come for free from the schedule. Right-rotating $C_i, D_i$ by the same $p_i$ schedule regenerates $k_i$ from $k_{i+1}$ without re-running PC-1.

Security Properties

• Avalanche effect
  A single plaintext bit difference should flip about 50% of ciphertext bits. $E$ feeds 16 of the 32 half-bits into 2 S-boxes each, and $P$ scatters each S-box’s 4 output bits into different S-boxes in the next round, so a local change spreads fast.
• Key size
  56 bits is the reason DES fell. A brute-force search averages $2^{55}$ steps, feasible on dedicated hardware such as the EFF Deep Crack machine in 1998.
• S-box strength
  The S-boxes were chosen to resist differential cryptanalysis, a technique not public until 1990.

Variations

Double DES

Encrypting twice with the same key, $c_2 = E_k(E_k(m))$, adds no strength. The single 56-bit key is still found by brute force in $2^{55}$ steps on average. DES is not a group, so the double encryption is not equal to a single DES under some other key. That rules out a trivial break but does not enlarge the key.

Double DES with 2 Keys

$c_2 = E_{k_2}(E_{k_1}(m))$ with 2 independent 56-bit keys. The key space is 112 bits, but the meet-in-the-middle attack inverts the 2 layers separately and cuts the effective strength to about $2^{57}$.

Triple DES (3DES)

$c = E_{k_3}(D_{k_2}(E_{k_1}(m)))$, effective key length 168 bits. The middle step is a decryption so that setting $k_1 = k_2 = k_3$ makes 3DES compute plain DES. 3DES hardware then stays interoperable with single-DES peers.

2-Key 3DES

Setting $k_1 = k_3$ gives $c = E_{k_1}(D_{k_2}(E_{k_1}(m)))$, effective key length 112 bits. The 3 forms are the standard keying options. 3 independent keys is option 1, $k_1 = k_3$ is option 2, all keys equal is option 3. NIST has since deprecated 3DES in favour of AES.

Why Not Extend DES

3DES already composed DES instead of redesigning it. 3 problems remained.

• Block size
  Still 64 bits. Birthday-bound collisions appear after about $2^{32}$ blocks under 1 key, no matter the key length.
• Composition loss
  Double DES’s 112-bit key space drops to about $2^{57}$ effective strength under a meet-in-the-middle attack. Reaching close to the nominal strength needs the full 3-stage 3DES structure.
• Speed
  3DES runs the DES round function 3 times per block, on top of DES already being tuned for 1970s hardware rather than software.

Widening DES’s key or block does not inherit its security margin. The margin comes from the specific interaction between the 16 rounds, the Feistel structure, and the 6-bit S-boxes, not from a formula that scales with the numbers. Changing any of those needs the same fresh cryptanalysis a new cipher would. NIST ran an open competition instead, which also settled decades of suspicion around the NSA’s undisclosed role in choosing the original S-boxes.

Attacking DES

A brute-force known-plaintext attack averages $2^{55}$ steps given the 56-bit key.

Meet in the Middle Attack

A known-plaintext attack. Breaks a double encryption $c = E_{k_2}(E_{k_1}(m))$ whose 2 layers can be inverted independently. Trades storage for time instead of searching all $2^{112}$ key pairs.

• Take one known plaintext-ciphertext pair $(m, c)$.
• For every key $k_1$, compute $x = E_{k_1}(m)$ and store $(x, k_1)$ in a table.
• For every key $k_2$, compute $x' = D_{k_2}(c)$ and look up $x'$ in the table.
• Each hit $x = x'$ gives a candidate pair $(k_1, k_2)$ that agrees at the midpoint.
• Test surviving candidates against a second known pair to drop false matches.

Take $b$-bit keys. The first loop runs $2^b$ encryptions and fills a table of $2^b$ entries. The second loop runs $2^b$ decryptions. The total is $2^b + 2^b = 2^{b+1}$ cipher calls, with $2^b$ storage for the table. Brute force instead tries every $(k_1, k_2)$ pair, $2^b \cdot 2^b = 2^{2b}$ calls, with no storage. For double DES $b = 56$, so the work drops from $2^{112}$ to roughly $2^{57}$.

Linear Cryptanalysis

A known-plaintext attack, published by Matsui in 1993.

Notation. $m_i$ is bit $i$ of the plaintext, $c_j$ bit $j$ of the ciphertext, $k_l$ bit $l$ of the key. $\bigoplus$ is XOR taken over a chosen set of positions: $I$ in the plaintext, $J$ in the ciphertext, $L$ in the key. XOR of a set of bits is 1 when an odd number of them are 1, so each side of the equation is the parity of its selected bits.

A linear approximation claims these 2 parities are equal:

The left side is built only from bits the attacker can see. The right side is 1 fixed bit, the parity of some unknown key bits. It never changes, since the key is fixed.

Example. With $I = \{4, 9\}$, $J = \{7\}$, $L = \{2, 5, 18\}$ the equation reads

For a random pair the left side is 0 half the time and 1 half the time, so it says nothing about the right side. The DES S-boxes are slightly unbalanced, so for a well-chosen $I, J, L$ the left side equals the right side with probability $\tfrac{1}{2} + \varepsilon$ for some bias $\varepsilon \ne 0$.

• Collect $N$ known pairs $(m, c)$.
• Compute the left side of each.
• If the left side is 0 in more than half the pairs, the fixed right side is 0, otherwise 1.

That recovers 1 bit of information about the key, the parity $k_2 \oplus k_5 \oplus k_{18}$ in the example. The answer is right with confidence that grows in $N$, needing about $\varepsilon^{-2}$ pairs. Enough different equations pin down enough key-bit parities to solve for the key. Full DES falls to about $2^{43}$ known pairs, below brute force but far more plaintext than an attacker usually holds.

Differential Cryptanalysis

A chosen-plaintext attack, made public by Biham and Shamir around 1990.

Works with the XOR difference of a plaintext pair $m, m'$, not the values. Fix an input difference $\Delta m = m \oplus m'$ and follow the difference forward through the rounds.

• The linear steps $E$, $P$, $\text{IP}$, $\text{IP}^{-1}$ satisfy $g(x) \oplus g(x') = g(x \oplus x')$. Their output difference is a fixed function of the input difference, free of the actual values and of the key.
• An S-box is not linear. For a given input difference its output difference is not fixed, but some output differences are far more likely than others. The difference distribution table counts, for each pair of input and output differences, how many of the 64 input pairs produce it.

Chaining high-probability S-box differences across rounds gives a characteristic. This is a predicted difference through the first 15 rounds that holds with some probability $p$.

• Encrypt many plaintext pairs with input difference $\Delta m$.
• For each guess of the last round key feeding the active S-boxes, undo the last round and check whether the round-15 difference matches the characteristic.
• The correct guess matches at rate $p$, wrong guesses at the lower random rate. The guess with the most matches is the key.

The pair difference never depends on $k$, since XORing the pair cancels the equal round-key terms. Full DES needs about $2^{47}$ chosen plaintexts. The S-boxes were tuned in 1974 to resist exactly this, so the attack does not threaten DES in practice.