Cracking Random Number Generators Using Machine Learning
research.nccgroup.com
Cracking Random Number Generators Using Machine Learning
1–10 of 100 posts
Re: Cracking Random Number Generators Using Machine Learning
#2ANNs 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 ?
Re: Cracking Random Number Generators Using Machine Learning
#3The 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.
Re: Cracking Random Number Generators Using Machine Learning
#4ANNs 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 ?
I 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.
Re: Cracking Random Number Generators Using Machine Learning
#5ANNs 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 ?
Uhh yeah right.
Re: Cracking Random Number Generators Using Machine Learning
#6ANNs 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 ?
I 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.
Would it be called pseudorandom if it had an undecipherable internal state such as temperature or sth? aren't all PRNGs deterministic functions by definition?
Re: Cracking Random Number Generators Using Machine Learning
#7ANNs 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 ?
Uhh yeah right.
cblconfederate happens to be right in this specific case (although wrong about using neural nets for predicting PRNGs in general): the author uses four consecutive non-truncated outputs of the xorshift128 generator as the network input, and learn to predict the next output. Since four consecutive outputs expose the entire internal state of the xorshift128 generator, this amounts to little more than approximating a (very simple) four-variable function.
Re: Cracking Random Number Generators Using Machine Learning
#8ANNs 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 ?
1. For many functions ANNs will never converge to an approximation of that function given only (input, output) tuples, even if the function is simple enough that the ANN could represent it. Chaotic functions rarely have a useful gradient the NN can follow.
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.
Re: Cracking Random Number Generators Using Machine Learning
#9Earlier quoted context omitted.
I 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.
Would it be called pseudorandom if it had an undecipherable internal state such as temperature or sth? aren't all PRNGs deterministic functions by definition?
For 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.
Re: Cracking Random Number Generators Using Machine Learning
#10Earlier quoted context omitted.
I 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.
Would it be called pseudorandom if it had an undecipherable internal state such as temperature or sth? aren't all PRNGs deterministic functions by definition?
Generally, PRNGs have an internal state, a transition function that determines a new internal state based on the current internal state, and an output function that determines the output value based on the current internal state.
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.