23 ms·
Cracking Random Number Generators Using Machine Learning
- bionhoward 5y agoCould this make a more performant PRNG for generative models, random simulations, etc?
- SavantIdiot 5y agoI'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?
- tptacek 5y agoThere's been over a decade of research into machine learning cryptanalysis. It's not a new idea.
- SavantIdiot 5y agoIf we knew everything we wouldn't be reading this website. Or do you already know everything and just like being dismissive?
- tptacek 5y agoIs there more information you’re looking for? Beyond what I said, I could have added “it has not been broken.”
- cblconfederate 5y agoANNs 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 ?
- seanhunter 5y agoI could see how they could learn to approximate the function if they could observe the internal state, but without being able to see the state, if it's a strong PRNG how would they be able to do it? Edit: Reading the paper they're approximating xorshift which as I understand it is fast and efficient but has very little internal state and is not a strong PRNG.
- cblconfederate 5y agoWould it be called pseudorandom if it had an undecipherable internal state such as temperature or sth? aren't all PRNGs deterministic functions by definition?
- adrian_b 5y agoFor 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 reduced to the second, because the unknown output function must be derived using known functions from a secret key, so you can consider the secret key as the part of the state that is unknown. (There is a third possible structure for a PRNG, with known state, known output function and unknown transition function, but this is obsolete for making unpredictable PRNGs, as it has inferior properties). So yes, a pseudo RNG that has a part of its state that remains unknown may produce an output sequence from which it is computationally infeasible to determine its complete state. Nonetheless, an unpredictable PRNG remains a PRNG, not a true RNG. You can reproduce any time its output sequence if you know the secret part of the state, e.g. when you are the recipient of an encrypted message. If a ML method would be able to recover the secret part of the state when given the output sequence, obviously that PRNG would be considered broken. Many PRNGs are designed for high-speed in non-cryptographic applications, e.g. simulations, and for those PRNGs it is usually very easy to determine the internal state from the output sequence, without the need of any ML.
- Hendrikto 5y agoThe 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.
- ChrisLomont 5y agoIt 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.
- tubby12345 5y agoHow do you pick how many constants and they're relationships?
- Someone 5y agoI 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.
- ChrisLomont 5y agoIt'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 original unknown state. It's absolutely trivial, taking a few lines of code. I've broken all sorts of code using similar tools.
- smitty1e 5y agoIf machine learning is ultimately pattern recognition, then, is random number generation the antithesis of machine learning?
- willis936 5y agoPerhaps the machine is hallucinating. https://en.m.wikipedia.org/wiki/Pareidolia https://en.m.wikipedia.org/wiki/Pareidolia
- SilasX 5y agoI would say “dual” rather than antithesis, in that [machine] learning involves finding regularities, while RNGs (like encryption) seek to obscure them, but yes.
- joe__f 5y agoWhat are the potential implications of this?
- IncRnd 5y agoNone. This has been trivial to break for a long time. It is not considered a cryptographically secure random number generator.
- joe__f 5y agoIs 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
- upofadown 5y agoPredictable 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.
- _hl_ 5y ago> 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?
- upofadown 5y agoA hopefully relevant search: * https://www.google.com/search?q=motherboard+spread+spectrum https://www.google.com/search?q=motherboard+spread+spectrum
- joe__f 5y ago
- swayvil 5y agoThey need to try this out on one those natural RNGs. Electron-noise or lava lamp. Maybe they'll discover something.
- maweki 5y agoThe only thing you could discover is, that it's not indeed a natural RNG, but a PRNG.
- tlholaday 5y agoStrong evidence, perhaps dispositive evidence, for the Simulation Hypothesis.
- JackFr 5y agoNo it isn’t.
- swayvil 5y agoA 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?
- chaboud 5y agoIt could just as easily be evidence of a previously non-understood physical phenomenon or mechanism being recognized by new methods. Of course, that’s exactly the kind of thing a simulation would type!
- rsfern 5y agoIsn’t the quantum nature of reality already like looking through a microscope and finding voxels? I don’t see why finding underlying structure in what we expect to be pure noise has to mean our reality is a simulation. I guess it could be consistent with that, but couldn’t it also be consistent with some previously undiscovered physics, much like the development of quantum mechanics?
- _hl_ 5y agoWhat 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.
- SeanLuke 5y ago> 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.
- gus_massa 5y agoThey 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?
- _hl_ 5y ago> 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.
- phenkdo 5y agoHow Is ML being used to generate more randomness in the PRNGs? Wouldn't the opposite be a more interesting research idea?
- sillysaurusx 5y agoThis 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.
- deleted 5y ago[deleted]
- deleted 5y ago[deleted]
- deegles 5y agoSince SHA-1 is known to be broken, could this be adapted to create collisions on demand? How much training would be required to break SHA256?
- tptacek 5y agoNo, you can't use ML to break SHA256.
- deleted 5y ago[deleted]
- arendtio 5y agoI think this is a very good idea, because both topics (random number generators and AI) are hard to fully understand and using both against each other could be used to teach both topics with increasing difficulty.
- ChuckMcM 5y agoCan't wait for the first time a couple of thousand people all pick the winning lottery numbers :-) This looks like excellent work.