DSP Explorables

Breaking a block cipher (a taste)

A modern block cipher takes a block of bits and a key, and puts the block through round after round of substituting and shuffling until the output looks like nothing at all. Trying every key is hopeless, so how would anyone break one? This page shows one real technique, differential cryptanalysis, on a cipher small enough to watch every bit of, and carries out the attack in front of you.

1 · What “broken” means

On What we want from cryptography your browser timed itself trying keys: a 128-bit key would take it, and a million computers like it, far longer than the age of the universe. That’s the bar. A cipher counts as broken if there’s any attack that needs less work than trying every key, even if the attack is still far beyond anyone’s reach. For AES with a 128-bit key, the best known attack (published in 2011) needs about 2¹²⁶ steps: about four times faster than brute force, and so, strictly, a break, but no threat to anyone.

Attacks usually need something besides ciphertext: here, the ability to choose plaintexts and see them encrypted (a chosen-plaintext attack). The question an attack answers is how many it needs, and how much work it takes, compared with trying every key.

2 · A toy cipher to break

The cipher here is the one from Howard Heys’s tutorial on cryptanalysis: a block of 16 bits, and four rounds. Each round does three things:

Mix in a round key: XOR the block with 16 bits of key.
Substitute: cut the block into four groups of 4 bits, and look each up in the same table, an S-box:

in 0 1 2 3 4 5 6 7 8 9 A B C D E F
out E 4 D 1 2 F B 8 3 A 6 C 5 9 0 7
Permute: move the bits so that each S-box’s four outputs go to four different S-boxes in the next round (bit 2 of S-box 1 goes to bit 1 of S-box 2, and so on: a transpose).

in	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
out	E	4	D	1	2	F	B	8	3	A	6	C	5	9	0	7

After the fourth round’s S-boxes there’s no permutation (anyone could undo it, so it would add nothing), just a fifth round key. The five round keys are independent, 80 bits of key in all. Real ciphers make their round keys from one key with a key schedule; this toy skips that.

The toy cipher encrypting one block, every bit shown at every stage: U is what goes into a round’s S-boxes, V what comes out, W the bits after the permutation. Click plaintext bits to flip them: every bit that’s now different from before is coloured, all the way down. One flipped bit reaches one S-box, which changes one or more of its four outputs; the permutation sends those to different S-boxes; and by the end, on average about half the ciphertext’s 16 bits have changed (checked over 2,000 random keys and flips in the tests).

The coloured bits are the difference between two blocks: their XOR, 1 wherever they differ. Follow it down the figure and notice what each step does to it:

The key does nothing to it. Both blocks are XORed with the same key bits, and a bit XORed with the same thing twice is back where it started: $(p \oplus k) \oplus (p' \oplus k) = p \oplus p'$ . The difference passes through every round key untouched, and the attacker doesn’t need to know the key to know that.
The permutation moves it, predictably. The difference’s bits go where the permutation sends them.
The S-boxes are the only step that does something unpredictable to it. And even there, not entirely.

3 · Differences through one S-box

Take two inputs to the S-box that differ by some amount, Δin (the Greek letter delta, for difference). Their outputs differ by some Δout. Which Δout depends on which pair of inputs it is. For example, with Δin = B (1011):

inputs 0 and B give outputs E and C, which differ by E ⊕ C = 2;
inputs 1 and A give outputs 4 and 6, which differ by 2 again;
inputs 2 and 9 give outputs D and A, which differ by 7.

Going through all 16 inputs and counting how often each Δout turns up gives one row of the S-box’s difference distribution table. Do it for every Δin and you have the whole table: the odds of every difference getting through.

The S-box’s difference table. Row: the difference going in; column: the difference coming out; each entry, how many of the 16 inputs give that pair (darker is more). Click a row to see its 16 inputs worked out on the right. Row B has the table’s biggest entry: B goes to 2 for 8 of the 16 inputs, half the time. Most entries are 0: 153 of the 240 in rows 1 to F (pinned in the tests). Every entry is even, because inputs come in twos: if x gives some Δout, so does x ⊕ Δin, the other half of the same pair.

An ideal S-box would send every difference everywhere equally, so the table could tell an attacker nothing. A 4-bit S-box can’t: its entries are even, and searches through every 4-bit S-box have shown that the best any can do is a largest entry of 4 in 16. The S-box of PRESENT, a small cipher for cheap chips, is one of those (its table is checked in the tests). Heys’s S-box, chosen to teach with, has 8 in 16: a lever.

4 · Chaining through the rounds

Now string entries together. Start with two plaintexts that differ by 0B00 (in hex: bits 5, 7 and 8, all in the second S-box’s input), and follow the most likely thing at each step:

Round 1: S-box 2 gets Δin = B. Half the time (8 in 16) its Δout is 2, a single bit, which the permutation carries to S-box 3 of round 2, as Δin = 4.
Round 2: S-box 3 turns Δin = 4 into Δout = 6 for 6 of its 16 inputs. The permutation sends those two bits to S-boxes 2 and 3 of round 3, each as Δin = 2.
Round 3: each turns 2 into 5, 6 times in 16. The permutation sends those four bits to S-boxes 2 and 4 of the last round, each as Δin = 6: a difference of 0606 going into round 4.

Such a path is called a differential characteristic. If each step happens independently, its odds are the product:

\frac{8}{16} \times \frac{6}{16} \times \frac{6}{16} \times \frac{6}{16} = \frac{27}{1024} \approx 2.6\%

about 1 pair in 38. A pair of plaintexts that does follow it is called a right pair.

The characteristic, drawn on the cipher: the coloured bits are the difference it predicts at every stage, and the active S-boxes are labelled with their table entries. Nothing is known below the last round’s S-box inputs (?). Measure makes new random keys, encrypts random pairs of plaintexts that differ by 0B00, and counts how often the difference going into round 4 really is 0606.

The measured odds come out near 2.6%, but not exactly: other paths through the S-boxes also end at 0606, and the key decides which pairs take which path. Measured exactly, over all 65,536 plaintexts, 10 random keys gave between 2.5% and 2.8% (in the tests). For an attack, what matters is that it’s far higher than chance would give.

5 · The attack

The attacker can’t see what goes into round 4: only the ciphertext. But between the two are just the last round’s S-boxes and the last key, and the S-boxes can be run backwards. So the attacker guesses the key bits over S-boxes 2 and 4 (8 bits: only 256 guesses), and for each guess undoes the last key and S-boxes on both ciphertexts, and checks whether the difference there is 0606.

For the right guess, every right pair passes the check: about 1 pair in 38, plus a few that pass by chance. For a wrong guess, undoing the S-boxes with the wrong key scrambles things, and pairs pass only by chance, less often. Count, for each guess, how many pairs pass, and the right guess stands out:

counts = [0] * 256
for p in random_plaintexts:
    c1, c2 = encrypt(p), encrypt(p ^ 0x0B00)        # chosen plaintexts
    if differ_outside_boxes_2_and_4(c1, c2):        # can't be a right pair
        continue
    for guess in range(256):
        u1, u2 = undo_last_round(c1, guess), undo_last_round(c2, guess)
        if u1 ^ u2 == 0x0606:
            counts[guess] += 1
key_bits = counts.index(max(counts))

The continue is a filter that throws away hopeless pairs. A right pair has no difference going into S-boxes 1 and 3 of the last round, so none coming out, so its ciphertexts can only differ over S-boxes 2 and 4.

The attack, run live against a hidden key, for as many pairs as you choose. Each bar is one of the 256 guesses for the 8 key bits, and its height is how many pairs fit; the real key’s bar is blue (the attacker doesn’t know which it is, but you can). Watch it pull away as pairs come in. With few pairs, a wrong guess can tie or win: over 40 hidden keys, 100 pairs found the right bits 19 times and 200 pairs 36 times; 500 pairs found them every time (pinned in the tests, with fixed random numbers).

A few hundred chosen plaintexts and some tallying have found 8 bits of the last key, where brute force would face 80 bits. From here, another characteristic (ending in the other two S-boxes) finds the rest of the last key, or the remaining 8 bits can simply be tried. Then the last round can be peeled off, leaving a three-round cipher to attack the same way.

6 · Why real ciphers resist

Differential cryptanalysis was published by Eli Biham and Adi Shamir around 1990, and applied to DES, the standard cipher of the time: the full 16-round DES needed 2⁴⁷ chosen plaintexts, too many to be practical, but fewer than brute force. Then, in 1994, Don Coppersmith of IBM, one of DES’s designers, revealed that they had known about the technique in 1974, and chosen DES’s S-boxes to resist it, keeping it secret at the request of the US government. A cousin, linear cryptanalysis (Mitsuru Matsui, 1993), looks for bits whose XOR the cipher gets right more or less often than half the time; it broke DES with 2⁴³ known plaintexts.

AES was designed with both in mind, and its designers could prove a bound rather than hope for one. Its S-box works on 8 bits, and its best table entry is 4 in 256, so no S-box passes a difference with odds better than 2⁻⁶. And its mixing is built so that any characteristic through four rounds must pass through at least 25 active S-boxes (the wide trail design). So every four-round characteristic has odds of at most

\left(2^{-6}\right)^{25} = 2^{-150}

so an attack would need about 2¹⁵⁰ pairs to expect even one right pair, and there are only 2¹²⁷ pairs of 128-bit plaintexts with any given difference. The toy cipher’s weaknesses are exactly the levers AES removes: an S-box with a big entry, and mixing that lets a difference travel through just one active S-box a round.

Summary

A cipher is broken by any attack that beats trying every key, practical or not.
XOR differences pass straight through round keys, and the permutation moves them predictably; only the S-boxes are uncertain, and their difference table gives the odds.
Chained through the rounds, the best entries make a differential characteristic: here 0B00 to 0606 with odds of 27 in 1,024.
With chosen plaintext pairs, guessing the last round’s key bits and counting pairs that fit the characteristic finds them: 8 bits of the toy’s key from a few hundred pairs.
DES was designed to resist this, before it was public. AES proves a bound: under 2⁻¹⁵⁰ for any four rounds.