Reversing Pseudo-Random Number Generators: Why PRNGs Are Predictable and Hackable

Most "random" numbers in computers are generated by deterministic formulas called pseudo-random number generators (PRNGs). Given the internal state, every future output is predetermined — and crucially, the formulas can be run backward to recover past states and predict future outputs. ## Linear Congruential Generators (LCG) Formula: `next = (state × multiplier + increment) mod modulus` To reverse: subtract the increment, then multiply by the **modular multiplicative inverse** of the multiplier. The inverse exists when the multiplier and modulus are coprime. Example: to undo `× 2 mod 5`, multiply by 3 (because `2 × 3 = 6 ≡ 1 mod 5`). Used in PHP's `lcg_value()` and many simple games. The Hull-Dobell Theorem provides rules for choosing constants that produce full-period sequences. ## XOR-Shift Generators Uses binary operations: shift bits left/right, then XOR with the original value. Typically chains 2-3 shift-XOR steps. Reversal exploits the self-inverting property of XOR (`a ⊕ b ⊕ b = a`). For a left-shift XOR by N bits: the top N bits are unchanged, XOR-shift those known bits to recover the next N, and repeat until all bits are recovered. | Generator | Used By | Reversible? | |-----------|---------|-------------| | Xorshift32 | Simple games | Yes, straightforward | | Xorshift128+ | JavaScript `Math.random()` | Yes, via Z3 solver or hand-coded inverse | | Xoroshiro128++ | Minecraft world generation | Active research, significantly harder | ## Flash Player's PRNG Multi-step process: linear feedback shift register for seed randomization, XOR-shift plus subtract-shift combinations, polynomial LCG-like step. Each step is individually reversible. Full reverse function developed by Dango (2017), optimized by George Teşeleanu (2019). Flash notably leaked RNG state across different games running in the same player, allowing one game's output to predict another's. ## Practical Demonstrations Minesweeper prediction: observe mine locations from a beginner puzzle, search billions of seeds for a match, predict the next expert puzzle's 99 mine locations — works perfectly. Slot machine jackpots: the earliest possible all-7s occurs after 5 pulls, requiring 15 coordinated random numbers. Four-leaf clovers: finding a seed that returns low numbers repeatedly, forcing all rare items to appear. ## Security Implications **Never use standard PRNGs for security-sensitive operations** — login codes, tokens, password resets, session identifiers. Use CSPRNGs (cryptographically secure PRNGs): `/dev/urandom` on Linux, `crypto.getRandomValues()` in browsers, `:crypto.strong_rand_bytes/1` in Erlang/Elixir. Don't leak RNG state between contexts. Assume client-side RNG is always manipulable.