Cracking Random Number Generators Using Machine Learning
research.nccgroup.com
research.nccgroup.com
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.
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.
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?
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.
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.
It's an interesting story: https://towardsdatascience.com/history-of-the-first-ai-winte...
But you are quite correct about the AI winter.
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.
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.
Having met a few casino owners, and many more game supervisors actually charged with understanding the math of the games to avoid exploitation, I can tell you this is patently false.
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.
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.
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 absolutely trivial, taking a few lines of code.
I've broken all sorts of code using similar tools.
// Code to demonstrate finding the hidden seed of a PRNG with Z3
// Chris Lomont Oct 2021
// Answering this comment on Hacker News https://news.ycombinator.com/item?id=28886698
// Start by getting Z3, a theorem prover from Microsoft, via nuget. See https://github.com/Z3Prover/z3
using Microsoft.Z3;
using System;
// get a solution
ulong Solution(Context ctx, BoolExpr f, BitVecExpr seed)
{
Solver s = ctx.MkSolver();
s.Assert(f); // assert constraint into solver
if (s.Check() == Status.SATISFIABLE)
{
var m = s.Model;
Expr e = m.Evaluate(seed);
return ulong.Parse(e.ToString());
}
else
throw new Exception("Fatal error");
}
// simple PRNG, used in many old C libs
UInt32 next = 0x1234;
UInt32 rand()
{
next = next \* 214013 + 2531011;
return (next / 65536) % 32768;
}
void Test()
{
var R = new Random();
next = (uint)R.Next();
var start = next;
Console.WriteLine($"Starting seed {next:X8}");
using (var ctx = new Context())
{
// 32 bit vector type
Sort bv_type = ctx.MkBitVecSort(32);
// unknown seed - we will solve for this
BitVecExpr seed = ctx.MkBVConst("seed", 32);
// constants used in the PRNG
BitVecExpr c214 = (BitVecNum)ctx.MkNumeral("214013", bv_type);
BitVecExpr c253 = (BitVecNum)ctx.MkNumeral("2531011", bv_type);
BitVecExpr c65536 = (BitVecNum)ctx.MkNumeral("65536", bv_type);
BitVecExpr c32768 = (BitVecNum)ctx.MkNumeral("32768", bv_type);
// track the boolean to satisfy
BoolExpr be = ctx.MkTrue();
var next = seed; // start here
int pass = 0;
while(true)
{
++pass;
if (pass > 10) break;
// the sampled random
var r = rand();
BitVecExpr rndBV = (BitVecNum)ctx.MkNumeral(r, bv_type);
// make this code using Z3 variables
//next = next * 214013 + 2531011;
//return (next / 65536) % 32768;
next = ctx.MkBVAdd(ctx.MkBVMul(next, c214), c253);
var ret = ctx.MkBVURem(ctx.MkBVUDiv(next, c65536), c32768);
// add a constraint boolean for this "Z3 ret = returned value"
be = ctx.MkAnd(be, ctx.MkEq(ret, rndBV));
// get solution
var val = Solution(ctx, be, seed);
// todo - can check unique by adding "seed != soln" to the boolean and checking
Console.WriteLine($"{pass} : 0x{val:X8}");
if (val == start)
break; // done - can also break when shown unique
}
}
}
Test();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.
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.
"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."
This looks like excellent work.
Maybe they'll discover something.
How is this not strong evidence for simulation?
Of course, that’s exactly the kind of thing a simulation would type!
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?
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.
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.
Fascinating! That seems very counterintuitive, where can I learn more about this?
* https://www.google.com/search?q=motherboard+spread+spectrum
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.
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.
Such RNGs are used instead of true RNGs, which might not be able to provide the required random numbers fast enough. They cannot be used instead of normal PRNGs in most of their applications.
Unpredictable cryptographic PRNGs can be used instead of any other PRNG for simulations, games, MonteCarlo integration etc. and they are actually better than simpler predictable PRNGs, except that they might be too slow.
On modern CPUs with hardware AES instructions, any of the traditional PRNGs that is not faster than computing AES, has become obsolete, as using AES with a counter would provide a random sequence with a higher quality.
In most cases, the output is determined by the output function based on a small part of the state (e.g. you may have 128 bits of state, feed the first 64 bits of it to an output function, and derive a 32-bit output as a result). This means that you don't learn much about the internal state of the generator merely by looking at an output value: you need to observe a lot of consecutive outputs to recover the internal state of the generator, and without knowing the internal state it's difficult (i.e. very hard to impossible) to use a relatively small number of known outputs to predict the next output.
The xorshift128 generator tested in the article has a nigh-trivial output function (because it's designed to be fast, not hard-to-predict) and a very simple transition function, which is why 4 outputs can be used to recover the internal state and to train a NN to predict the next output.
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 75x + 74 (mod 65537), and output the first digit of your internal state (your random number)
Here's a sequence of outputs: 6,5,3,3,3,5. Does this information allow you to predict the next output? No.
For example, if the generator's starting state is x=60160, then the generator's internal state evolves as follows: [60160,55558,38093,38958,38296,54183,505]. So the seventh output will be 5. However, if your generator's starting state was instead x=6, then the generator's state evolved as follows: [6,524,39374,3959,34851,57956,21332]. So the seventh output will be 2. The releationship between the first six outputs and the seventh output is not deterministic.
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...).
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.
2. To break a PRF it'd need to learn its inverse. For many of them it's unlikely that a small circuit computing the inverse even exists, so a non-iterated NN couldn't even represent the desired function, let alone converge to it.
So yes, an absurdly large ANN will break any PRNG, but so will other absurdly long-running algorithms, some of which are quite trivial: Just try every possible seed until you get the same sequence as what you observe, repeat until only one candidate seed is left.
EDIT: To add to this, you seem to be referring to the universal approximation theorems for ANNs. These theorems state that for any function (subject to some conditions not relevant here) and any arbitrary approximation ratio, there exists a finite ANN that approximates the function to within the desired approximation ratio. It says nothing about whether it's possible to train such an ANN, merely that it exists. Which in this case is a fairly trivial results, you could feasibly create a look-up table of PRNG sequences to seeds and encode that as an enormous ANN. But finding/training this ANN is prohibitively expensive.
Of course, this is assuming that practical CSPRNGs conform to the theory, but we're just debating theory here.
Yes. But chances are that the network size scales exponentially with the number of e.g. input bits. Good luck building/training/storing a model with 2^128 neurons in the hidden layer.