1
$\begingroup$

In general, is it possible that two different seeds produce the same output from a PRNG? I'm not sure how many different types of PRNGs there are and maybe it depends on which one we consider. I know that an identical seed produces and identical output, but can different seeds stumble upon the same output (seed collisions)?

$\endgroup$
  • 4
    $\begingroup$ Yes. A PRNG isn't guaranteed to be a permutation, so collisions in the output are possible. $\endgroup$ – Melab Jan 15 '18 at 21:51
  • $\begingroup$ Imagine a PRNG that takes a 128-bit seed, hashes it using SHA-1, then uses 56-bits of it as a key for DES in CTR mode. I hope nobody would ever use it, but it is a good example of one where many seeds would produce the same output $\endgroup$ – Richie Frame Jan 16 '18 at 2:28
  • $\begingroup$ Here's an example: the TEA block cipher suffers from equivalent keys—every key is equivalent to three others. So if you used TEA in counter mode as a PRNG, with the key as the seed, then correspondingly you have multiple seeds that produce the same output. $\endgroup$ – Luis Casillas Jan 16 '18 at 2:39
3
$\begingroup$

Well, yes, but the output should be limited by chance. It's kind of obvious that repetition is possible if you just consider a single bit of output. However, when you request more bits then the chance that the bits are equal should become less.

The seed or seeds are an entropy source for the PRNG. The PRNG should not disregard any bits that contain entropy, so the seed should be integrated into the state of the PRNG. A cryptographically secure PRNG should have quite a large state; the chance that a seed recreates a previously known state should be computationally impossible. The output is created using this state, and the output should therefore be random given a specific seed. So if the output is identical then it is by chance alone.

PRNG's are often constructed from secure hash functions. Getting collisions from output created by a secure hash is a computationally hard problem.


The output of stream ciphers using the same seed / key may not be able to repeat at all, for any amount of data that contains a full block. For instance counter mode encryption will never repeat the same block.

This is inconsequential for any block cipher with a block size of 128 bits or higher, as the likelihood of generating a repeating block by chance is also quite low, even if bounded by the birthday problem.

If a stream cipher has equivalent keys then the key stream may of course repeat if one of the seeds results in equivalent keys being used (as indicated by the comments below the question). Those stream ciphers however should not be considered secure PRNG's.

Note that stream ciphers usually lack procedures for e.g. adding seed material (re-seeding) to the state or extracting the entropy. A stream cipher doesn't fully comply with the interface for DRBG's as stated in NIST SP-800 90Ar1 although they are normally thought of to be PRNG's.

| improve this answer | |
$\endgroup$

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.