The adversary who knows the seed

Every figure in this phase is reproducible. The skip list at seed 20260810 has the same eleven levels on every machine that renders this page; the hash table’s multiplier is 332,584,831 on every build; the two hundred treaps come from seeds 90001, 97920, 105839 and so on. That is not incidental — a caption may only quote a number the reader can reproduce, and a figure drawn from Math.random() would show different numbers on every build and could not be written about.

It is also the precise condition under which every guarantee this phase has demonstrated stops holding.

The gap, stated once #

A randomised algorithm’s guarantee is over its own coin flips. The reasoning goes: the input cannot influence the coins, therefore the input cannot select which case arises, therefore the expected bound holds on every input.

The middle step is the one that fails. It should read: the input cannot influence the coins, and whoever chooses the input does not know them. When both hold, the guarantee holds. When the second fails — when the coins are known in advance — an adversary can compute the input that produces the worst case exactly as easily as they could against a deterministic algorithm, because at that point there is a deterministic algorithm.

Randomisation does not create unpredictability. It relocates the thing that must be unpredictable, from the input to the seed. If the seed is published, nothing has been gained.

How completely it fails #

“Weakened” would be the comfortable word. The measurements say something stronger: with the seed known, the randomised structure is not degraded relative to the deterministic one, it is identical to it.

The first and second rows are the same number, and it is the maximum possible number. There is no partial protection.

The reason is that the adversary’s work is a closed form rather than a search. Given the multiplier $a$, the modular inverse $a^{-1}$ takes five multiplications by Newton’s iteration, and then the colliding keys are $a^{-1}, 2a^{-1}, 3a^{-1}, \ldots$ modulo $2^{32}$. Two thousand and forty-eight keys that all hash to bucket zero cost about ten microseconds to generate. It is not an attack that requires resources; it is arithmetic.

The same holds for the other structures in this phase. Knowing a skip list’s seed gives the height of every node before it is inserted, so the keys that produce a degenerate list are computable. Knowing a treap’s seed gives every priority, so the insertion order that produces a spine is computable. In each case the “randomised” structure with a known seed is a deterministic structure whose worst case is written down in the documentation.

One qualification belongs here and it cuts the other way. Not every randomised algorithm is equally exposed, and the difference is how much the adversary has to know to compute the bad input. Against multiply-shift the answer is one 32-bit word. Against a skip list it is the whole future coin stream, which is more but is still a single seed. Against randomised quicksort it is the pivot at every level of a recursion whose shape depends on the input — so constructing the worst case means solving for an input that makes the algorithm’s own choices bad, which is a fixed-point problem rather than an inversion. That is harder, and it is not a defence: an adversary with the seed can simply simulate the algorithm and search, and the search is cheap because they get to run it as many times as they like.

Where this actually happened #

This is not a hypothetical, and the case history is worth knowing because the failure was not in any algorithm.

Around 2011 a family of denial-of-service attacks landed on essentially every web framework at once. The mechanism: HTTP request parameters are put in a hash table keyed by parameter name; the hash function was a fixed, published one — a variant of the same multiply-and-add most languages shipped; so an attacker could compute a few thousand parameter names that all collide, send them in one POST, and turn an $O(n)$ parse into an $O(n^2)$ one. A request of a few hundred kilobytes consumed seconds of CPU. A handful of such requests took a server down.

Nothing about that is a hashing failure in the sense of a bad function. The hash spread ordinary keys perfectly well. The failure is exactly the one this essay is about: the choice of function was fixed and public, so the randomisation that would have protected the table had been optimised away in favour of a constant, and the constant was in the source of an open-source runtime.

The fix deployed was to randomise the hash per process at start-up from an operating-system entropy source, which is precisely “choose the member at run time”. Several runtimes went further and adopted SipHash, a keyed hash with cryptographic collision resistance, because per-process randomisation is defeated by an adversary who can observe which keys collide and work backwards — and timing a web request reveals it.

Why the seed is worse than it looks #

Two properties of the situation make it more fragile than “keep the seed secret” suggests, and both are worth knowing before relying on level two.

The seed space is often small. A seed taken from the clock at second resolution has about twenty-five bits of entropy over a year, and one taken from a process ID has fifteen. An adversary who can force restarts, or who can simply try, is searching a space of thousands rather than billions. The randomisation is real and the amount of it is a number, and the number is frequently far below what the phrase implies.

Outcomes leak the seed. This is the property that defeats level two even when the seed space is large. Every collision an adversary can detect is a constraint on the multiplier; enough constraints determine it. Detection does not require access to the table — a slower response is enough, and a timing difference of microseconds is measurable over enough requests. So an adversary who can send requests and time them can, in principle, recover a per-process hash seed and then compute a colliding set against it. That is the argument for level three, and it is the reason several language runtimes went past per-process randomisation to a keyed cryptographic hash rather than stopping at the cheap fix.

The general shape of both points is that randomisation is a security property and inherits security’s rules, including that the entropy has to be counted and that side channels exist. An algorithms textbook analysing an expected-case bound is not doing security analysis, and the bound it proves is correct and is not a threat model.

The three levels of “randomised” #

The case history suggests a distinction the word “randomised” does not make on its own, and it is the useful takeaway of this essay.

Level one: randomised at development time. The constant in the source was chosen by rolling a die. This is not randomisation in any sense that matters; it is a constant. It defends against nothing.

Level two: randomised at run time from a non-secret source. A seed from the clock, the process ID, or a counter. This defends against an adversary who chose the input in advance and did not know which process they would hit. It does not defend against one who can observe outcomes, because the seed’s entropy is small enough to search, and it does not defend against one who can read the seed.

Level three: randomised at run time from a secret, unguessable source. A cryptographic key, held for the lifetime of the process, never exposed. This defends against an adversary who can choose inputs adaptively, and it costs a slower hash.

Almost all discussion of randomised algorithms is about level two, almost all code is at level one, and the threat models people have in mind usually require level three. Being explicit about which one is in use costs a sentence, and the sentence is nearly always missing.

Counting the bits level two actually needs #

“The seed space is often small” is the right diagnosis and it has an arithmetic that decides how small is too small — and the arithmetic then shows that the second failure, the leak, is a different problem that more bits do not fix.

Take the essay’s own cost for the attacker’s inner loop: about ten microseconds to compute two thousand colliding keys once the multiplier is known. An adversary who must guess the seed simply runs that loop once per candidate.

A process ID gives fifteen bits, so the whole space is 32,768 candidates and enumerating it costs $32{,}768 \times 10\,\mu\mathrm{s} = 0.33$ seconds. A clock at second resolution over a year gives twenty-five bits: 335 seconds, about six minutes, once, offline, after which every possible seed has a prepared attack sitting beside it. Neither of those is randomisation in any useful sense; both are a lookup table the adversary builds over lunch.

To put the search beyond a serious adversary — say $2^{60}$ operations — the seed needs sixty bits, and a sixty-four-bit word from the operating system’s entropy source supplies them at the cost of one call. So the practical rule is not “randomise at run time” but “randomise at run time from a full-width entropy source”, and the clock and the process ID miss it by thirty-five to forty-five bits. That is a large enough shortfall to be worth the sentence, because both are what a programmer reaches for when getrandom feels like overkill.

Now the second failure, and the point of doing the first arithmetic first. Against an adversary who can observe collisions, adding bits to the seed does almost nothing.

A multiply-shift hash into $2^b$ buckets reveals, with every collision the adversary can detect, a constraint on the top $b$ bits of $a(x-y)$. Each observation is therefore worth about $b$ bits of information about the multiplier, so recovering a 32-bit $a$ takes a handful of detected collisions rather than $2^{31}$ trials — and the number of observations grows linearly in the key’s width, not exponentially. A 64-bit multiplier costs the adversary twice as many probes as a 32-bit one, which is not a defence; it is a rounding error in the attack’s duration.

That is the precise sense in which level three is a different thing rather than more of level two. A keyed cryptographic hash does not have more entropy in its key than a well-seeded multiply-shift; what it has is the property that its outputs do not constrain its key, so observations buy the adversary nothing and the only route left is the exhaustive search the bit count already priced out of reach.

Two sentences worth carrying, then. Against a non-adaptive adversary, count the seed’s bits — and the count has to be sixty, not fifteen. Against an adaptive one, count nothing about the seed and ask whether the function leaks it, because a function that does is broken at every key width. A hash is a family, not a function is where the family is the object; this is the observation that a family whose member is recoverable from its behaviour is, to an adversary who can watch, a family of one. And counting the coin flips is the instrument that makes the first of the two an arithmetic rather than a feeling.

The site’s own position #

This site is at level one by design and it is worth saying so plainly rather than letting the figures imply otherwise.

Every seed here is a constant in a source file. 20260810 builds the skip lists, 8080 fills the Bloom filters, 1234 chooses the hash multiplier, 909 supplies the treap priorities. All of them are printed in the caption strips. Anyone who wants the input that destroys any structure on this site can compute it, and the essays have shown how.

That is the correct choice for the purpose, and the purpose is worth separating into its two halves.

What a seeded figure demonstrates is the distribution. Two hundred builds at two hundred seeds measure how a skip list’s cost varies over the coins, and that measurement is exactly as valid seeded as unseeded — the seeds are a sample from the space of coin sequences and nothing about them being written down changes what the sample shows. Every concentration result in this phase is real.

What a seeded figure cannot demonstrate is unpredictability. The claim “an adversary cannot construct a bad input” is a claim about what somebody does not know, and a figure whose seed is printed beneath it is not evidence for it. There is no version of this site’s figures that could be.

So the honest division is: the distributions are measured, the unpredictability is argued. Where this phase says “an adversary cannot do X”, that is a statement about level three and this site is demonstrating it at level one — and the demonstration takes the form of showing what happens when the level fails, which is what the figures above are.

The three levels are worth drawing rather than listed, and the same generator draws all three.

The second level is the one that is supposed to be the repair, and the reason it is hard to sell is that it looks exactly like the thing it repairs on every input anybody has.

And the third level is what happens when the input is chosen after the parameters are, which is the case the guarantee explicitly does not cover and the case a leaked seed produces.

What follows for anyone building something #

Four things, in the order they come up.

Decide the threat model before choosing the level. “Is there an adversary?” is a question with three answers — no, a careless one, a deliberate one — and each maps to a level. Most internal batch processing is genuinely at “no”, and level one is fine there; anything parsing input from outside the system is at “deliberate”, and level one is a vulnerability.

Randomise at start-up, not at compile time. This is nearly free and it is the step most often skipped. One getrandom() call per process, one word per structure.

Do not seed the algorithm from the same source as the data. This phase found the failure by accident: a treap whose priorities came from the same seeded stream as its keys produced height 3,849 at $n = 4{,}096$, against 26 for the same treap on genuinely independent priorities and 28 for an ordinary binary search tree. The priorities were the keys, rescaled. The structure was still correct, no test failed, and it had silently become the worst case. Seeding everything from one number is the natural thing to do in a test harness, and it is exactly what breaks the independence every analysis assumes.

Keep the reproducibility, separately. The reason people fix seeds is real: a bug that does not reproduce is much harder to fix. The answer is not to give up run-time randomisation but to log the seed and provide a way to force it — random by default, fixed on request. That gets reproducibility when it is wanted and unpredictability the rest of the time, and it costs one flag.

The cost of getting it right #

It is worth putting numbers on the three levels, because the reason level one persists is that the alternatives are assumed to be expensive and two of the three are not.

Level one to level two costs one syscall and one word. getrandom() at process start, a multiplier per table. There is no per-operation cost at all: the hash is the same two instructions whether its multiplier came from a constant or from the kernel. This is as close to free as a security improvement gets, and it is the step that fixed the 2011 attacks.

Level two to level three costs a slower hash. SipHash-1-3 runs at roughly a byte per cycle against multiply-shift’s effectively-free single multiply, so on short keys it is several times the cost. Whether that matters depends entirely on what fraction of the workload is hashing; for a hash table in a hot loop it is measurable, and for a request parser it is nothing next to the parsing.

And there is a fourth cost nobody counts, which is the reproducibility. That is the one this essay is really about, because it is the reason engineers reach back for the constant. A test that fails one time in fifty and cannot be reproduced is genuinely worse than a test that never fails, and fixing the seed makes the problem go away. The trap is that it makes it go away in production too.

The resolution is not clever and is worth stating because it is so often not done: make the seed an input. Default it to the entropy source, allow it to be overridden, and log the value used. Then a failing run reports the seed that produced it, replaying is a command-line flag, and the production default is still unpredictable. That is fifteen lines of code and it dissolves the tension entirely.

The sentence this phase keeps arriving at #

What randomising the pivot buys ended with a version of this and treated it as a caveat. Six essays later it is the load-bearing point, so it is worth its final form:

Randomisation converts a claim about the data into a claim about a secret. That is a good trade when the secret is kept, because data is chosen by other people and secrets are not. It is not a trade at all when the secret is printed in the source, in the documentation, or in the caption of a figure — and at that point the algorithm has all the costs of being randomised and none of the benefit.