Differential Cryptanalysis

1. Core Idea: Track XOR Differences, Not Values

Differential cryptanalysis (Biham–Shamir, 1990) is a chosen-plaintext attack: feed pairs $(P, P')$ with fixed input difference $\Delta P = P \oplus P'$ and study output difference $\Delta C = C \oplus C'$ . Key insight: XOR differences propagate through linear parts (E, P, XOR-key cancel!) deterministically, and through S-boxes probabilistically — key bits cancel since $(X \oplus K) \oplus (X' \oplus K) = X \oplus X'$ .

ΔP → [E] → ΔE (deterministic) → XOR K cancels → S-box → ΔS with prob p
   → [P] → next round Δ (deterministic) → ... → ΔC with prob p1·p2·...

2. S-Box Difference Table (Worked Mini-Example)

For S-DES $S0$ , input difference $\Delta_{in} = 0001$ : try all 16 inputs $X$ , compute $S(X) \oplus S(X \oplus 0001)$ : output $\Delta = 00$ occurs 4/16, $\Delta = 01$ occurs 2/16, etc. — non-uniform! A uniform (ideal) S-box would give each $\Delta$ exactly 4/16. Entries like $P(\Delta_{out} = 00 | \Delta_{in} = 0001) = 4/16 = 1/4$ are the signal. DES S-boxes were secretly designed to minimize max differential probability ( $\le 1/4$ -ish) — the classified criteria.

Toy trace: 2-round cipher, characteristic $\Delta P = 00001000 \to \Delta C = 0100$ with $p = 3/8$ : send $\approx 4/p = 11$ pairs (rule: $c/p$ pairs for signal); majority-vote $\Delta C$ confirms characteristic; then guess last-round subkey bits: only the key making observed pairs fit the characteristic survives filtering.

3. Characteristics, Rounds, and Key Recovery

Chain single-round differentials into an $(r-1)$ -round characteristic with probability $P = \prod p_i$ (independence assumption, roughly holds).
Attack $r$ -round cipher: use characteristic over first $r-1$ rounds, then peel the last round: for each candidate last-subkey, partially decrypt $\Delta C$ one round and check the characteristic's predicted value — wrong keys randomize, right key scores $\approx P$ .
Data needed $\approx c/P$ chosen pairs; $P$ decays exponentially in rounds — hence round count is the defense.

4. Differential vs DES/AES (Numbers to Quote)

Cipher	Best characteristic $P$	Data needed	Verdict
8-round DES	$\approx 2^{-20}$	$\approx 2^{21}$ pairs — practical break	Reduced DES falls
15-round DES	$\approx 2^{-47}$	$\approx 2^{47}$ chosen plaintexts	Worse than $2^{55}$ brute force? Comparable — resists
Full 16-round DES	$\approx 2^{-55}$ – $2^{-60}$	$\ge$ brute force	Practically secure vs differential
AES-128	provably $\le 2^{-150}$ (4+ rounds, wide trail)	utterly infeasible	Immune by design (Wide Trail Strategy)

AES's Wide Trail (Rijndael designers, also differential pioneers) bounds every 4-round differential below $2^{-150}$ — differential attack needs more than the codebook. Design lesson: S-box max differential probability × branch number × rounds = security margin.

Exam Points

Difference-propagation diagram + key-cancellation line — 2-mark opener.
S-box non-uniformity + $c/P$ data rule with toy numbers — 5-mark core.
Last-round peeling logic (right key scores $P$ , wrong keys random) — favourite 2–3 marker.
Table: 8-round practical vs 16-round infeasible vs AES bound.

Differential Cryptanalysis