Comment by saithound | Hacker News Reader

Comment by saithound | Hacker News Reader

Parent Full thread

Generally, PRNGs have an internal state, a transition function that determines a new internal state based on the current internal state, and an output function that determines the output value based on the current internal state.

In most cases, the output is determined by the output function based on a small part of the state (e.g. you may have 128 bits of state, feed the first 64 bits of it to an output function, and derive a 32-bit output as a result). This means that you don't learn much about the internal state of the generator merely by looking at an output value: you need to observe a lot of consecutive outputs to recover the internal state of the generator, and without knowing the internal state it's difficult (i.e. very hard to impossible) to use a relatively small number of known outputs to predict the next output.

The xorshift128 generator tested in the article has a nigh-trivial output function (because it's designed to be fast, not hard-to-predict) and a very simple transition function, which is why 4 outputs can be used to recover the internal state and to train a NN to predict the next output.

but ANNs are universal approximators, they dont care if a function is recursive or anything as long as it's deterministic

The point is precisely that predicting the next output based on a number of known outputs is not deterministic. Predicting the next _internal state_ from the current _internal state_ is deterministic, but that doesn't help, since you don't have access to the internal state.

Here's a simple random number generator. You start with a 16 bit number x, (your internal state). At each step you update your internal state to 75x + 74 (mod 65537), and output the first digit of your internal state (your random number)

Here's a sequence of outputs: 6,5,3,3,3,5. Does this information allow you to predict the next output? No.

For example, if the generator's starting state is x=60160, then the generator's internal state evolves as follows: [60160,55558,38093,38958,38296,54183,505]. So the seventh output will be 5. However, if your generator's starting state was instead x=6, then the generator's state evolved as follows: [6,524,39374,3959,34851,57956,21332]. So the seventh output will be 2. The releationship between the first six outputs and the seventh output is not deterministic.

The function is still deterministic. ANNs can learn the source code of the function , they re not looking for an analytical solution to the forward or inverse problem.

The point is, you can be handed 1) the entire source code of the PRNG, and 2) six outputs from it, and it's impossible to know what the starting state of the PRNG was because six outputs could have come from many different starting states. You could brute force every single starting state and find every one that would produce those 6 outputs but it still doesn't let you know the next value.

> Here's a sequence of outputs: 6,5,3,3,3,5. Does this information allow you to predict the next output? No.

Your prng looks like a truncated LCG, it could be broken if enough outputs are known. For example, 16 bits could be bruteforced in this case. If the internal state have more bits, depends on how much bits do the outputs provide, you could probably break it by Lattice (https://crypto.stackexchange.com/questions/37836/problem-wit...).

This PRNG is a truncated LCG. It can be "broken" if enough outputs are known. But that's not news: _any_ PRNG can be predicted if enough outputs are known.

For this specific generator, knowing 6 outputs is not enough to pin down the seventh output. Not by using a NN, not by brute-forcing the possible starting seeds, not by lattice methods, not by solving a linear system over a finite field. Unless you know the internal state of the generator, you won't be able to predict the seventh output. And the first 6 outputs simply don't reveal enough information to recover the internal state.

Reply on news.ycombinator.com