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

31–40 of 100 posts

Re: Cracking Random Number Generators Using Machine Learning

#31

Post by tubby12345 »

ChrisLomont wrote: post #23
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,…

How do you pick how many constants and they're relationships?

Re: Cracking Random Number Generators Using Machine Learning

#32

Post by tlholaday »

maweki wrote: post #29
swayvil wrote: post #19

They need to try this out on one those natural RNGs. Electron-noise or lava lamp. Maybe they'll discover something.

The only thing you could discover is, that it's not indeed a natural RNG, but a PRNG.

Strong evidence, perhaps dispositive evidence, for the Simulation Hypothesis.

Re: Cracking Random Number Generators Using Machine Learning

#33

Post by _hl_ »

cblconfederate wrote: post #24
_hl_ wrote: post #15

Earlier quoted context omitted.

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 informa…

The argument is fairly straightforward: Let n be the number of seed bits of the CSPRNG. Assume there exists an ANN that approximates the CSPRNG so that the number of possibly wrong output bits is at most polylogarithmic in n (otherwise you haven't really gained much insight from the ANN). Assume further that the ANN is sufficiently small so that a forward pass through the ANN takes at most polynomial time in n. Then you can create a polynomial-time algorithm that (i) runs the ANN on the observed CSPRNG samples/by querying the oracle, and then (ii) brute-forces the possible error bits in polynomial time, thereby recovering the full seed. But this is a contradiction with the assumption that the CSPRNG is secure, i.e. that it admits no polynomial-time adversary, q.e.d.

Re: Cracking Random Number Generators Using Machine Learning

#34

Post by joe__f »

IncRnd wrote: post #26
joe__f wrote: post #18

What are the potential implications of this?

None. This has been trivial to break for a long time. It is not considered a cryptographically secure random number generator.

Is it potentially useful for something outside of cryptography? I was watching a video on speedrunning where they were gaming the RNG somehow to improve their times

Re: Cracking Random Number Generators Using Machine Learning

#35

Post by gus_massa »

SeanLuke wrote: post #30
_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-re…

They can see the last 4 results, not only the last result. That's somewhat equivalent of partially seeing the secret internal state.

As a bad metaphor: Let's suppose that you enter a lifter and a NN without internal state must predict which button you will press, but now consider the case where the NN can see a video of everything you have done during the last year. Do you think it's possible?

Re: Cracking Random Number Generators Using Machine Learning

#36

Post by _hl_ »

gus_massa wrote: post #35
SeanLuke wrote: post #30

Earlier quoted context omitted.

> 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-re…

They can see the last 4 results, not only the last result. That's somewhat equivalent of partially seeing the secret internal state. As a bad metaphor: Let's suppose that you enter a lifter and a NN without internal state must predict which button you will press, but now consider the case where the NN can see a video of everything you have done during the last year. Do you think it's possible?

> That's somewhat equivalent of partially seeing the secret internal state

Not just partially, xorshift128 is designed such that the output depends only on the last 4 results. So this is "just" learning the output function of xorshift as a neural network.

Re: Cracking Random Number Generators Using Machine Learning

#37

Post by cblconfederate »

_hl_ wrote: post #33
cblconfederate wrote: post #24

Earlier quoted context omitted.

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 informa…

The argument is fairly straightforward: Let n be the number of seed bits of the CSPRNG. Assume there exists an ANN that approximates the CSPRNG so that the number of possibly wrong output bits is at most polylogarithmic in n (otherwise you haven't really gained much insight from the ANN). Assume further that the ANN is sufficiently small so that a forward pass through the ANN takes at most polynomial time in n. Then…

The difference is that ANNs make approximations. It could be manageably small and learn an approximation of the PRNG code that succeeds for a large number of outputs, even if running a fully accurate network is impossible. I think the complexity of the PRNG recursive algorithm , when unrolled through time for large number of steps, is the relevant complexity here. The ANN is not necessarily trying to devise a new function that recovers the seed.

Re: Cracking Random Number Generators Using Machine Learning

#38

Post by jameshart »

SeanLuke wrote: post #30
_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-re…

It looks like this specific algorithm can easily be deterministically reversed - the XORs and bitwise shifts mean that, given four output numbers, you can completely determine what state it was in before the numbers were generated - and, in fact, that there is probably a simple series of bit shifts and XORs you can perform on the last four outputs that produces the next number.

Bit shifts and XORs are very much the kind of pattern neural networks should excel at learning - they mean that each output bit is a simple linear function of the input bits.

Actually doing it is still a good demonstration! But the fact that the function in question is used as a PRNG doesn’t imply that other PRNGs would be susceptible to a similar approach.

Re: Cracking Random Number Generators Using Machine Learning

#40

Post by SeanLuke »

gus_massa wrote: post #35
SeanLuke wrote: post #30

Earlier quoted context omitted.

> 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-re…

They can see the last 4 results, not only the last result. That's somewhat equivalent of partially seeing the secret internal state. As a bad metaphor: Let's suppose that you enter a lifter and a NN without internal state must predict which button you will press, but now consider the case where the NN can see a video of everything you have done during the last year. Do you think it's possible?

That's only ~365 values. XORshift32 has a period of 2^32-1, a good portion of that (I'd imagine) unique. If XORshift had really good randomness properties, at the extreme we'd expect that the NN would have to special case all of them. What this implies is that XORshift has easily cracked, nonrandom, repeatable patterns (which we suspect of course since it fails certain tests) and that the NN has identified them.
Post reply on HN