I’ve written a pair posts recently about reverse engineering the inner state of a random quantity generator, first Mersenne Tornado then lehmer64. This submit will take a look at xorshift128, carried out under.
import random
# Seed the generator state
a: int = random.getrandbits(32)
b: int = random.getrandbits(32)
c: int = random.getrandbits(32)
d: int = random.getrandbits(32)
MASK = 0xFFFFFFFF
def xorshift128() -> int:
international a, b, c, d
t = d
s = a
t ^= (t << 11) & MASK t ^= (t >> 8) & MASK
s ^= (s >> 19) & MASK
a, b, c, d = (t ^ s) & MASK, a, b, c
return a
Recovering state
Recovering the inner state of the generator is easy: it’s the 4 newest outputs in reverse order. That is illustrated by the next chart.
Because of this as soon as we’ve seen 4 outputs, we will predict the remainder of the outputs. The next code demonstrates this.
Let’s generate 5 random values.
out = [xorshift128() for _ in range(5)]
Operating
print(hex(out[4]))
exhibits the output 0xc3f4795d.
If we reset the state of the generator utilizing the primary 4 outputs
d, c, b, a, _ = out print(hex(xorshift128()))
we get the identical end result.
Good stats, unhealthy safety
Mersenne Tornado and lehmer64 have good statistical properties, regardless of being predictable. The xorshift128 generator is even simpler to foretell, nevertheless it additionally has good statistical properties. These mills can be fantastic for a lot of functions, corresponding to Monte Carlo simulation, however disastrous to be used in cryptography.
The submit on lehmer64 talked about on the finish that the inner state of PCG64 can be recovered from its output. Nevertheless, doing so requires way more refined math and 1000’s of hours of compute time. Nonetheless, it’s not satisfactory for cryptography. For that you just’d want a random quantity generator designed to be safe, corresponding to ChaCha.
So why not simply use a cryptographically safe random quantity generator (CSPRNG) for every thing? You can, however the different mills talked about on this submit use much less reminiscence and are a lot sooner. PCG64 occupies an attention-grabbing center floor: easy and quick, however not simply reversible.
