Four numbers and the rule is yours

The two rungs below measure how well a generator spreads its output over space. That is the right question for a simulation, where the points are being used to sample a region, and it is entirely the wrong question when somebody is allowed to look at the output and act on it.

The question then is: given some of the outputs, can the rest be worked out? For a linear congruential generator the answer is yes, and it takes very little.

The solution #

Suppose $x_{n+1} = a x_n + c \bmod m$ with $a$ and $c$ unknown and $m$ known.

Take three consecutive outputs $x_0$, $x_1$, $x_2$. Subtracting consecutive relations removes the increment:

$$x_2 - x_1 \equiv a(x_1 - x_0) \pmod m.$$

That is one congruence in one unknown. If $x_1 - x_0$ is invertible modulo $m$ — which it is unless it shares a factor with $m$ — then

$$a \equiv (x_2 - x_1)(x_1 - x_0)^{-1} \pmod m,$$

and the inverse is computed by the extended Euclidean algorithm in a few steps.

With $a$ in hand, $c \equiv x_1 - a x_0 \pmod m$ directly.

Three outputs give the rule and a fourth confirms it. Everything after is then determined.

The one obstruction is the invertibility, and it is minor. If $x_1 - x_0$ shares a factor $g$ with $m$, the congruence determines $a$ only modulo $m/g$, leaving $g$ candidates — and a fourth output rules out all but one of them. Since $g$ is typically small and can be handled by trying every candidate, the method never really fails; it occasionally needs one more number. A method whose worst case is “use a fifth output” is not a method anybody defends against.

When the modulus is unknown too #

The above assumes $m$ is known, which is usually true — moduli are published — and is not necessary.

Given six or so outputs, form the differences $d_i = x_{i+1} - x_i$. These satisfy $d_{i+1} \equiv a d_i$, so the quantities

$$t_i = d_{i+2}d_i - d_{i+1}^2$$

are all congruent to zero modulo $m$, hence are multiples of $m$ over the integers. Taking the greatest common divisor of several of them gives $m$, usually exactly and always up to a small factor.

So the modulus, the multiplier and the increment come out of about six outputs, by arithmetic that a person could do by hand. There is no security here of any kind, and the point is worth stating plainly because linear generators were used for exactly such purposes for a long time.

The greatest-common-divisor step deserves a note, because it is a small piece of luck rather than a general technique. Each $t_i$ is a multiple of $m$; two multiples of $m$ have a greatest common divisor that is a multiple of $m$ and is usually $m$ itself, because two random multiples share no further factor with probability about $6/\pi^2$. Taking three or four of them makes the failure probability negligible. A quantity known to be a multiple of an unknown number is nearly as good as the number, which is a habit worth having and is the same trick that recovers a hidden modulus anywhere it appears.

A worked example, by hand #

The algebra is short enough to carry out on paper, and doing it once removes any suspicion that a computer is required.

Take a generator modulo $1000$ that produces $x_0 = 7$, $x_1 = 320$, $x_2 = 613$.

The differences are $d_0 = 313$ and $d_1 = 293$. So $293 \equiv a \cdot 313 \pmod{1000}$, and $a$ is $293$ times the inverse of $313$ modulo $1000$.

Finding that inverse is the extended Euclidean algorithm on $313$ and $1000$: $1000 = 3\cdot313 + 61$, then $313 = 5\cdot61 + 8$, then $61 = 7\cdot8 + 5$, then $8 = 1\cdot5 + 3$, then $5 = 1\cdot3 + 2$, then $3 = 1\cdot2+1$. Running the remainders back up gives $313^{-1} \equiv 377 \pmod{1000}$, which checks: $313 \times 377 = 118001$.

So $a \equiv 293 \times 377 = 110461 \equiv 461 \pmod{1000}$, and then $c \equiv 320 - 461 \times 7 = 320 - 3227 = -2907 \equiv 93 \pmod{1000}$.

Confirming on the output the solve did not use: $461 \times 320 + 93 = 147613$, and $147613 \bmod 1000 = 613$, which is $x_2$. The rule is $x_{n+1} = 461x_n + 93 \bmod 1000$, recovered from two differences and a division.

That took a dozen lines of arithmetic and no insight whatever. Anything a person can do in a dozen lines, an adversary does instantly, and there is no version of this generator with a cleverer multiplier that resists it, because the solve never looks at the multiplier’s value.

Truncation does not help #

The obvious repair is to hide part of each output: publish only the high bits, on the grounds that the low ones carry the recoverable structure.

It helps a little and not enough. Given enough truncated outputs the full state is still recoverable, by lattice methods: the unknown low bits are small, the relations among the outputs are linear, and finding small solutions to a system of linear congruences is exactly the shortest-vector problem the previous rung measures — this time used as an attack rather than as a quality measure.

The arithmetic of how much it buys is worth having. Publishing only the top $t$ bits of a $b$-bit state leaves $b - t$ unknown bits per output, and each further output supplies one linear relation. So the unknowns and the relations both grow linearly and the lattice attack succeeds once enough relations accumulate — in practice a few dozen outputs for realistic sizes. Truncation converts an attack that needs three outputs into one that needs thirty, which is not a defence against anybody.

That is a satisfying reversal. The same lattice that says how evenly the generator spreads its points also says how few outputs are needed to break it, and a generator with a good spectral score is not thereby harder to predict.

The two failure modes are independent. A generator can spread points beautifully and be solvable in four outputs, which is the case here; or it can be hard to predict and spread points badly. Measuring one says nothing about the other.

The next-bit test #

The right definition of “random enough for an adversary” turns out to be a single condition, and it is a strong one.

A generator passes the next-bit test if no efficient procedure, given the first $k$ output bits, predicts the $(k+1)$-th with probability meaningfully better than a half.

Two things make the definition the right one.

It is equivalent to indistinguishability. Yao’s theorem says a generator passes the next-bit test exactly when no efficient procedure can distinguish its output from genuinely random bits at all — by any test whatsoever. So a single, checkable-sounding condition is equivalent to passing every test that could ever be devised, which is why the definition is worth its awkwardness: a battery of tests can always be extended and this cannot be.

And it is falsifiable in one direction. Exhibiting a predictor refutes a generator, which is what the figure does. Establishing that no predictor exists is a statement about all efficient procedures and has never been proved unconditionally for any generator.

That distinction is worth insisting on. Most claims about generators are statistical — a test statistic falls inside a confidence band, a chi-squared value is unremarkable — and are therefore about a sample. The claim here is arithmetic: given three outputs, these two congruences determine the parameters, and the parameters determine everything. No amount of sampling could weaken it and no amount could strengthen it.

What a strong generator rests on #

Since no generator is unconditionally strong, the strong ones are built on problems believed hard.

Blum–Blum–Shub iterates $x \mapsto x^2 \bmod pq$ and outputs one bit of each state — the parity. Predicting that bit is provably as hard as deciding quadratic residuosity modulo $pq$, which is as hard as factoring. So it is strong if factoring is hard — a conditional statement, and the strongest kind available. The squaring is what defeats the fitting argument: the relation between consecutive states is quadratic, so the outputs impose quadratic rather than linear equations, and solving those is exactly the problem believed hard.

The practical generators — the ones in use — are built from block ciphers or hash functions run in a counter mode, and their security rests on the belief that those primitives behave like random functions. That belief is supported by decades of failed attacks and is not a theorem either.

And the gap between the two families is a factor of a thousand in speed. A provably-conditional generator does modular exponentiation per bit; a practical one does a few hundred instructions per hundred bits. Almost everybody chooses speed, and the choice is deliberate rather than ignorant: a generator that produces a hundred megabytes a second is usable for encrypting a network link and one that produces a kilobyte is not.

Putting that figure here rather than leaving it on the previous rung is the point of the pair. A perfect spectral score and total predictability are compatible, and the reason is that the spectral test asks about the set of points the generator produces while the solve asks about the order in which it produces them. A set can be beautifully distributed and enumerated in a completely predictable sequence.

The general shape of the failure #

Both the lattice defect and the predictability come from the same source, and naming it is the useful part.

A linear rule is a rule with a small description that outputs can be fitted to. Fitting is what a solver does: the outputs impose linear equations on the parameters, and linear equations are solved. A generator resists prediction only if its rule cannot be fitted from its outputs, which requires the rule to be non-linear in a way that makes the fitting problem hard.

That is why every strong generator is built around an operation believed hard to invert — squaring modulo a composite, a block cipher’s round function — and why no amount of care with a linear rule produces one. Linearity is the defect, and every other property is a symptom.

Where this has actually mattered #

The vulnerability is not theoretical and the cases are instructive because in each one the generator was chosen by somebody who knew it was a generator and did not ask the second question.

Online card rooms, 1999. A poker site shuffled its decks with a linear congruential generator seeded from the clock, with a state of thirty-two bits. Two researchers showed that observing five cards of a hand determined the seed, hence the whole deck, in real time. The defect is a combination of the solve above and a seed space small enough to search.

Session identifiers. A great many early web frameworks issued session tokens from a language’s built-in generator, which was and often still is linear. Observing a few tokens gives the state and hence every other user’s token — an attack that requires no cryptography at all.

And simulation, in the other direction. Where predictability does not matter, linear generators remain in use and are perfectly appropriate. The difficulty is never that they are bad; it is that the same function is exposed under one name and used for both purposes.

The pattern in all three is a default. A language ships one generator, it is the fast one, and the interface gives no hint that there are two questions. Modern languages separate them into two libraries with different names, one documented as unsuitable for anything adversarial, and the separation is a response to exactly these failures.

What the pictures cannot show #

A solve is arithmetic and the figure shows its input and output. The extended Euclidean algorithm that inverts the difference, and the search the figure actually performs, are steps rather than pictures; what is drawn is a row of numbers and a claim about them.

The predictor is checked on one generator. The claim is about every linear congruential generator, and the argument for that is the three lines of algebra rather than the four hundred trials.

The bar chart compares two things that are not commensurable. One bar is a measured success rate over four hundred trials; the other is a computed chance rate for a hypothetical guesser. Putting them side by side is the right rhetorical move and it is not a controlled comparison, since the second was never run.

And absence of a predictor cannot be drawn at all. Every figure here exhibits a successful attack. The property a strong generator has is that no attack exists, which is a statement about all procedures and has no picture and, for the generators in use, no proof.

Where the ladder goes next #

The next rung asks what a generator would have to be like to pass the test this one fails: randomness that is hard rather than merely uniform.

Named here as a debt: Berlekamp–Massey, the algorithm that recovers a linear recurrence of any order from twice as many terms as its order, which is the general form of this rung’s solve and is drawn nowhere.

Also unwritten: the seed, which is where a generator’s unpredictability has to come from in the first place. Every construction above assumes the initial state is unknown; a strong generator seeded from a clock has as many possible states as the clock has readings, and several of the failures listed above are failures of seeding rather than of the generator.

Sideways, the inverse modulo $m$ that the solve needs is the extended Euclidean algorithm’s output, the lattice used to attack truncated outputs is the previous rung’s quality measure, and the arithmetic throughout is modular.

What “efficient” is doing in the definition #

The next-bit test is stated with the word efficient in it, and the word is not decoration — without it the definition would be vacuous.

Any generator with a finite state is predictable by an inefficient procedure: try every state, keep the ones consistent with the output seen so far, and predict by majority. For a state of $n$ bits that takes $2^n$ work and always succeeds. So “no procedure predicts the next bit” is false for every generator that exists, and the definition has to bound the resources.

That is why the whole subject is conditional. A statement of the form “no efficient procedure does X” is a statement about complexity classes, and separating complexity classes is the central open problem of the subject. If the two main classes coincided, no generator would be strong and the definition would be empty.

So the honest statement is: strong generators exist if certain problems are hard, and every construction in use is a bet on a specific problem. The bets have different characters — factoring for the provable constructions, “nobody has broken this cipher” for the practical ones — and the second is a weaker kind of evidence held with more confidence, for reasons that are sociological as much as mathematical.

None of that applies to a linear generator, which is broken outright by a procedure taking a dozen lines of arithmetic. There is no conditionality to discuss and no hardness assumption to examine: the rule is recovered, and that is the end of it.

What is worth carrying away #

Two entirely different questions can be asked of the same object, and passing one says nothing about the other.

A generator’s points can be spread as evenly as the modulus allows, pass every statistical battery, and be solvable in four outputs by arithmetic anybody could do. The evenness and the unpredictability are unrelated properties, and a generator is chosen for one or the other depending on whether anybody adversarial will see its output.

The habit worth taking is to ask who is allowed to look. A simulation’s generator is used by a program that does not care what produced its numbers; a protocol’s generator is used against an opponent who does. The same object is adequate for one and useless for the other, and no single measure covers both.