Linear Cryptanalysis — known-plaintext linear approximation with a biased key parity bit

A known-plaintext attack that approximates a cipher with a linear (XOR) equation over plaintext, ciphertext, and key bits which holds with probability 1/2 + ε instead of exactly 1/2; enough pairs let that bias ε accumulate into evidence for a key parity bit.

The signal that gives it away

- The cipher is an SPN or Feistel network with a small, low round count — same family as differential cryptanalysis targets (toy DES, baby-AES, custom "N rounds" ciphers with N roughly ≤ 6–8). Full production round counts are the tell that this is *not* the intended path — see "What does NOT work". - You only have (or are only given) known plaintext/ciphertext pairs, with no control over their values — no chosen-plaintext oracle. This is the sorting signal against Differential Cryptanalysis — chosen-plaintext XOR-difference propagation through S-boxes: if the challenge hands you a pile of (P, C) pairs but won't let you pick P, linear is the productive direction, not differential. - The S-box is given, or recoverable, and has a biased Linear Approximation Table (LAT) — some input-mask/output-mask pair (a, b) has Pr[a·x = b·S(x)] far from 1/2. Challenge hints mentioning "approximation", "mask", "bias", or handing you raw S-box data are the tell, mirroring the DDT tell for differential. - You want key bits directly, not a distinguisher requiring you to steer inputs — linear cryptanalysis is the passive-data route when the differential attack's requirement of a chosen-plaintext oracle isn't available.

How to exploit it

1. Compute each S-box's Linear Approximation Table (LAT):

``python def lat(sbox, bits): n = 1 << bits L = [[-n//2]*n for _ in range(n)] # store bias*N offset for a in range(n): # input mask for b in range(n): # output mask c = sum(bin(((x & a) ^ (sbox[x] & b))).count('1') % 2 == 0 for x in range(n)) L[a][b] = c - n//2 return L # large |entry| = strong approximation ` A large |L[a][b]| means the linear relation a·x = b·S(x) holds with bias ε = L[a][b]/n` well away from 0 — that's your candidate single-round mask pair.

2. Chain masks across rounds with the Piling-Up Lemma: pick the highest-bias input/output mask through each round's S-box(es) so the output mask of one round lines up with the input mask of the next, producing one linear relation spanning several rounds. Under the (approximate) independence assumption, the combined bias is:

ε_total = 2^{n-1} · Π ε_i

for n chained per-round approximations — this is exactly what the LAT code above is set up to feed. Sign matters, not just magnitude: each ε_i carries a sign, and the product's sign determines whether the accumulated relation predicts the key-bit parity directly or its complement. Getting a sign wrong when chaining masks doesn't just weaken the bias — it can silently cancel it (see "What does NOT work").

3. Estimate the data complexity: known pairs needed scales as N ≈ 1/ε² (Matsui's own DES break used ≈2^43 known plaintexts against the full 16-round cipher — a concrete anchor for how fast this grows as ε shrinks with each extra round piled on).

4. Extend one round and recover key bits (Matsui's Algorithm 2 pattern): build the linear approximation over r-1 rounds, then for each candidate subkey covering the last round's relevant S-box(es), partially decrypt every known ciphertext one round back and evaluate the extended linear expression (plaintext bits ⊕ partially-decrypted intermediate bits) over all N pairs. Count how often it evaluates to 0.

5. Read off the key: the correct subkey candidate makes that count deviate the most from N/2 (either strongly above or strongly below — the direction of the deviation combined with the known sign of ε_total tells you the actual key-bit value, not just which candidate is "right"). Wrong candidates behave like a random walk around N/2. Repeat per key byte/S-box to assemble the full last-round subkey.

Related building blocks: S-box Analysis — profiling a cipher's S-box to pick the right statistical attack to profile the LAT/DDT and decide whether linear or Differential Cryptanalysis — chosen-plaintext XOR-difference propagation through S-boxes is the productive path for a given S-box and query model; Feistel Structure — the split-and-XOR shape that tells you which attack family applies to know which half of the state a round's mask actually touches; Linear Algebra over GF(2) — solving bit-level unknowns as a linear system mod 2 for the degenerate case below.

What does NOT work

- Throwing this at a full-round, real-world cipher without doing the arithmetic first. DES's S-boxes were hardened against *differential* cryptanalysis by design — a property only revealed decades after DES's 1977 release — but not against linear cryptanalysis, which wasn't publicly known until Matsui introduced it in 1993 and so played no role in the original S-box design; the resistance DES does have to linear attacks is incidental, not deliberate. Even so, Matsui's own practical break of full 16-round DES needed ≈2^43 known plaintexts and comparable computation — collectible in a research setting, not in a typical CTF's data budget. If a challenge presents genuine full-round DES or AES as a black box, the intended path is elsewhere (weak key, mode-of-operation flaw, side channel) — check 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 building a LAT. - Chaining the locally-best mask at each round without checking the resulting sign and magnitude of the combined bias. The Piling-Up Lemma's ε_total shrinks multiplicatively with every round added, and a greedy per-round choice of "biggest LAT entry" doesn't guarantee the best *chained* result — a large single-round bias with the wrong sign relative to the rest of the chain can partially or fully cancel the accumulated bias, leaving a key-recovery counter that never separates from noise no matter how many pairs you collect. Profile the whole chain's ε_total, not just each round's local maximum, before committing to a mask path. - Running the full statistical machinery when the S-box is affine/linear over GF(2). If the LAT (or DDT) is degenerate — the S-box already satisfies a linear relation with bias ε = ±0.5, i.e. probability 0 or 1 — there's no statistics to accumulate: the relation holds exactly, and the whole cipher reduces to a linear system solved directly with Linear Algebra over GF(2) — solving bit-level unknowns as a linear system mod 2. No LAT search, no pair counting needed; treating an already-linear S-box as a bias-accumulation problem wastes the entire setup. - Trusting the independence assumption behind the Piling-Up Lemma blindly. The 2^{n-1}·Πε_i estimate assumes each round's approximation behaves independently of the others; on some round-function/key-schedule combinations this overstates the real combined bias, and the predicted key-bit counter never spikes above noise regardless of how many known pairs are thrown at it. If the expected spike doesn't appear after collecting the estimated N ≈ 1/ε² pairs, don't assume it's purely a data-volume problem — re-derive the mask chain (a different path through the LAT) rather than just gathering more pairs. - Confusing "known-plaintext" with "free/easy". Linear cryptanalysis's lighter query requirement (no chosen-plaintext oracle needed) is an advantage over differential only when the challenge actually hands you a 2^{≈1/ε²}-sized pool of pairs; if the available known-plaintext budget is small relative to the bias the cipher's round count leaves you, linear is not the shortcut it looks like and the chosen-plaintext route (when available) may need fewer pairs for the same round depth.