Differential Cryptanalysis — chosen-plaintext XOR-difference propagation through S-boxes

A chosen-plaintext attack that tracks how an input XOR difference ΔP propagates to an output difference ΔC through a cipher's S-boxes; a high-probability path (a "characteristic") turns into a statistical distinguisher that leaks key bits.

The signal that gives it away

- The cipher is an SPN or Feistel network with a small, low round count — toy DES, baby-AES, or any custom cipher with "N rounds" explicitly small (roughly ≤ 6–8). Full-strength production ciphers (real 16-round DES, real AES) were specifically hardened against this attack, so seeing full round counts is itself a signal that plain differential cryptanalysis is *not* the intended path (see "What does NOT work" below). - You control the plaintext and can request encryptions of pairs (P, P⊕ΔP) for a difference you choose — a chosen-plaintext oracle, not just known-plaintext. - The S-box is given, or recoverable, and it is not a "perfect" S-box — i.e. its Difference Distribution Table (DDT) has non-uniform entries (some (Δin, Δout) pairs occur much more often than n/2^bits). Challenge hints that mention "characteristic", "propagation", "S-box table", or that hand you the S-box as raw data are a strong tell. - The block/key size is small enough that per-key-candidate partial decryption of many pairs is computationally cheap (a byte or nibble at a time), which is what makes the key-recovery step tractable.

How to exploit it

1. Recover or read the S-box(es) and build each one's Difference Distribution Table (DDT):

``python def ddt(sbox, bits): n = 1 << bits T = [[0]*n for _ in range(n)] for x in range(n): for dx in range(n): dy = sbox[x] ^ sbox[x ^ dx] T[dx][dy] += 1 return T # look for large non-trivial entries ` A large entry T[dx][dy] means Pr[S(x)⊕S(x⊕dx) = dy] = T[dx][dy]/n is well above the 1/n` baseline — that is your candidate single-round differential.

2. Chain per-round differentials into a characteristic covering r-1 rounds (one round short of the full cipher, so the last round's subkey is the thing you recover): pick the highest-probability (Δin → Δout) path through the round function, round after round. Under the usual (approximate) independence assumption, the characteristic's overall probability is the product of the per-round probabilities.

3. Estimate the data complexity: you need roughly N ≈ 1/p_characteristic chosen-plaintext pairs (with a small safety multiplier) for the right-key counter to separate from the noise floor of wrong-key guesses. If p_characteristic is too small for the plaintext budget the challenge gives you, this path won't converge — see below.

4. Collect pairs and attack the last round: encrypt N pairs (P, P⊕ΔP) through the target. For each candidate last-round subkey (byte/nibble at a time to keep the search small), partially decrypt both ciphertexts of every pair one round back and check whether the resulting difference matches the characteristic's predicted intermediate difference. Increment a counter per candidate key.

5. Read off the key: the correct subkey candidate produces a statistically significant spike in its counter; wrong candidates behave like uniform random noise. Repeat per key byte/S-box to assemble the full last-round subkey, then brute-force or unroll the remaining key schedule for any bits not directly covered.

Related building blocks: S-box Analysis — profiling a cipher's S-box to pick the right statistical attack to profile the DDT/LAT and decide whether differential or Linear Cryptanalysis — known-plaintext linear approximation with a biased key parity bit is the more productive path, and Feistel Structure — the split-and-XOR shape that tells you which attack family applies to know which half of the state a given round's difference actually touches.

What does NOT work

- Throwing this at a full-round, real-world cipher. DES's S-boxes were deliberately designed to resist differential cryptanalysis (Biham and Shamir's full 16-round DES break needed ≈2^47 chosen plaintexts — infeasible to actually collect); AES's S-box and diffusion layer are proven resistant by design. If a CTF challenge presents a genuine full-round DES or AES black box, the intended attack is elsewhere (weak key, mode-of-operation flaw, side channel) — see DES Weaknesses — recognizing and exploiting a 56-bit Feistel cipher and Block Cipher Modes of Operation — the mode carries the CTF vulnerability, not the primitive before spending time here. - Naively picking the "best single-round" differential and chaining it blindly. The per-round probabilities multiply, and after enough rounds even the best single-round differential can drop below what your plaintext budget can distinguish from noise. Profile the DDT first with S-box Analysis — profiling a cipher's S-box to pick the right statistical attack and sanity-check the *chained* probability against the number of pairs you can actually collect, rather than assuming the locally-best step is globally best. - Running the full statistical machinery when the S-box turns out to be affine/linear over GF(2). If the DDT is degenerate — every nonzero input difference maps to exactly one output difference with probability 1 — the S-box has no useful nonlinearity to exploit statistically; the whole cipher reduces to a linear system and is solved directly and exactly with Linear Algebra over GF(2) — solving bit-level unknowns as a linear system mod 2, no DDT, no pair collection, no counters. Check this before building a characteristic — it's a completely different (and much cheaper) attack, and treating a linear S-box as if it needed differential cryptanalysis wastes the entire setup. - Trusting the independence assumption blindly. The multiply-per-round probability estimate is an approximation; on some round-function/permutation combinations it overstates the real characteristic probability, and the predicted counter spike never separates from noise no matter how many pairs you throw at it. If the expected spike doesn't show up after collecting the estimated N, don't just collect more pairs — re-derive the characteristic (a different, possibly non-greedy, path through the DDT) rather than assuming it's a data-volume problem.