Week 3 · Block ciphers · KL 7.2

Differential cryptanalysis

The attack that shaped the design of AES, run on a cipher small enough to see all of it. Pick a pair of plaintexts that differ in a chosen way, watch the difference travel through the rounds, and use the one place it behaves predictably, the S-box, to read off the last round key.

A one-nibble, two-round cipher

The block is a single 4-bit nibble. Each round XORs in a round key and pushes the result through a 4-bit S-box (the one from Heys' tutorial), and a final key is XORed on at the end. There is no permutation layer because there is only one nibble to permute. Three round keys, sixteen possible values each, and an attacker who can ask for the encryption of any plaintext they like.

P→ ⊕ K₀→ S→ ⊕ K₁→ S→ ⊕ K₂→ C

The whole attack rests on one algebraic fact. XORing a key never changes the difference between two values, because (x ⊕ k) ⊕ (x′ ⊕ k) = x ⊕ x′. So the key steps are transparent to differences, and the S-box is the only place a difference can change. If the S-box changes differences in a predictable way, the attacker can predict a difference deep inside the cipher without knowing any key at all.

1 · The difference distribution table

For every input difference ΔX (rows) and output difference ΔY (columns), the table counts how many of the sixteen inputs x satisfy S(x) ⊕ S(x ⊕ ΔX) = ΔY. An ideal S-box would spread every row evenly. This one does not: row B puts half of its mass on column 2. That single entry is the vulnerability. Click any cell to choose the differential used in the rest of the page.

2 · Chosen pairs through the cipher

The attacker asks for the encryption of every plaintext P together with its partner P ⊕ ΔP. That gives eight pairs. In a right pair the first S-box sends ΔP to the expected ΔV, and from there the difference is fixed all the way to the input of the last S-box, even though the attacker never sees those inner values. Choose a pair to trace it. The keys are shown here for teaching; the attacker does not know them.

3 · Recovering the last round key

Why K₂ and not K₀ or K₁? Because K₂ is the only key that sits between something the attacker can see and something the attacker can predict. Read the picture from both ends.

Where the forward prediction meets the backward computation The cipher drawn left to right. A teal arrow runs forward from the plaintext to the input of the last S-box: the difference there is predicted without any key. An orange arrow runs backward from the ciphertext to the same point: computing it needs the inverse S-box and a guess of K2. The two meet at the inputs to the last S-box. Forward, no key needed on a right pair the difference here is ΔV, because ⊕ K₀ and ⊕ K₁ never change a difference P ⊕ K₀ S ⊕ K₁ S ⊕ K₂ C u, u′ : the inputs to the last S-box Backward, from the ciphertext undo ⊕ K₂ (needs a guess of K₂), then undo S with the public inverse table

K₀ is invisible to differences, so no difference test can identify it. K₁ is buried behind the second S-box, so the attacker cannot reach it from the ciphertext without first passing K₂. K₂ is the first key in the way, so it is the first one recovered. Once it is known, strip the last round off every ciphertext and the same attack lands on K₁.

Step through one guess on one pair

Pick a pair and a guess, then walk the attacker's computation one operation at a time. Use the buttons, or the arrow keys.

That is the whole procedure. Written out, for each guess g and each pair:

  1. Take the two observed ciphertexts C and C′.
  2. Undo the last key under the guess: y = C ⊕ g and y′ = C′ ⊕ g.
  3. Undo the last S-box with the inverse table: u = S⁻¹(y) and u′ = S⁻¹(y′).
  4. Form the recovered difference u ⊕ u′.
  5. Score a hit if it equals ΔV. The guess with the most hits over all pairs is the attacker's answer.

If g is the true K₂, then u and u′ are the real inputs to the last S-box, and their difference is ΔV on every right pair. If g is wrong, step 2 produces the wrong values, step 3 pushes them through the wrong branch of the inverse S-box, and the difference that comes out is unrelated to ΔV. It matches only by chance.

The inverse S-box

Step 3 needs S⁻¹, which the attacker can tabulate because the S-box is public. The two highlighted entries are the ones step 3 uses for the pair you selected in section 2, which is also the outlined row in the table below.

The computation for one guess

pairCC′C ⊕ gC′ ⊕ g S⁻¹(C ⊕ g)S⁻¹(C′ ⊕ g)u ⊕ u′= ΔV?

All sixteen guesses

Each bar is the hit count from the table above, for one value of g. Click a bar to inspect that guess.

With only eight pairs the tall bar occasionally ties or loses. Real attacks fix this by collecting more pairs, or by running two independent differentials and keeping the key guess both agree on. Try a weaker cell of the table, such as a 4-of-16 entry, and watch how much noisier the picture gets: the attack's data cost is roughly the inverse of the differential's probability.

Why this does not break AES

AES was designed after differential cryptanalysis was published, and its authors built the defence in. The S-box is 8 bits wide and chosen so that no entry of its difference distribution table exceeds 4 out of 256. The ShiftRows and MixColumns layers guarantee that any difference passes through at least 25 S-boxes over four rounds, so the probabilities multiply down past the point where an attacker could ever collect enough pairs.

best S-box differential
2⁻⁶

Largest table entry is 4 of 256, versus 8 of 16 for the toy S-box above.

active S-boxes in 4 rounds
≥ 25

The wide-trail bound from ShiftRows and MixColumns together.

best 4-round trail
≤ 2⁻¹⁵⁰

Far below 2⁻¹²⁸: there are not enough plaintexts in the world to detect it.

AES-128 has ten rounds. The best published attacks in this family reach about seven rounds, and only with more chosen plaintexts than anyone could ever obtain.

← back to all demos