Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Cracking Random Number Generators Using Machine Learning

research.nccgroup.com

Post reply on HN
Print view View original

21–30 of 100 posts

Re: Cracking Random Number Generators Using Machine Learning

#21

Post by adrian_b »

joshuaissac wrote: post #14
adrian_b wrote: post #9

Earlier quoted context omitted.

For some PRNGs it is intended that the output values must be unpredictable, e.g. for using in cryptographic applications. For such PRNGs, you can either view them as having a known state and an unknown output function or you can view them as having a known output function and a state composed of a known part and of an unknown, secret, part. The second point of view is more general, as the first case can always be red…

There are CSPRNGs like Fortuna that contain an entropy accumulator, so even if the secret part of the state is compromised, it can recover.

True, but they belong to a different class, which are used for applications like key generation, where there is no need to ever reproduce a certain output sequence.

Such RNGs are used instead of true RNGs, which might not be able to provide the required random numbers fast enough. They cannot be used instead of normal PRNGs in most of their applications.

Unpredictable cryptographic PRNGs can be used instead of any other PRNG for simulations, games, MonteCarlo integration etc. and they are actually better than simpler predictable PRNGs, except that they might be too slow.

On modern CPUs with hardware AES instructions, any of the traditional PRNGs that is not faster than computing AES, has become obsolete, as using AES with a counter would provide a random sequence with a higher quality.

Re: Cracking Random Number Generators Using Machine Learning

#22

Post by saithound »

cblconfederate wrote: post #12
saithound wrote: post #10

Earlier quoted context omitted.

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, an…

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.

Re: Cracking Random Number Generators Using Machine Learning

#23

Post by ChrisLomont »

Hendrikto wrote: post #3

The underlying problem seems to be that the PRNG they are emulating is giving away its internal state. I wouldn‘t expect this to work for PCG, for example.

It would also work for PCG. You're simply modeling the PRNG and learning the internal state from outputs.

It's even easier using Z3 or your own SAT solver. I've broken pretty much all non-crypto PRNGS using Z3, and it's trivial to do so. You simply model the PRNG in Z3, with unknown constants, plug in a few values from the output (or even parts of output, or even non-consecutives ones, anything you derive from them, etc - just model how the inputs formed), and ask Z3 to solve for the internal state. It works every time.

Re: Cracking Random Number Generators Using Machine Learning

#24

Post by cblconfederate »

_hl_ wrote: post #15
cblconfederate wrote: post #11

Earlier quoted context omitted.

i dont know much about cryptography but why would it need to learn its inverse? I mean a theoretically absurdly large/wide network can approximate almost any function . Are PRFs resistant to that?

The underlying assumption of all of modern cryptography is that one-way functions exist (implying P != NP), and further that the algorithms we use in practice are actually instances of these theoretically hard problems. So there provably always exists an algorithm that breaks any given PRNG, it will just always take you very long to compute and/or a lot of queries to the PRNG. ANNs are nothing special in that regard,…

I'm not sure if there is any guarantee on the size of the network required. Problems like vision or language were also very complex and nonlinear but anns were able to handle them. It is analytically difficult to find an inverse function but the ANNs are not trying to do that, merely approximating the source code of the PRNG as piecewise-nonlinear functions. So i wouldn't think the former problem (inverse) is informative about the difficulty of the ANN training. At least i dont know if there's theoretical work on designing ANN-hard cryptographic functions

Re: Cracking Random Number Generators Using Machine Learning

#25

Post by ChrisLomont »

cblconfederate wrote: post #2

ANNs are function approximators so it s trivial for them to learn a mathematical function like a prng. The seed is irrelevant to the ANN, it just learns the function's sequence, regardless of where it started. Which makes the interesting question how many people are already cracking PRNGs with ANNs ?

They're already trivial to crack 100% with Z3. Using something fuzzy like a neural net is by far not an optimal way to break it.

Re: Cracking Random Number Generators Using Machine Learning

#27

Post by _hl_ »

What they are doing is essentially encoding the binary circuit of the xorshift128 PRNG as a neutal network. The fact that you can encode abritrary binary circuits as neural networks is well-known, so it's not surprising that it is possible to do this.

The interesting and perhaps surprising result is the demonstration that it is possible to train this network using standard gradient methods, when choosing the proper loss function for the problem and designing the network with the required domain-knowledge of the algorithm it is supposed to model. In other words, this can be seen as an example of how well-educated network design and choice of loss function massively impacts the performance of your fancy ML model.

For more "real-world" problems, it is often very difficult to come up with a network design that encodes the implicit constraints of the problem, mostly because these constraints are not even known (that's why we use ML!), but results like the recent AlphaFold show that even for these problems, thoughtful design of the model architecture goes a very long way.

Re: Cracking Random Number Generators Using Machine Learning

#28

Post by cblconfederate »

saithound wrote: post #22
cblconfederate wrote: post #12

Earlier quoted context omitted.

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…

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.

Re: Cracking Random Number Generators Using Machine Learning

#30

Post by SeanLuke »

_hl_ wrote: post #27

What they are doing is essentially encoding the binary circuit of the xorshift128 PRNG as a neutal network. The fact that you can encode abritrary binary circuits as neural networks is well-known, so it's not surprising that it is possible to do this. The interesting and perhaps surprising result is the demonstration that it is possible to train this network using standard gradient methods, when choosing the proper l…

> What they are doing is essentially encoding the binary circuit of the xorshift128 PRNG as a neutal network. The fact that you can encode abritrary binary circuits as neural networks is well-known, so it's not surprising that it is possible to do this.

Mcullough-Pitts aside, I think this is unfair. What's interesting to me is that they can predict a recurrent algorithm with internal state using with a trivial NON-recurrent feedforward network without any internal state.

Post reply on HN