Skip to main content
added 620 characters in body
Source Link
Neil Slater
  • 33.3k
  • 3
  • 44
  • 65

Machine Learning is a bad fit to this problem.

Even simple PRNGs that are not suitable for use in simulators (such as rand()) are varied enough that it is very hard to reverse engineer them statistically using generic techniques - essentially what 90% of ML does is fit a generic model to data statistically by altering parameters. The remaining 10% might do things in specialist manner, such as saving all the data and picking best option.

In theory most ML approaches would eventually solve a PRNG, however that would typically involve iterating through the entire state space of the PRNG multiple times. The statistical relationship between internal state, next state and output of a PRNG is complex by design, so that this is the only "black box" statistical approach, and this is clearly not feasible for any real implementation of a random number generator, which is going to have at least $2^{31}$ states on modern machines. Perhaps older 16-bit PRNGs, with a single value for state might be tractable.

An AI advanced enough to attempt to reverse engineer the output logically based on purely the data and researching how RNGs work is too advanced for current ML techniques to consider.

That leaves approaches that might try to construct a similar RNG, such as Genetic Programming (where the genome is converted to executable code). The trouble with this approach is there is no heuristic for a RNG that measures how close its output is to a target. A single bit of state difference or any tiny but meaningful change in generated RNG design will produce output that has no similarities with the target output whatsoever. Without such a measure you have no fitness function, and no way to attempt a guided search using the many discrete optimisation tools from AI.

Instead the usual approach to "breaking" a PRNG is to analyse the algorithm. Knowing the algorithm of many non-cryptographic PRNGs can allow predicting the internal state of the generator, sometimes in very few steps (for really simple Linear Congruential Generators that might be just a single step!).

Machine Learning is a bad fit to this problem.

Even simple PRNGs that are not suitable for use in simulators (such as rand()) are varied enough that it is very hard to reverse engineer them statistically using generic techniques - essentially what 90% of ML does is fit a generic model to data statistically by altering parameters. The remaining 10% might do things in specialist manner, such as saving all the data and picking best option.

In theory most ML approaches would eventually solve a PRNG, however that would typically involve iterating through the entire state space of the PRNG multiple times. The statistical relationship between internal state, next state and output of a PRNG is complex by design, so that this is the only "black box" statistical approach, and this is clearly not feasible for any real implementation of a random number generator, which is going to have at least $2^{31}$ states on modern machines. Perhaps older 16-bit PRNGs, with a single value for state might be tractable.

Instead the usual approach to "breaking" a PRNG is to analyse the algorithm. Knowing the algorithm of many non-cryptographic PRNGs can allow predicting the internal state of the generator, sometimes in very few steps (for really simple Linear Congruential Generators that might be just a single step!)

Machine Learning is a bad fit to this problem.

Even simple PRNGs that are not suitable for use in simulators (such as rand()) are varied enough that it is very hard to reverse engineer them statistically using generic techniques - essentially what 90% of ML does is fit a generic model to data statistically by altering parameters. The remaining 10% might do things in specialist manner, such as saving all the data and picking best option.

In theory most ML approaches would eventually solve a PRNG, however that would typically involve iterating through the entire state space of the PRNG multiple times. The statistical relationship between internal state, next state and output of a PRNG is complex by design, so that this is the only "black box" statistical approach, and this is clearly not feasible for any real implementation of a random number generator, which is going to have at least $2^{31}$ states on modern machines. Perhaps older 16-bit PRNGs, with a single value for state might be tractable.

An AI advanced enough to attempt to reverse engineer the output logically based on purely the data and researching how RNGs work is too advanced for current ML techniques to consider.

That leaves approaches that might try to construct a similar RNG, such as Genetic Programming (where the genome is converted to executable code). The trouble with this approach is there is no heuristic for a RNG that measures how close its output is to a target. A single bit of state difference or any tiny but meaningful change in generated RNG design will produce output that has no similarities with the target output whatsoever. Without such a measure you have no fitness function, and no way to attempt a guided search using the many discrete optimisation tools from AI.

Instead the usual approach to "breaking" a PRNG is to analyse the algorithm. Knowing the algorithm of many non-cryptographic PRNGs can allow predicting the internal state of the generator, sometimes in very few steps (for really simple Linear Congruential Generators that might be just a single step!).

Source Link
Neil Slater
  • 33.3k
  • 3
  • 44
  • 65

Machine Learning is a bad fit to this problem.

Even simple PRNGs that are not suitable for use in simulators (such as rand()) are varied enough that it is very hard to reverse engineer them statistically using generic techniques - essentially what 90% of ML does is fit a generic model to data statistically by altering parameters. The remaining 10% might do things in specialist manner, such as saving all the data and picking best option.

In theory most ML approaches would eventually solve a PRNG, however that would typically involve iterating through the entire state space of the PRNG multiple times. The statistical relationship between internal state, next state and output of a PRNG is complex by design, so that this is the only "black box" statistical approach, and this is clearly not feasible for any real implementation of a random number generator, which is going to have at least $2^{31}$ states on modern machines. Perhaps older 16-bit PRNGs, with a single value for state might be tractable.

Instead the usual approach to "breaking" a PRNG is to analyse the algorithm. Knowing the algorithm of many non-cryptographic PRNGs can allow predicting the internal state of the generator, sometimes in very few steps (for really simple Linear Congruential Generators that might be just a single step!)