1
$\begingroup$

I understand that PRNG are Random Number Generators that uses a deterministic algorithm based off of a seed.

I also understand that CSRNG are PRNG that are cryptographic-ally safe to use for generating random numbers.

And by cryptographic-ally safe, I believe this means that even if an attacker knows the deterministic algorithm and the seed, they would not be able to predict the next random number. I understand this is due to CSRNG also making use of some internal states.

If there are any errors in the above, I will appreciate a clarification because my questions depends on them being accurate.

So my main question is, when do you need a PRNG? and when must you use a CSPRNG?

My initial answer to that was that CSPRNG should be used when generating keys, but when I searched for "what are prng used for", one of the pages I found was this which states that:

In cryptography, PRNG’s are used to construct session keys and stream ciphers

Which leaves me a bit confused, why should PRNG, that is not cryptographically strong be that is used for keys? I would expect CSPRNG to be used instead.

This makes me realise that perhaps I do not fully understand PRNG's and CSPRNG's yet and how they are used. Hence this question: In Cryptography, When exactly are PRNG used and when are CSPRNG used?

$\endgroup$
6
  • $\begingroup$ in one of the links, the question states that "We use PRNG for key generation" is that true? Are PRNG used for key generation? or is it CSPRNG that is used? $\endgroup$ Nov 15 '21 at 11:11
  • $\begingroup$ I have looked at both links and I am not sure they answer my core question: In Cryptography, When exactly are PRNG used and when are CSPRNG used? $\endgroup$ Nov 15 '21 at 11:13
  • 1
    $\begingroup$ Such pseudorandomness can be cryptographically secure, or not. It is cryptographically secure if nobody can reliably distinguish the output from true randomness, even if the PRNG algorithm is perfectly known (but not its internal state). A non-cryptographically secure PRNG would fool basic statistical tests but can be distinguished from true randomness by an intelligent attacker. $\endgroup$
    – kelalaka
    Nov 15 '21 at 12:27
  • 2
    $\begingroup$ Not covered by the other answers: "And by cryptographic-ally safe, I believe this means that even if an attacker knows the deterministic algorithm and the seed, they would not be able to predict the next random number. I understand this is due to CSRNG also making use of some internal states." This is incorrect, a PRNG is an algorithm and thus deterministic. If you know or can guess the seeds (and when they are mixed into the state) then you'd be able to calculate the inner state and all output. In other words: the seed are the source of entropy to the PRNG. $\endgroup$
    – Maarten Bodewes
    Nov 15 '21 at 22:29
2
$\begingroup$

First, some definitions:

  • A PRNG is a pseudo-random number generator. It can be a very poor one, or one with very strong mathematical properties. It does not matter for this definition.
  • A CSPRNG is a cryptographically secure PRNG. It is a PRNG, with some strong requirements.

In your link, the author is writing about CSPRNGs, but calling them PRNGs. The "cryptographically secure" element is implied by this requirement:

The generated bit strings should "look random" to an adversary.

Indeed, CSPRNG are required when the output of the PRNG must be indistinguishable from perfectly uniform randomness (this implies the output to be unpredictable). This is required by some cryptographic algorithms.

Most CSPRNG provided by operating systems will update their internal state from random input, so that even if the seed or the inner state leak at some point, it will automatically correct itself to a secured state. But this is not a requirement for a CSPRNG. Some CSPRNG provided by cryptographic libraries do not update their state automatically, while others do.

CSPRNG can always be used instead of PRNG when there is no need to be able to generate the same output twice. For example, when generating video game levels from a seed, or when fuzzing, it is important to be able to reproduce the output. In those case, a PRNG should be used, or a CSPRNG which does not automatically update its inner state from other sources than its initial seed. A stream cipher could also be used, but a simple PRNG might be more than enough and more efficient, depending on the requirements.

To directly answer your questions: you must use a CSPRNG when it is specified by the cryptographic algorithm (which is often the case). And you must use a PRNG or a CSPRNG which does not automatically update its inner state when reproducing its output is needed. For the other cases, most of the time which kind of RNG you use does not matter.

Also, if you somehow need a reproducible output that is indistinguishable from perfectly uniform randomness, then you need a stream cipher, not a PRNG.

$\endgroup$
5
  • $\begingroup$ @fgrieu That's not exactly what I wrote. Nevertheless, I modified my answer to be clearer. About TRNGs, In my answer I do not distinguish PRNGs from their seeding, but from the updating (or lack of it) of their inner state after they are seeded, as done by OpenSSL or /dev/urandom on Linux. Since there is ambiguity on the meaning of "true" in TRNG (depending on who is talking), I never use this term. $\endgroup$
    – A. Hersean
    Nov 15 '21 at 17:20
  • $\begingroup$ I would not call /dev/urandom a CSPRNG or a PRNG. To me, a PRNG is deterministic (that's implied by the Pseudo), and a CSPRNG becomes unpredictable only when combined with an appropriate entropy source, making it a CSRNG, standing for Cryptographically Secure (True, typically left implied rather than stated) Random Number Generator. Not all CSRNGs include a CSPRNG: it is common to make a Cryptographically Secure True RNG out of a good seed with a good online test and a non cryptographically secure PRNG, e.g. a basic LFSR with some decimation. $\endgroup$
    – fgrieu
    Nov 15 '21 at 17:45
  • $\begingroup$ @fgrieu If I understood correctly your definition, a Mersenne twister (MT19937) seeded from /dev/urandom becomes a CSRNG. But the output of this RNG can be predicted from the observation of 624 iterations. For me (and Wikipedia), this cannot be CS, and it conflicts with your stated requirement of unpredictability for CSRNG. Since you are more experienced than me, I feel like I'm missing something. Could you enlighten me? $\endgroup$
    – A. Hersean
    Nov 15 '21 at 18:00
  • $\begingroup$ @fgrieu Is that you consider MT19937 seeded secretly an unpredictably a CSRNG under the condition that at most 64x624 bits are generated? While similar conditions are implied for every RNG whose inner state depends only on a seed, I think it is abusive here to call MT19937 a CSRNG. Side note: personally, I use "pseudo" when the bits are generated by an algorithm, so I do not make your distinction between CSPRNG and CSRNG. I would reserve the lack of "pseudo" (or the use of "true") to imaginary perfect hardware RNG, and I prefer HRNG for real (biased) hardware generators. $\endgroup$
    – A. Hersean
    Nov 15 '21 at 18:12
  • $\begingroup$ Using "pseudo" whenever an algorithm is involved is not unseen, and I would agree calling /dev/urandom a Pseudo-TRNG or stating that it uses a (CS)PRNG; but not that it is a (CS)PRNG, which has a precise definition in modern crypto. Indeed MT19937 not cryptographically secure when used like you describe, and thus not a CSRNG when used alone. My statement was about LFSRs (e.g. in scrambler mode) fed with an entropy source, and most importantly with decimation (leaving sizably less output than input). $\endgroup$
    – fgrieu
    Nov 15 '21 at 18:45
1
$\begingroup$

It's actually pretty simple.

P. Random number generators produce random looking numbers (see below). Sometimes all that is expected is that the numbers are computationally indistinguishable from random looking (PRNG). If you can predict the next number algorithmically, it doesn't matter. For example, Monte Carlo experiments. The Mersenne Twister is pretty good and probably the most used PRNG in the world (it's inside Python), yet completely predictable after observing ~624 outputs. Therefore useless for hiding secrets.

C. A CSPRNG is an upgraded PRNG in that you cannot predict the next number. It's called the next bit test, i.e. you cannot predict the next output bit no matter what observations you undertake (not knowing the hidden internal state). So:-

$$ P(x_{i} = 1) = \frac{1}{2} + \epsilon $$

where the bias from evens is (typically) $< 2^{-64}$. If you then make assumptions about the first part of a cipher text, it won't help with the next part and you end up nowhere. Which is what we want to hide secrets. An example is Salsa20 as part of a stream cipher.

In cryptography, PRNG’s are used to construct session keys and stream ciphers

Is just sloppy talk. I call all of them RNGs unless a narrower definition is required.


  1. Nuance: a PRNG can generate numbers with all sorts of wacky distributions useful for science and that stuff. In cryptography, we generate uniform distributions in order to mask our messages.

  2. Have a look at https://en.m.wikipedia.org/wiki/List_of_random_number_generators.

  3. Also note the existence of TRNGs, which are a blend of the above and hardware.

$\endgroup$
8
  • $\begingroup$ I (as usual) object to calling HWRNGs TRNGs. There's nothing any more "true" about them than any CSPRNG. This is a metaphysical objection: the laws of physics are consistent with an entirely deterministic universe, so there's no reason to assume that there's some hidden entropy source allowing for total nondeterminism instead of just mathematical Chaos resulting in it being impossible to predict future events. Not really a practical difference, but calling them TRNGs can give people mistaken ideas about how entropy works. $\endgroup$ Nov 15 '21 at 15:21
  • $\begingroup$ @SAIPeregrinus Oh dear - you've set me off ;-) Bait swallowed and digested. Have you washed today? Not a personal criticism, but science. The water goes round and around down the plug hole. In fluid dynamics it’s called turbulent (non laminar) flow. Whilst it goes clockwise (in the North), it does so with a certain randomness don’t you think? The waves, the curves e.t.c. An unpredictable pattern? Yet in stays in the sink. Bar poor plumbing, it doesn’t flood next door’s attic. This proves that the indeterminate micro and the predictable macro can co-exist without the Universe exploding. $\endgroup$
    – Paul Uszak
    Nov 15 '21 at 16:02
  • $\begingroup$ See my page for a more technical explanation of quantum indeterminacy and why TRNGs do indeed exist. Also consider that CSPRNGs are entirely deterministic, predicable by someone, of finite output and have ~zero Kolmogorov complexity. Thus by loads, CSPRNGs $\ne$ TRNGs. And then there’s the one time pad stuff. Or do those not exist either..? $\endgroup$
    – Paul Uszak
    Nov 15 '21 at 16:02
  • $\begingroup$ But I don't understand your last "entropy" sentence. $\endgroup$
    – Paul Uszak
    Nov 15 '21 at 16:03
  • $\begingroup$ You believe that Quantum Mechanics is non-deterministic. I don't: assuming non-determinism isn't necessary for the math to work out. So I'm making the distinction between "true" random processes and those which are merely chaotic. There's no way to tell the difference from the output, so it's a metaphysical question. Just like it's impossible to actually run the "next bit test" in the physical universe. $\endgroup$ Nov 15 '21 at 19:21

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.