Are there conditions on the definition of cryptographically secure pseudo random number generators that require distinct seeds to generate distinct (periodic) sequences? What if a generator has the property that two distinct seeds generate the same sequence, but the generator is provably secure? Can this property be ignored then or is it a requirement that distinct seeds generate distinct pseudo random sequences?
$\begingroup$
$\endgroup$
5
1 Answer
$\begingroup$
$\endgroup$
5
For a CSPRNG, finding two seeds that generate the same sequence should be difficult as finding two strings with the same hash. Similarly if someone can find these two strings, then this CSPRNG must be deprecated, cause the entropy should be so large enough so that the probability of finding this "collision" is negligible.
Two very important properties should be accomplished by a CSPRNG:
The next bit test: states that given a sequence of m bits generated from a generator, no feasible method can predict the
(m + 1)thbit with probability significantly higher than one half.Malicious seeding resistance: even if an attack(er) can gain full or partial control of the inputs to the
CSPRNGfor a period (time), it is still unfeasible to predict or reproduce any random output from theCSPRNG.
Nevertheless, when you're going to use a CSPRNG, ensure all the seeds are as much real random as possible (eg., devrandom).
-
$\begingroup$ That's not a property that I've seen noted to be a required for a CSPRNG by anyone else. It should not be assumed that you can pass arbitrary seed material to CSPRNGs in general. Pseudo-Random things (PRPs, PRFs) assume a key sampled from a uniform distribution. No security guarantees are claimed for biased keys. Individual algorithms may permit it (providing a security level up to the entropy of the non-uniform distribution) but read the "user manual" before using an algorithm you're not familiar with. $\endgroup$ May 2, 2020 at 0:27
-
$\begingroup$ If you need the CSPRNG version of collision resistance, use an eXtendable Output Function, use an algorithm that explicitly supports arbitrary seed material, or pre-hash seed material. (For pre-hashing to work you need an algorithm with a keyspace large enough to account for the birthday problem. But that's probably a good idea for every algorithm.) $\endgroup$ May 2, 2020 at 0:35
-
$\begingroup$ According to Rose et. all (2011), a CSPRNG is seeded with unpredictable inputs in a secure way so that it is unfeasible to distinguish its output from a sequence of random bits. As defined herein, a CSPRNG has all properties of a normal PRNG, and, in addition, at least two other properties. $\endgroup$– MafMay 19, 2020 at 20:44
-
$\begingroup$ One of these properties, referred to as the next bit test, states that given a sequence of m bits generated from a generator, no feasible method can predict the
(m + 1)thbit with probability significantly higher than one half. The second property, referred to a malicious seeding resistance, states that even if an attack can gain full or partial control of the inputs to the CSPRNG for a period (time), it is still unfeasible to predict or reproduce any random output from the CSPRNG. $\endgroup$– MafMay 19, 2020 at 20:45 -
$\begingroup$ Kindly read the following: Gregory Gordon Rose, Alexander Gantman, and Lu Xiao. Cryptographically secure pseudo-random number generator, September 13 2011. US Patent 8,019,802. $\endgroup$– MafMay 19, 2020 at 20:45
(m + 1)thbit with probability significantly higher than one half. $\endgroup$CSPRNGfor a period (time), it is still unfeasible to predict or reproduce any random output from theCSPRNG. $\endgroup$