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

41–50 of 100 posts

Re: Cracking Random Number Generators Using Machine Learning

#41

Post by cookiengineer »

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

This whole project reads as a beginner's guide to ML and what it can do.

I mean, it's nice and all but at some point I would've expected at least a mention that this all was solvable with a quantized neural network with low bit precision as well.

Most of the article was about LSTMs and the recurrent design of those is just a very inefficient way to solve the problem at hand.

I would've expected an LSTM try for something like a seed based randomizer like MT19937 and that the unfolding layers are trained on the seed itself with the idea that they learn how to predict the seed's state for the next iteration.

Something like this would be really important research, especially in times where time based one time passwords are used everywhere, and their cryptographic security of how seeds are generated is important.

Re: Cracking Random Number Generators Using Machine Learning

#42

Post by SeanLuke »

_hl_ wrote: post #36
gus_massa wrote: post #35

Earlier quoted context omitted.

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.

Perhaps you might consider how big that output function ideally is, then compare to the capacity of the neural network they used and the number of samples provided.

Re: Cracking Random Number Generators Using Machine Learning

#44

Post by roywiggins »

cblconfederate wrote: post #28
saithound wrote: post #22

Earlier quoted context omitted.

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.

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.

Re: Cracking Random Number Generators Using Machine Learning

#45

Post by cblconfederate »

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.

If a hidden variables model is found, it would be the discovery of the century

Re: Cracking Random Number Generators Using Machine Learning

#46

Post by sillysaurusx »

cookiengineer wrote: post #41
_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…

This whole project reads as a beginner's guide to ML and what it can do. I mean, it's nice and all but at some point I would've expected at least a mention that this all was solvable with a quantized neural network with low bit precision as well. Most of the article was about LSTMs and the recurrent design of those is just a very inefficient way to solve the problem at hand. I would've expected an LSTM try for someth…

> I mean, it's nice and all but at some point I would've expected at least a mention that this all was solvable with a quantized neural network with low bit precision as well.

This doesn't matter, so I'm not sure why you were expecting it.

I'm struggling to be diplomatic, so I'll leave it at that.

Re: Cracking Random Number Generators Using Machine Learning

#47

Post by rurban »

SeanLuke wrote: post #40
gus_massa wrote: post #35

Earlier quoted context omitted.

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.

We knew that before the two ML attempts. You just need to look at the source. There are several other trivial PRNG's with the exact same properties. Never use a trivial PRNG for security or seeding.

Re: Cracking Random Number Generators Using Machine Learning

#48

Post by swayvil »

JackFr wrote: post #43
tlholaday wrote: post #32

Earlier quoted context omitted.

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

No it isn’t.

A fundamentally entropic phenomenon is discovered to be patterened. It would be like looking through a microscope and seeing voxels.

How is this not strong evidence for simulation?

Re: Cracking Random Number Generators Using Machine Learning

#49

Post by sillysaurusx »

This is pretty hilarious. I just noticed that this is published by NCC Group. (Former NCC Group pentester here, and now I happen to be an ML engineer.)

I don't think HN's negativity is warranted. But there's also some confusion, which I'd like to help clear up.

People here seem confused about "Why? Why do this?"

The answer is simply that it's an interesting problem. That's it.

It doesn't need to be important, or a promising research direction, or mention low bit precision, or quantized networks, or be performant, or tackle a complex PRNG.

It just needs to be an interesting problem which you can solve. Love of ML is no more complicated than that.

Knowing the fellas at NCC, I'm quite certain that they did this mostly out of intellectual curiosity rather than some grand plan to advance the state of the art of ML. And I think that's wonderful. More people should get into ML with exactly that mindset.

Re: Cracking Random Number Generators Using Machine Learning

#50

Post by More-nitors »

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

hm can this be applied to AES?
Post reply on HN