The Case of the Mystery Seeds · Chapter 5
Fake randomness
Ask a 1990s programmer for 20 random bytes and they'd reach for one of a few standard tools built into their computer's software. Those tools aren't random at all. They're tiny machines that follow a rule, and if you understand the machine, you can run it forward, run it backward, and find out exactly when it was switched on.
Nib says: This is the chapter where the case turns. The last toy lets you start a real 1990s generator from any moment in time, then rewind it to recover that moment. Hold on to that idea; it's the whole trick.
Computers can't flip coins
A computer is built to do exactly the same thing every time. That's wonderful for spreadsheets and terrible for dice. So for most purposes, programs fake randomness with a pseudorandom number generator, or PRNG.
A PRNG keeps a secret number called its state. Each time you ask for a random number, it churns the state with a fixed rule and hands you part of the result. Where the state starts is the seed. Same seed, same numbers, forever. Games seed it with the clock so each round feels different; scientists fix the seed so their simulations can be repeated exactly.
You may know the Mersenne Twister, invented in 1997 by Makoto Matsumoto and Takuji Nishimura and still the default in Python's random module. It's an excellent fake: its sequence takes 219937 − 1 steps to repeat. But even it is a machine. Watch 624 of its outputs in a row and you can rebuild its entire state and predict everything that follows. Fine for games and simulations; never for secrets.
Our generator is far older and simpler than the Twister. To understand it, start with a tiny one.
The simplest machine
A linear congruential generator, or LCG, has a one-line rule. To get the next state: multiply by a, add c, and wrap around a clock of size m.
next = (a × state + c) mod m
It's the clock arithmetic from Chapter 1 with an extra "add". Here's one on a clock of just 32. Change the numbers and see what happens.
A tiny generator
The gold dot is the seed. Each hop is one turn of the machine. Green dots are states it has visited.
Try a = 5 and c = 3: the machine visits all 32 states before repeating, in a jumbled order. Try c = 0 or an even a, and it gets stuck in a short loop. There's a neat rule (the Hull–Dobell theorem) for which choices visit every state; real LCGs are designed to follow it.
LCGs are fast and tiny, which made them everywhere in early software. The Rnd function in Excel's VBA, for example, is a small LCG. Their weakness is the same as their charm: there is nothing hidden in the rule. And every step can be undone, because on a clock like this, multiplying by an odd a has an exact reverse.
Meet drand48
Unix C libraries have shipped a family of LCG functions for decades: drand48 and its siblings. They all share one machine:
• a 48-bit state, so the clock has 248 (about 281 trillion) positions;
• a = 25214903917 (in hex, 5DEECE66D) and c = 11;
• srand48(seed) starts it: the seed becomes the top 32 bits of the state, and the bottom 16 bits are always set to the fixed value 330E (hex);
• lrand48() turns the machine once and returns the top 31 bits of the state as a whole number.
The usual way to seed it is with the current time as a Unix timestamp, the count of seconds since 1970. One line of C, srand48(time(NULL)), and every run of your program gets different "random" numbers. Unless you know when it ran.
Start the real machine
Pick a moment (in UTC). We seed with that timestamp, then turn the machine. Each output's top byte (8 bits) is highlighted, because we'll need it later.
The 48-bit state after the latest turn. The gold outline marks the 31 bits lrand48 returns; solid gold marks the top byte.
| Turn | lrand48() | Top byte |
|---|
Seed it again with the same moment and you'll get exactly the same numbers. A whole sequence of "random" output is completely fixed by one number: the second at which the program started.
Running it backward
Here's the move that cracks the case. If you know the full 48-bit state at any point, you can undo the rule one step at a time: subtract 11, then multiply by the reverse of a. Keep going and you'll eventually reach a state whose bottom 16 bits are 330E, the fingerprint srand48 leaves. That's probably where the machine was switched on, and its top 32 bits are the seed. If the seed is a timestamp, you've just learned when the program ran.
Rewind the machine
Nib started the generator at a secret moment and turned it a secret number of times. You get only the final state. Rewind until you see the srand48 fingerprint (330E in the bottom 16 bits).
One honest caveat. The bottom 16 bits of the state run on their own little clock: they never depend on the higher bits, and they visit all 65,536 possible values before repeating. So 330E comes round exactly once every 65,536 turns, and each time the top 32 bits decode to a different "seed". Rewind far enough and you'll meet decoys. Telling the real start from a decoy takes more than the fingerprint; Chapter 8 shows how. Hold that thought.
There's a bigger snag, too. In the toy, Nib handed you the whole state. Real output doesn't do that. lrand48 shows only 31 of the 48 bits, and a program that keeps just the top byte of each output shows only 8. The hidden bits have to be worked out first. How that happens is the next two chapters.
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
- 1
Pseudorandom numbers come from a machine and a seed. Same seed, same numbers, every time.
- 2
An LCG can be run backward. Each step is "multiply and add on a clock", and both can be undone exactly.
- 3
Clock-seeded generators remember when they were started. Rewind lrand48 to its srand48 fingerprint and the seed tells you the second it began.
Check yourself
A program seeds its generator with the current time in seconds. You know it ran some time on one particular day. How many seeds would you need to try?
At most 86,400, the number of seconds in a day. That's nothing for a computer, which is exactly why clock seeds are hopeless for secrets.
Why can you run an LCG backward, but not a hash function?
An LCG's rule is a simple multiply-and-add on a clock, and with an odd multiplier both steps have exact reverses. A hash function is deliberately built so that no practical reverse exists.
What does the value 330E in the bottom 16 bits tell you?
That this state looks like one srand48 just set up, so it may be where the generator started. It's only a hint: the bottom 16 bits cycle through every value, so 330E comes round exactly once every 65,536 turns, each time with a different decoy seed. You need other evidence to pick the real one.