3
$\begingroup$

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?

$\endgroup$
5
  • 3
    $\begingroup$ In theory, it would seem there would be an infinite number of seeds that can result in the same sequence of random numbers. The reason being that there is an infinite number of seeds, but the internal state of any DRBG is finite, thus multiple seeds must result in the same state. Now finding any two seeds that generate the same state should be very difficult. It's very much like finding hash collisions. There's an infinite number of inputs that can generate a particular hash output, but finding two that generate the same output should be very difficult. $\endgroup$ Mar 31 '20 at 3:51
  • $\begingroup$ @Swashbuckler It really depends on your definition of "seed" esp. if you take it to be synonymous with "initial state" or not - doesn't it? I vaguely recall that some CSPRNGs make the distinction sharper with a process to update the internal state rather then setting it. But with something like AES-CTR any distinction would be outside the definition. $\endgroup$
    – bmm6o
    Apr 30 '20 at 16:45
  • $\begingroup$ Two very important properties should be accomplished by a CSPRNG: $\endgroup$
    – Maf
    May 19 '20 at 21:03
  • $\begingroup$ 1. The next bit test: states that given a sequence of m bits generated from a generator, no feasible method can predict the (m + 1)th bit with probability significantly higher than one half. $\endgroup$
    – Maf
    May 19 '20 at 21:03
  • $\begingroup$ 2. Malicious seeding resistance: even if an attack(er) 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$
    – Maf
    May 19 '20 at 21:03
0
$\begingroup$

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:

  1. The next bit test: states that given a sequence of m bits generated from a generator, no feasible method can predict the (m + 1)th bit with probability significantly higher than one half.

  2. Malicious seeding resistance: even if an attack(er) 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.

Nevertheless, when you're going to use a CSPRNG, ensure all the seeds are as much real random as possible (eg., devrandom).

$\endgroup$
5
  • $\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 '20 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 '20 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$
    – Maf
    May 19 '20 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)th bit 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$
    – Maf
    May 19 '20 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$
    – Maf
    May 19 '20 at 20:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.