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

81–90 of 100 posts

Re: Cracking Random Number Generators Using Machine Learning

#81

Post by ChrisLomont »

downandout wrote: post #68
ChrisLomont wrote: post #61

Earlier quoted context omitted.

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…

If I recall, something like 7 hand shuffles becomes indistinguishable from random. I'd guess a pro could get this level of mixing in a few shuffles

Re: Cracking Random Number Generators Using Machine Learning

#82

Post by ChrisLomont »

tmoertel wrote: post #63
ChrisLomont wrote: post #60

Earlier quoted context omitted.

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.)

Yeah, I was considering posting one. I've lately switched to Z3 under C# since it's so easy to do things... If I get around to it tonight I'll make a post.

Re: Cracking Random Number Generators Using Machine Learning

#83

Post by upofadown »

_hl_ wrote: post #76
upofadown wrote: post #74

Earlier quoted context omitted.

Predictable bit streams that look random are useful for communications. Satellite navigation systems like GPS for instance use such streams where the whole idea is for a receiver to sync up on on the bitstream. An example where no one even cares exactly what the bitsream is can be found on motherboards where a bitstream is used to jitter the system clock to spread out any radio interference caused by the motherboard.

> to jitter the system clock to spread out any radio interference caused by the motherboard Fascinating! That seems very counterintuitive, where can I learn more about this?

A hopefully relevant search:

* https://www.google.com/search?q=motherboard+spread+spectrum

Re: Cracking Random Number Generators Using Machine Learning

#84

Post by nsonha »

sillysaurusx wrote: post #46
cookiengineer wrote: post #41

Earlier quoted context omitted.

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.

the rest of their comment sounds insightful

Re: Cracking Random Number Generators Using Machine Learning

#85

Post by SilasX »

smitty1e wrote: post #17

If machine learning is ultimately pattern recognition, then, is random number generation the antithesis of machine learning?

I would say “dual” rather than antithesis, in that [machine] learning involves finding regularities, while RNGs (like encryption) seek to obscure them, but yes.

Re: Cracking Random Number Generators Using Machine Learning

#86

Post by shaicoleman »

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

I don't think this will work on PCG.

"pcg32, which has state-space size of 2^127 (2^64 period × 2^63 streams) and produces 32-bit outputs."

https://www.pcg-random.org/predictability.html

That said, The PCG author does not recommend to use it for cryptography.

"Although it is less trivial to predict than many mainstream generators, that does not mean it should be considered crypographically secure. Exactly how hard it is to break different members of the PCG family is unknown at this time."

https://www.pcg-random.org/other-rngs.html

Re: Cracking Random Number Generators Using Machine Learning

#87

Post by downandout »

ChrisLomont wrote: post #81
downandout wrote: post #68

Earlier quoted context omitted.

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…

If I recall, something like 7 hand shuffles becomes indistinguishable from random. I'd guess a pro could get this level of mixing in a few shuffles

Yeah, but that's 7 shuffles of a single deck. Most casinos use 6 or 8 decks. They are certainly not shuffling 42+ times.

Re: Cracking Random Number Generators Using Machine Learning

#88

Post by maple3142 »

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…

> Here's a sequence of outputs: 6,5,3,3,3,5. Does this information allow you to predict the next output? No.

Your prng looks like a truncated LCG, it could be broken if enough outputs are known. For example, 16 bits could be bruteforced in this case. If the internal state have more bits, depends on how much bits do the outputs provide, you could probably break it by Lattice (https://crypto.stackexchange.com/questions/37836/problem-wit...).

Re: Cracking Random Number Generators Using Machine Learning

#89

Post by danbmil99 »

IAmGraydon wrote: post #80
downandout wrote: post #66

Earlier quoted context omitted.

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.

Financial market prediction is where my mind went too.

Good luck with that. Financial markets are not pRNG's -- they are more like an adversary you are playing poker with. Think game theory, rather than pattern matching.

Re: Cracking Random Number Generators Using Machine Learning

#90

Post by saithound »

maple3142 wrote: post #88
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…

> Here's a sequence of outputs: 6,5,3,3,3,5. Does this information allow you to predict the next output? No. Your prng looks like a truncated LCG, it could be broken if enough outputs are known. For example, 16 bits could be bruteforced in this case. If the internal state have more bits, depends on how much bits do the outputs provide, you could probably break it by Lattice ( https://crypto.stackexchange.com/question…

This PRNG is a truncated LCG. It can be "broken" if enough outputs are known. But that's not news: _any_ PRNG can be predicted if enough outputs are known.

For this specific generator, knowing 6 outputs is not enough to pin down the seventh output. Not by using a NN, not by brute-forcing the possible starting seeds, not by lattice methods, not by solving a linear system over a finite field. Unless you know the internal state of the generator, you won't be able to predict the seventh output. And the first 6 outputs simply don't reveal enough information to recover the internal state.

Post reply on HN