Differential Cryptanalysis Fundamentals

Differential cryptanalysis (Biham & Shamir, 1990) is a chosen-plaintext attack that analyzes how differences in plaintext pairs propagate through a cipher. By finding input differences that produce predictable output differences with high probability, an attacker recovers key bits statistically.

For XOR-based ciphers: difference ΔX = X XOR X'. For addition-based ciphers: difference ΔX = X - X' mod 2^n. XOR differences are most common since XOR commutes with XOR-keying (key schedule effects cancel in differential pairs).

A differential pair (P, P') has input difference ΔP = P XOR P'. After encryption: (C, C') with output difference ΔC = C XOR C'. A useful differential is ΔP → ΔC with high probability p — meaning many (P, P') pairs with difference ΔP produce output difference ΔC.

The DDT (Differential Distribution Table) counts: for each input difference Δx and output difference Δy, how many inputs x satisfy S(x) XOR S(x XOR Δx) = Δy. Divide by 2^n = probability. A good S-box has max DDT value 2 (probability 1/2^{n-1}) — no strong differentials.

For a block cipher with r rounds: find a sequence ΔP → ΔU1 → ΔU2 → ... → ΔU_{r-1} where each round transition has known probability. Multiply probabilities across rounds: overall probability p = p1 * p2 * ... * p_{r-1}. Attack uses 2/p pairs to recover last-round key.

With a high-probability r-1 round differential: collect N = 2/p plaintext pairs. For each candidate last-round key K': decrypt both ciphertexts one round, XOR the results, check if difference matches ΔU_{r-1}. The correct K' matches ~N/2 times; wrong keys match ~N/2^{bit_size} times.

AES S-box is the multiplicative inverse over GF(2^8) followed by an affine transform. Its DDT maximum is 4 (out of 256), giving differential probability ≤ 4/256 = 1/64 per S-box. AES has 4 S-boxes per round, but the Wide Trail design ensures full differential trails are below 2^{-100}.

Joan Daemen's Wide Trail design (used in AES/Rijndael): define branch number B of MixColumns. Any non-trivial differential trail through one round activates ≥ B active S-boxes. 4 rounds × 4 S-boxes per round guarantee ≥ 25 active S-boxes → prob < 2^{-100}.

Truncated differentials specify only part of the difference (e.g., only which columns are active, not the exact difference values). Enables attacks on more rounds where full differentials are too weak. Used against reduced-round AES, SERPENT, and other SPN ciphers.

An impossible differential is a pair (ΔP, ΔC) that can never occur for any key. Any key that maps an observed pair (P, P') with this difference is eliminated. By collecting enough pairs, all wrong keys are eliminated, leaving the correct key.

The boomerang attack (Wagner, 1999) combines two short differentials into an adaptive chosen-plaintext/ciphertext attack. It decomposes the cipher into two halves, each with a short high-probability differential, achieving an attack longer than any single differential would allow.

What is the purpose of the Differential Distribution Table (DDT) in cryptanalysis?

Differential cryptanalysis exploits high-probability input→output difference propagation. AES resists it via its DDT-optimal S-box and Wide Trail design. Next: linear cryptanalysis and approximation tables.