Instrument 05prng-lattice-lab
Forty-eight bits, however you spend them.
java.util.Random keeps a 48-bit seed. This is a closed harness that
measures how much of it has to leak before the rest can be rebuilt, and the answer turns out not
to care how the bits arrive.
Writeup
It attacks a generator it instantiates itself.
java.util.Random is a 48-bit truncated linear congruential generator. The lab is anchored on Randar, the Minecraft attack that recovers a server’s seed from three rounded floats, and it revalidates against that published vector on every run.
There is no network target and no third-party system anywhere in it. The point is diligence: a predictable token is a real finding in code under review, and a finding is worth more when it arrives with a working demonstration than with a citation.
The boundary is a straight line at forty-eight bits.
The generalisation is a phase diagram over two axes: k, the bits leaked per call, and n, the number of observations. Recovery is essentially free wherever n·k clears 48 with a small margin. Round-off resolves it on its own, with no enumeration at all.
Below the line the system is under-determined and no amount of work closes it. What governs the boundary is the product rather than its shape: eight bits from six calls and three bits from sixteen sit on the same diagonal and behave the same way.
At the edge the answer stops being a value.
Right on n·k ≈ 48, recovery is no longer unique. A trial there typically leaves 1.8 to 2.2 states consistent with everything observed, so the honest output is a small set and not a seed. That was found rather than predicted, which is the part worth keeping.
Noise sharpens the same point. One unit of measurement noise at the edge takes the candidate count from about 1.5 to about 27, while a cell at n·k = 96 is still uniquely recoverable at noise 12. Margin is what buys tolerance.
The last two leaks now have complete solvers.
nextInt(odd bound) is the RandomStringUtils idiom. The state splits into its low 17 bits, which run their own LCG mod 217 and are enumerated as 217 vectorised slices, and a 31-bit top half that is a truncated-LCG box problem per slice. A certified round-off radius bounds every point in the box, so the candidate set is complete: an edge collision surfaces as more than one candidate rather than as a confident wrong answer.
The bit length of nextInt(2^k) is the Minerva analogue. It keeps only observations worth two bits or more, because a lattice dimension costs about 21.05 in enumeration and a one-bit observation cannot pay for itself. The rest is an irregular-gap lattice, enumerated completely and replay-filtered against every observation.
Leak shape moves the price, not the edge.
Odd-bound cells at 48 realized bits recover uniquely in 67 to 88 trials out of 200, carrying the same 1.8 to 2.2 consistent states the top-bits model shows. Bit length reaches the same edge at roughly twice the observations. At the starved extreme of two bits per call it is infeasible until 48 observations, then 98% at 48 and 99.5% at 64.
So the shape of a leak changes what it costs to reach the boundary. It does not move the boundary.
It folds into the auditor.
The lab ships a weak_rng_adapter that reuses the validated cracker, and the detector it justifies is merged into repoauditor, a private sibling, as OPT-036, where weak_rng runs against real code under review. The lab is the evidence behind a check rather than a standalone demonstration.
RegisterPublic surface
prng-lattice-lab
- Repository
- github.com/erxxc/prng-lattice-lab
- Version
- v0.2.0
- Target
java.util.Random, 48-bit truncated LCG- Anchor
- Randar published vector, revalidated on every run
- Leak models
- Top bits ·
nextInt(odd)residue ·nextInt(2^k)bit length - Solver
- fpylll box enumeration, complete
- Folds into
- repoauditor, OPT-036
weak_rng - Nature
- Closed offline harness · no network target · no third-party system