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

61–70 of 100 posts

Re: Cracking Random Number Generators Using Machine Learning

#61

Post by ChrisLomont »

Someone wrote: post #55
tubby12345 wrote: post #31

Earlier quoted context omitted.

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

I think that’s the “You simply model the PRNG in Z3” part. Whether that’s simple depends is debatable, but for example would be if somebody open-sourced the server-side of their poker dealing site.

Also, to break unknown/unseen PRNG, model a few popular classes of PRNG, a few common reductions (so for cards the naive val%52 and better rejection sampling), then solve across the states till you get one. Then watch a few more outputs, check that you guessed the source and reduction, and now you've cracked that too.

I doubt any poker site uses anything other than a crypto rand for deals because the technique I just explained would eat them alive. They can use fast and insecure PRNG for doing Monte Carlo hand evaluation, though, since that doesn't give you any advantage.

Re: Cracking Random Number Generators Using Machine Learning

#62

Post by SavantIdiot »

I'd like to see a neural net have a go at a DRBG, such as one using an HMAC/SHA256 and PBDKF2, a cryptographically strong pseudo-random bit generator. Is it possible there's something that analytic methods of this RFC didn't catch that a neural net could?

Re: Cracking Random Number Generators Using Machine Learning

#63

Post by tmoertel »

ChrisLomont wrote: post #60
Someone wrote: post #55

Earlier quoted context omitted.

I think that’s the “You simply model the PRNG in Z3” part. Whether that’s simple depends is debatable, but for example would be if somebody open-sourced the server-side of their poker dealing site.

It's quite simple. Z3 supports every basic integer option out of the box. You literally write the same code as the original prng. Instead of a uint32, or uint64, or float32, etc., you use the Z3 equivalent type. That's it. You define the state as unknown, but same Z3 type as in C or JavaScript. Then you run the function once. Set it to the output you see, repeat a few observed outputs, then tell Z3 to solve for the o…

Do you have a worked example of finding a PRNG's internal state that you could share? (Most people are unfamiliar with Z3 and other SMT solvers. Seeing a relevant worked example would be very illustrative.)

Re: Cracking Random Number Generators Using Machine Learning

#64

Post by bawolff »

More-nitors wrote: post #50
_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?

I'm pretty sure it can't

Re: Cracking Random Number Generators Using Machine Learning

#66

Post by downandout »

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

So would this model be able to predict any imperfect PRNG with some degree of accuracy, or just xorshift128? For the purposes I'm thinking, even 1% accuracy above purely random would suffice.

Re: Cracking Random Number Generators Using Machine Learning

#67

Post by tubby12345 »

ChrisLomont wrote: post #60
Someone wrote: post #55

Earlier quoted context omitted.

I think that’s the “You simply model the PRNG in Z3” part. Whether that’s simple depends is debatable, but for example would be if somebody open-sourced the server-side of their poker dealing site.

It's quite simple. Z3 supports every basic integer option out of the box. You literally write the same code as the original prng. Instead of a uint32, or uint64, or float32, etc., you use the Z3 equivalent type. That's it. You define the state as unknown, but same Z3 type as in C or JavaScript. Then you run the function once. Set it to the output you see, repeat a few observed outputs, then tell Z3 to solve for the o…

Oh gotcha. I thought you meant that you were some how modeling the prng using some reduced set of constraints.

Re: Cracking Random Number Generators Using Machine Learning

#68

Post by downandout »

ChrisLomont wrote: post #61
Someone wrote: post #55

Earlier quoted context omitted.

I think that’s the “You simply model the PRNG in Z3” part. Whether that’s simple depends is debatable, but for example would be if somebody open-sourced the server-side of their poker dealing site.

Also, to break unknown/unseen PRNG, model a few popular classes of PRNG, a few common reductions (so for cards the naive val%52 and better rejection sampling), then solve across the states till you get one. Then watch a few more outputs, check that you guessed the source and reduction, and now you've cracked that too. I doubt any poker site uses anything other than a crypto rand for deals because the technique I just…

So building on this...many physical casinos use a manual shuffle, especially at higher limits, as bigger players tend to distrust shuffle machines. Even some online casinos with live dealers will shuffle the previous shoe on camera, manually.

Since getting a truly random shuffle would take too long, this is a poor method of getting random results. Would it be possible to, at least to some degree, predict the order of the cards using one of these models, given the order of the cards prior to shuffling? I'm thinking something along the lines of being able to say that the odds of a given card being the next one are higher than they should be, not outright predicting the full order of the cards.

Re: Cracking Random Number Generators Using Machine Learning

#70

Post by JackFr »

swayvil wrote: post #48
JackFr wrote: post #43

Earlier quoted context omitted.

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?

Intellectually the simulation hypothesis is creationism’s hipster cousin.

It’s not a falsifiable hypothesis. It makes so many implicit assumptions it’s scarcely worth talking about.

It’s fake smart and not interesting.

Post reply on HN