0
$\begingroup$

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?

$\endgroup$
8
  • $\begingroup$ Why would you say that [1, 2, 3, 4, 5] is not random? Can you prove it? $\endgroup$
    – hunter
    Commented Jul 25, 2022 at 8:25
  • 2
    $\begingroup$ By definition, elements from the set from which you choose aren't random. If they have been chosen using a random method is something else. If that is the case then either element should have the same likelihood to be chosen, and therefore [1, 2, 3, 4, 5] could be said to be just as "random" as [1, 81, 44, 1, 9, 2] (although one has 5 elements and the other 6, I suppose that's an error on your side). $\endgroup$
    – Maarten Bodewes
    Commented Jul 25, 2022 at 8:32
  • $\begingroup$ @MaartenBodewes But wouldn't the set [1, 2, 3, 4, 5] fail on the randomness test and therefor not be a PRNG? And yes, the sets are different in length, it was merely a demonstration set. You could also assume the first set would be [1, 2, 3, 4, 5, 6] $\endgroup$
    – Bram
    Commented Jul 25, 2022 at 9:33
  • 1
    $\begingroup$ Hmm, I should have been talking about a list instead of a set. I'll change that later on. But yes, it might well fail a randomness test (although those require a lot more data, and for good reason). But the fact remains that such a list is just an example, and it is just as likely as any other specific list. $\endgroup$
    – Maarten Bodewes
    Commented Jul 25, 2022 at 9:50
  • $\begingroup$ Maybe I'm being pedantic, but when you say "unique", do you mean "contains no duplicates"? $\endgroup$
    – bmm6o
    Commented Aug 24, 2022 at 15:59

2 Answers 2

0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Can you elaborate more on the theory of just the CSPRNG. I understand that a stream cipher might be used to create the RNG, but so can a hash or mac. I too believe that an RNG won't output unique data, but is there mathematical proof of that, that's what I'm after. You mention the DRBG, and I understand that by only having the ability to generate 0's or 1's you're guaranteed to have collisions if the set is not large enough, but how does that hold when I use that to create larger amounts of data? What's the maths behind it to support this and does every CS(P)RNG use a DRBG as well? $\endgroup$
    – Bram
    Commented Jul 25, 2022 at 12:28
  • $\begingroup$ I'm saying that a stream cipher can be thought of as being a CSPRNG, not as a building block of one. A hash or MAC isn't really a CSPRNG by themselves as they are constrained regarding the output that they produce. Of course, the stream cipher is generally constrained to a certain seed size as well and it doesn't support re-seeding, hence it is not a DRBG as defined by NIST. $\endgroup$
    – Maarten Bodewes
    Commented Jul 25, 2022 at 13:27
  • $\begingroup$ As for a mathematical proof: you cannot do that without specifying the algorithm itself. However, if the CSPRNG is defined to have randomized output then the property is directly implied from that. A DRBG is just a different wording and definition of a CSPRNG; it's not a building block for a CSPRNG. $\endgroup$
    – Maarten Bodewes
    Commented Jul 25, 2022 at 13:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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