A rotation that hides the lattice

The congruential generator was the first subject of this sequence and its weaknesses were the next three. Its outputs lie on planes; how far apart the planes are ranks one generator against another; and four outputs reveal its rule. Then the sequence moved to the generator most simulations use, a linear recurrence with nineteen thousand bits of state, and a last filter that improves how its outputs spread without changing anything else. That filter was linear and reversible, and the essay ended with its limitation: a linear filter cannot remove linearity.

This essay goes back to the oldest and weakest of the generators and asks what a filter that is not linear can do to it. The answer, in the design Melissa O’Neill published in 2014 as the permuted congruential generator, is: nearly everything a statistical test can see, and nothing a determined attacker cannot undo.

Clocks in the low bits #

The generator in the figure is as simple as a congruential generator can be. Its state is a 16-bit number $s$, updated by $s \mapsto 31829\,s + 12345 \pmod{2^{16}}$. The multiplier leaves remainder 1 on division by 4 and the increment is odd, which is the condition for the full period: the state visits all 65,536 values before repeating, which the figures check by running it round once.

A full period does not make every bit of the state random, and the top panel shows the problem. The lowest bit alternates, 1, 0, 1, 0, for ever. The next repeats every 4 steps, the next every 8, and in general bit $k$ repeats every $2^{k+1}$ steps. The reason is that reduction modulo $2^{16}$ never lets a high bit affect a low one: the lowest $k+1$ bits of the next state depend only on the lowest $k+1$ bits of this one, so they form a congruential generator of their own, modulo $2^{k+1}$, with period at most $2^{k+1}$. The low bits of the state are not random numbers; they are clocks.

The bottom panel shows the eight bits the permuted generator outputs from the very same states. They have no visible pattern, and the figure confirms what the eye suggests: every one of them runs the full period of 65,536 steps before repeating. Something has moved the long periods of the high bits into every bit that is shown.

The lowest bit shows the mechanism in one line. The multiplier 31829 and the increment 12345 are both odd, so if $s$ is even, $31829\,s + 12345$ is odd, and if $s$ is odd it is even: the parity flips at every step, whatever the rest of the state is doing. For the next bit, the same argument applied modulo 4 shows that the last two bits run through all four combinations and then repeat, and so on upwards. Nothing random happens in the low bits at all; all the mixing happens in the carries that run upwards from them, which is why only the high bits are worth anything.

The standard advice for congruential generators, which Donald Knuth gave in 1969, is therefore to use only the high bits. Java’s built-in generator follows it: its state is 48 bits and each 32-bit output is the top 32 of them, discarding the 16 bits whose periods are shortest. Discarding helps with the clocks but not with the planes, because the high bits are still a linear function of the previous state’s high bits, up to a small correction from the carries. The permutation is a way of using the low and middle bits as well, without letting their short periods through.

The periods put numbers to it. The low byte’s bits repeat every 2, 4, 8, up to 256 steps. The high byte’s bits are state bits 8 to 15, so even its lowest bit repeats every 512 steps, its highest every 65,536. The permuted output’s bits all repeat every 65,536. That is the first and simplest thing the permutation buys: no bit of the output is a short clock, even though most bits of the state are.

A rotation chosen by the state #

The output function takes three steps, and the figure works through them for one state. First, the state is combined by exclusive or with a copy of itself shifted five places to the right, which folds information from the high bits down into the middle. Second, eight bits are taken from the middle of the result, discarding the lowest five, which are the shortest clocks. Third, those eight bits are rotated to the right — bits falling off the right end reappear at the left — by an amount between 0 and 7, read from the state’s top three bits.

The first two steps are linear: an exclusive or with a shift and a selection of bits are exactly the kind of operation the tempering filter uses, and they could be written as a matrix over the field of two elements. The third is not. A rotation by a fixed amount would be linear too, but this rotation’s amount depends on the state, so the map from state to output mixes a choice made by some bits with the values of others. That is the step no matrix can express, and it is the one that removes the lattice.

The top three bits are the best possible choice for the rotation, because they are the state’s least predictable bits: they have the longest periods, and they depend on every lower bit through the carries of the multiplication. The output’s lowest bit is therefore taken from a position the top bits choose afresh at every step, and its period becomes the full period of the top bits.

Why these three steps #

Each step of the output function answers a specific weakness, and O’Neill’s paper describes a family of alternatives built from the same parts. The shift-and-fold brings high bits down into the bits that will be shown, so the output depends on the long-period bits as well as on the middle ones. Discarding the lowest bits removes the shortest clocks entirely, since no folding can make a bit of period 2 into one of period 65,536. And the rotation, chosen by the top bits, is the cheapest operation that makes the output’s bit positions depend on the state: on most processors it is a single instruction.

The proportions matter more than the details. The generator shows half as many bits as it keeps — eight of sixteen here, 32 of 64 in the standard small version, 64 of 128 in the large one — so every output leaves half the state hidden, and the hidden half includes the bits that choose the rotation. Showing more of the state would make it easier to see the lattice; showing less would waste the state. Other members of the family replace the rotation by a shift whose amount the state chooses, or add a multiplication to the output, trading a little speed for more mixing; all of them keep the same cheap state update and put the non-linearity in the output.

Pairs that fill the square #

The planes of the first essay reappear here in their simplest form. Plot each output against the next, for all 65,536 steps of the cycle. The low byte of the state is a congruential generator modulo 256 in its own right, so it repeats every 256 steps and its pairs are only 256 points, lying on a few parallel lines; 99.6% of the grid’s cells are never visited. The high byte has the full period, but consecutive values are tied by the multiplier, and its pairs fall on a lattice of stripes that leaves 52.7% of the grid empty.

A truly random sequence of 65,536 bytes would visit cells at random, and the chance that a given cell is missed by every one of 65,536 throws into 65,536 cells is $(1 - 1/65536)^{65536}$, almost exactly $e^{-1} = 36.8\%$. The permuted output leaves 36.4% empty. To this test, it is indistinguishable from random.

Each output value also appears exactly 256 times over the cycle, which the figures check by counting: one output at a time, the permuted generator is perfectly equidistributed, as its state is.

Triples, against a random spread #

The planes are a three-dimensional phenomenon, and the stronger test sorts triples. Taking the top four bits of three consecutive outputs gives a box in a 16 × 16 × 16 grid, and over the full cycle each box should receive about 16 triples, with the number varying from box to box as a Poisson count does. The permuted output does exactly that: its histogram sits on the dashed Poisson curve, and the chi-squared statistic, which measures the total squared deviation from 16, is 3,973 on 4,095 degrees of freedom — as close to its expected value as a random sequence’s would be. The high byte of the state fails badly. Its triples lie on planes, so 272 boxes are never hit and others receive more than 30, and its chi-squared statistic is 25,548.

The comparison is fair in a precise sense: the two panels are computed from the same 65,536 states in the same order. The high byte is simply eight bits of the state, shown unchanged; the permuted output is eight bits computed from the state by a short function. The tests that detect the lattice are blind to it once the function has been applied, even though the lattice is still there in the state.

Four outputs still give it away #

What the permutation does not do is make the generator unpredictable, and the last figure shows it by brute force. Before any output is seen, the state could be any of 65,536 values. After one eight-bit output, only 256 states are consistent with it, for either generator. After the second, the generator that shows its high byte has 3 candidates left and the permuted generator has 1. After four outputs both are pinned down exactly, and every future output is known. The plain generator is the slower to pin down, oddly, because its outputs say less: one high byte nearly determines the next, so its second output repeats much of what the first already said, while the permuted generator’s second output depends on bits the first one hid.

At sixteen bits this is a search over 65,536 possibilities, which takes a fraction of a second. A full-size permuted generator has a 128-bit state and shows 64 bits per output, so a naive search would have to try the $2^{64}$ possible values of the hidden half, which is out of reach. But the structure that makes the generator fast also makes it attackable: the state still evolves linearly, the rotation has only a few possible amounts, and in 2020 Charles Bouillaguet, Florette Martinez and Julia Sauvage recovered the full state of the 64-bit-output version from its outputs by combining a guess of the rotations with the lattice methods that recover a congruential generator’s rule from a few outputs. The computation was large but feasible.

This is the boundary randomness that has to be earned drew. A statistical generator is judged by whether its output looks random to tests that do not know how it was made. A cryptographic generator is judged by whether its output can be predicted by anyone who does. The permuted generator is an excellent statistical generator built from a very poor one, and it is not a cryptographic generator at all.

Why the cheap fix works #

The permuted generator is fast because its state update is a single multiplication and addition, the cheapest possible, and its output function is a few shifts, an exclusive or and a rotation. The design’s insight is that the expensive part of a good generator does not have to be in the state. The state only has to have a long period and some bits of high quality; a cheap non-linear output function can then spread those bits across everything that is shown.

The Mersenne twister’s tempering applied the same idea linearly and was limited by it: the output of a linear filter applied to a linear recurrence is still a linear recurrence, with the same failures on tests that look for linearity. The rotation breaks that, and it is why the permuted generator passes test batteries, such as the large suites assembled to stress generators with hundreds of statistical tests, that the twister fails on its linearity tests. It is also why NumPy, the standard numerical library in Python, adopted a permuted generator as its default in 2019.

The period is still the state’s #

A permutation of the output cannot do two things, and both are visible in the model. It cannot lengthen the period: the output is a function of the state, so when the state repeats after 65,536 steps the output does too, and no output function can make a generator with $2^{16}$ states run longer than $2^{16}$ steps. The full-size generators get their long periods, $2^{64}$ or $2^{128}$, from their state sizes, not from their output functions.

And it cannot make different starting points independent. Two runs of one generator from different seeds are two stretches of the same cycle, and if a simulation draws enough numbers the stretches can overlap. The permuted design offers a remedy that comes from the congruential state rather than from the permutation: the increment can be any odd number, and each choice gives a different cycle through all the states. With a 64-bit state there are $2^{63}$ such streams, which lets parallel computations each take their own stream rather than hoping their stretches of one cycle never meet. That is a property congruential generators always had and seldom used. Whether it is safe is disputed. Two streams with different increments are not unrelated: the state of one is a simple affine function of the state of the other, shifted along the cycle, and critics of the design, Sebastiano Vigna prominently, have exhibited pairs of streams whose permuted outputs are visibly correlated when the increments are chosen carelessly. The permutation hides the relation from tests applied to one stream; it does not remove the relation between two.

What the figures establish #

The figures run the sixteen-bit generator through its full cycle of 65,536 states and compute every quantity exactly: the period of each output bit, the occupied cells for pairs, the box counts for triples, and the number of states consistent with each prefix of outputs. The sixteen-bit generator is a model of the design, with the same three steps at a smaller size; it is not the generator anyone uses. The statements about the full-size generator — its state size, its adoption, the 2020 state recovery — are from the published record.

Still open: what a non-linear output proves #

For permuted generators, as for almost every fast non-linear generator, there are no proofs of the statistical properties they display. A linear generator’s period, its equidistribution in each dimension and its lattice structure are theorems, computed from the recurrence. Once a non-linear output function is applied, the period of each output bit can still be proved, as here, but how evenly pairs, triples and longer tuples of outputs spread is known only by measurement. The tests the permuted generator passes are evidence, and the theory that would turn them into guarantees does not exist.

The cryptographic side has its own open question. The 2020 attack recovered the state of one standard variant, and its cost depended on the output function’s details. How much a cheap non-linear output function can raise the cost of recovering a linear state — whether there is a design as fast as this one that resists every efficient attack — is not known, and the general belief is that speed and provable unpredictability pull in opposite directions. That belief is itself unproved: it is a special case of the question whether one-way functions can be very cheap to compute, which is open.