The Case of the Mystery Seeds · Chapter 7

Lattices

The prime-curve seeds keep just one byte from each turn of the generator, so each byte shows 8 bits of the state and hides 40. Guessing 40 bits is out of reach. But the bytes aren't independent: they're all chained together by the same rule. A beautiful piece of geometry turns that chain into a way to see the hidden bits.

Nib says: This is the hardest chapter, so it's mostly toys. First you'll tidy up a two-dimensional grid by hand. Then you'll watch an algorithm do the same thing in thirteen dimensions and pull out the hidden bits behind P-256's seed.

The problem

Write each state of the generator as its top byte (which we can see, because it's one byte of the seed) plus a hidden part under it: a number smaller than 240, about a trillion. Twelve consecutive bytes give us twelve hidden parts. Trying every combination is hopeless.

But they aren't twelve unrelated numbers. Each state is the previous one times a plus c, around a clock of 248. So once you pick the first hidden part, all the others are forced. That's still a trillion choices for the first one. What saves us is a single extra fact: every hidden part is small, less than 240 on a clock of 248. The right choice is the one that keeps all twelve small at once. Finding numbers that are all small at once is exactly what lattices are good at.

What is a lattice?

Take two arrows. Every point you can reach by adding whole numbers of each, forward or backward, is a point of the lattice. It looks like a tilted sheet of graph paper.

Here's the twist: very different-looking pairs of arrows can make exactly the same dots. Two long, nearly parallel arrows describe the grid badly; you'd never guess its smallest step from them. Two short, nearly square-on arrows describe it well. Turning a bad description into a good one is called lattice reduction.

Reduce a lattice

Gold and rust arrows describe the grid of dots. Each step subtracts the right whole-number multiple of the shorter arrow from the longer one, then swaps if needed. The dots never change; only the description does.

In two dimensions this trick goes back to Lagrange and Gauss, two centuries ago. In 1982, Arjen Lenstra, Hendrik Lenstra and László Lovász found a way to do it in any number of dimensions, quickly. Their method, called LLL, doesn't always find the very shortest arrow, but it reliably finds one that's short enough for an astonishing range of problems, from factoring polynomials to breaking weak cryptography.

Building the trap

Now the clever part, which is a standard recipe in cryptanalysis. We build a lattice in thirteen dimensions out of the generator's multiplier, the clock size 248 and our twelve visible bytes. It's arranged so that one of its points has coordinates equal to the twelve hidden parts (shifted to sit around zero), plus one marker coordinate. Every hidden part is small, so that point is unusually close to the origin, far shorter than a typical point of this lattice. The starting arrows are huge, around 248. LLL shrinks them, and the short point drops out as one of the new arrows, flagged by its marker.

For the curious: the actual lattice

Write state i as xi = 240·yi + zi, where yi is the visible byte and 0 ≤ zi < 240 is hidden. Since xi = ai·x0 + ci (mod 248), with ci the accumulated additions:

zi − H ≡ ai·(z0 − H) + di (mod 248), H = 239

where every di is known. The rows of the basis are (1, a, a², …, a11, 0), then 248·ei for i = 1…11, then (0, d1, …, d11, W) with weight W = 239. The lattice contains (z0−H, …, z11−H, W), a vector of length about 241, while the lattice's volume suggests typical vectors around 243.6. That gap is why LLL finds it. This is the classic attack on truncated linear congruential generators.

Watch the numbers shrink

Each square is one number in the 13 × 13 lattice built from P-256's first 12 bytes, colored by size. Press the button to run LLL on it, right here.

Before

After LLL

Before: most numbers are around 248.

Crack a prime-curve seed

Time for the real thing. Pick a curve. We use its first 12 bytes to build the lattice, run LLL, read off the hidden 40 bits of the very first state, and then run the generator forward. If we're right, it will reproduce all 20 bytes of the published seed, including the 8 we never used.

Recover the hidden state

The 20 bytes of the seed. Gold borders: the 12 we feed in.

Press Crack it.

All twenty bytes, 160 bits, regenerated from 96 bits of input. A wrong state would match the eight unused bytes by chance about once in 264. This is the same kind of evidence that convinced Anthropic: in their words, each recovered state regenerates all 160 bits of its seed.

One more thing to notice: the trick works on all five prime curves and only on them. Try the same lattice on B-163's bytes (Nib did, off-page) and nothing fits. Its origin is still open.

We now hold the exact internal state of a 1997 program, at the moment it produced P-256's seed. You know what comes next. Rewind.

Words in this chapter

Tap any word with a dotted gold underline to see what it means. Here they all are in one place.

Three things to keep

Check yourself

In the 2D toy, did the set of dots change when the arrows got shorter?

No. Subtracting a whole-number multiple of one arrow from another, or swapping them, describes exactly the same grid. Reduction only changes the description.

Why does it matter that the hidden parts are small, not just unknown?

Smallness is the only thing that singles out the right answer. The rule allows a trillion possible first states; only one makes every later hidden part small too, and "small in every coordinate" is what makes it a short lattice point.

We used 12 bytes but checked 20. Why does matching the other 8 matter so much?

Those 8 bytes (64 bits) were never used to find the state, so they're an independent test. A wrong state would match them only about once in 264 tries.

Go deeper