5 ms·
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 t
by adrian_b 5y ago
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.
- deleted 5y ago[deleted]
- joshuaissac 5y agoThere are CSPRNGs like Fortuna that contain an entropy accumulator, so even if the secret part of the state is compromised, it can recover.
- adrian_b 5y agoTrue, but they belong to a different class, which are used for applications like key generation, where there is no need to ever reproduce a certain output sequence. 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.
- rurban 5y agoWrong as we can see with x64's new rdrand which relies on a fast aesna, but is terribly broken.