CS(P)RNG uniqueness

Question

I recently read a StackOverflow post about a CS(P)RNG generating sixteen bytes of random data. The OP wanted this data to be random and unique. One of the answers said that uniqueness and randomness are mutually exclusive when talking about a CS(P)RNG. I commented on that matter with the following example:

The list [1, 2, 3, 4, 5] is unique, but we can hardly call it random. Additionally, given a theoretical random source, we could generate a list of [1, 81, 44, 1, 9, 2]. This might be random, but is not unique.

I concluded that therefor randomness and uniqueness are not mutually exclusive. I was commented on that I was likely correct for random number generators, but that the CS(P)RNG does exclude randomness, but I can't find it does anywhere.

I do understand that the uniqueness and randomness of course have to deal with the amount of generated data (in this sceneario sixteen bytes) and the generated set. But my question is more related to the terminology or definition of the CS(P)RNG. So, is the output of a CS(P)RNG unique?

Answer 1

What is a CSPRNG? Fundamentally, it's an algorithm that can be initialized with some kind of seed, and can be repeatedly invoked to return values. These values are in a range defined by the generator, usually $[0, n = 2^k)$ for some $k$. The definition of random that is used to evaluate such a generator is if the output is distinguishable from a series of independent values drawn from a uniform distribution on the range. Right away, you can see that the requirement means that it must be possible to produce duplicate values.

Random number generators themselves are just a tool, and some applications might have a need for random numbers without duplicates. This can come up any time you need to select without replacement, such as in a card game. The RNG typically exposes a function like int Next(int low, int high) which takes whatever range the RNG "natively" produces and adapts to your requested range (hopefully without introducing bias). If you work it out right, you don't really need to avoid duplicates, you just need to shrink your range each time. See for instance Fisher-Yates shuffling.

Another common way to produce random numbers without duplicates is entirely different. You use a PRP like a block cipher, and encrypt a counter.

Answer 2

So, is the output of a CS(P)RNG unique?

Generally no.

---

First of all, if you take the definition of a CSPRNG here you will see that a stream cipher is something different than a DRBG as specified by NIST. If you would take any of the NIST defined RNG's then you would expect to get well distributed bits, assuming that the CSPRNG is seeded correctly of course.

Some people will also say that a stream cipher is a CSPRNG. In that case they will argue that a stream cipher would fit in all the definitions of a CSPRNG. This is getting a bit tricky, as it then comes down to how the CSPRNG is defined in the first place. As far as I know there isn't a widely accepted definition for it.

Stream ciphers can be constructed using or in similar fashion as counter mode (of operation) on a block cipher. In that case you would not expect repetition in the blocks that are encrypted. However, with blocks of 128 bits (for e.g. AES-CTR) you would not expect much repetition anyway, even if those 128 bits would be generated using a DRBG, simply because the chance of collision is pretty low.

If you are going to request 128 bits then I would strongly recommend a DRBG if you need true randomness. If you're going to generate a lot of random values you might want to keep an ordered set of previously generated values.

---

Of course, to see that a CSPRNG would normally repeat, you'd just have to think of the set made by a single bit $\{0, 1\}$. Obviously that set will "repeat" after two outputs at most.