Matsui Line

Linear cryptanalysis · piling-up lemma · Matsui 1993

Watch sixteen key guesses compete on real evidence until the right one separates — the attack that broke DES, run on a cipher small enough to break in front of you.

Break the toy cipher ↓

Break the toy cipher

A cipher should look like a coin flip. This one doesn't, quite — and that is enough. Below is a real 8-bit cipher holding a secret key. You get to watch ordinary encrypted traffic, nothing chosen, nothing privileged. Guess the last four key bits sixteen ways, count which guess makes the cipher's leak show up, and the right one rises out of the noise.

The secret 4 hidden bits

A 16-bit key from crypto.getRandomValues(), in memory only. The attack never reads it.

Traffic to collect

Rounds in the cipher

Change the target

S-box

Target nibble of the final subkey

Approximation

Try to break the attack:

Why the wrong guesses are not quite noise (the wrong-key hypothesis)

2 Why did that work?

One chain, four links, all of it real. A single S-box is slightly unbalanced; the piling-up lemma carries that imbalance across rounds at a cost; whatever survives shows up as a bias in the counter for the correct key guess — and nowhere else. Each link below shows the value your current settings produce. Select one to open the exhibit behind it.

The five words you need

S-box: A small substitution table — here, 4 bits in, 4 bits out. It is the only non-linear part of the cipher, so it is the only part that can resist an attack made of linear equations.
Mask: A choice of which bits to add together. The mask 1001 means "take bit 3 XOR bit 0". Written <a, x>, read "a dot x".
Bias (ε): How far from a coin flip a relation is. If it holds 12 times in 16, the probability is 3/4 and the bias is 3/4 − 1/2 = 1/4. Zero bias means no information.
Trail: A chain of masks, one per round, connecting a plaintext relation to a last-round relation.
Known plaintext: The attacker sees plaintext/ciphertext pairs but does not get to pick them. Weaker than the chosen-plaintext access differential cryptanalysis needs — and far more realistic.

Where this comes from (primary sources)

Mitsuru Matsui, Linear Cryptanalysis Method for DES Cipher, EUROCRYPT 1993 — the attack, the piling-up lemma, and the success-rate table this demo reproduces in its tests.
Mitsuru Matsui, The First Experimental Cryptanalysis of the Data Encryption Standard, CRYPTO 1994 — full DES broken with 2⁴³ known plaintexts, executed in 50 days.
Howard Heys, A Tutorial on Linear and Differential Cryptanalysis — the S-box and worked piling-up example used here, and the source of two of this demo's known-answer tests.
Bogdanov et al., PRESENT: An Ultra-Lightweight Block Cipher, CHES 2007 — the second S-box, and the design criteria that cap its linear bias at 4/16.
Nyberg, Linear Approximation of Block Ciphers, EUROCRYPT 1994 — linear hulls, the reason the lemma's prediction and the measured bias part company in exhibit 5.

3 Inspect the cipher

An 8-bit block, a 16-bit key, and a 4-bit S-box applied to each nibble — the same toy SPN that Biham Lens attacks with differentials, so the two attacks can be compared on the same target. The highlighted state is what the attack aims at: everything after it is one substitution and one XOR, which four guessed bits can undo.

Send a plaintext through

4 Inspect one S-box leak

The linear approximation table. Each cell asks one question: over all 16 inputs, how often does this XOR of input bits equal that XOR of output bits? A balanced table would be all zeros. Ringed cells are the ones your attack is riding on. Select any cell to see the 16 rows behind its number.

5 Watch the bias compound

The piling-up lemma: chain biased relations together and the biases multiply. Because each is smaller than 1/2, the chain gets weaker every round — which is the entire reason ciphers have round counts.

What one more round costs the attacker

Does the lemma actually tell the truth? (measured against the real cipher)

6 How much traffic do you need?

Matsui's rule: the number of known plaintexts scales as the inverse square of the bias. Halve the bias — one more round — and you need four times the data. But the formula describes a single counter, and the attack ranks sixteen. Below, the formula and the measurement side by side.

Runs the whole attack end to end over 60 random keys at each data size — 300 complete attacks, off the main thread, with real progress. Not a curve drawn from the formula.

7 The pair-mate attack

Differential and linear cryptanalysis arrived three years apart and are usually taught together. They attack the same cipher from opposite directions.

Differential versus linear cryptanalysis, compared across seven properties.
	Differential — Biham & Shamir 1990	Linear — Matsui 1993
Access needed	Chosen plaintext — the attacker must submit pairs with a specific XOR difference.	Known plaintext — the attacker only watches traffic. A much lower bar.
What propagates	A difference between two encryptions of the same key.	A parity relation over a single encryption.
The S-box table	Difference distribution table (DDT) — how often ΔX becomes ΔY.	Linear approximation table (LAT) — how often a bit parity survives.
How rounds compound	Probabilities multiply along a characteristic.	Correlations multiply — the piling-up lemma.
Cost measure	Pairs needed ≈ 1 / characteristic probability.	Known plaintexts needed ≈ 1 / bias².
Round keys	Cancel out of the difference entirely.	Flip the sign of the relation, never its strength.
Against full DES	2⁴⁷ chosen plaintexts — more than exist in practice.	2⁴³ known plaintexts — and Matsui actually ran it, in 1994, in 50 days.

On this toy, the two attacks do not reach equally far — worth knowing rather than smoothing over. An 8-bit block gives a wrong key guess only 256 plaintexts to look wrong on, so the noise floor for a linear counter sits near 1/16, the same order as a three-round bias. Differential counting on this cipher works against a much quieter background. Verified here, exhaustively: no linear approximation over three rounds recovers the four-round subkey nibble reliably, while two rounds fall immediately. That is what the Add a round button is showing you.

8 What this is, and what it does not prove

Real

The cipher is real code — every ciphertext here came out of it.
The LAT is counted over all 16 inputs; nothing in it is asserted.
The trail search is exhaustive over the 8-bit mask space, not a heuristic sample.
The attack uses only plaintext/ciphertext pairs and its own guesses. It never reads the key.
Every counter you watch move is a count that was performed, including the partial ones.
Biases labelled "measured" come from running the cipher over its entire 256-plaintext codebook.

Not

Not production cryptography. An 8-bit block is broken by definition — the codebook fits on this page. It exists to make the attack visible.
Breaking this toy proves nothing about AES or DES. It shows the mechanism that forced their designs, at a scale you can watch.
The key schedule is deliberately trivial. Recovering four bits of the final subkey is not a full key recovery, and the demo does not claim one.
No multidimensional or zero-correlation linear cryptanalysis, and no attack on real DES — all three are far past what a browser tab should attempt.