40
$\begingroup$

What is the difference between CSPRNG and PRNG?

Is there performance differential between them? For example: We use PRNG for key generation which is very expensive and CSPRNG for IV/nonce in block ciphers which is fast?

What is the difference between the two types of RNGs?

$\endgroup$
10
  • 4
    $\begingroup$ Since a CSPRNG will also be a PRNG, if your choice of CSPRNG is faster than your choice of PRNG you might as well swap and use the CSPRNG for both (which you almost certainly should be anyway) $\endgroup$ Dec 18, 2013 at 17:06
  • 2
    $\begingroup$ What research have you done? After all, Wikipedia's "Cryptographically secure pseudorandom number generator" and "Pseudorandom number generator" already provide a pretty good insight into the difference between them two. $\endgroup$
    – e-sushi
    Dec 18, 2013 at 17:07
  • 2
    $\begingroup$ PRNG encompasses all pseudo random number generators, from the horrible rand call in c, over suitable for simulations but not security ones like the mersenne twister, to the most secure cryptographic PRNG. CSPRNGs are simply the subset of PRNGs which are secure. Every stream cipher, including AES-CTR can act as CSPRNG. Depending on the context, one might also include the proper seeding in the scope, which is far more complex than the actual data generation. $\endgroup$ Dec 18, 2013 at 18:42
  • 2
    $\begingroup$ @cpast, I don't think that question (or the answer there) will help people with the confusion that my question is intended to get at. For instance, think of a typical reader who sees some awesome statistical PRNG (say, Mersenne twister) and thinks, hey, I bet I could use this for cryptography! I don't think the answer there is going to help them understand why that's a bad idea, and I don't think the question there will be meaningful to them. The question there also is a bit confused/unclear (a PRNG for key generation? no -- we use a CSPRNG for that). I think this is a better formulation. $\endgroup$
    – D.W.
    Jan 6, 2015 at 0:24
  • 1
    $\begingroup$ While I understand your general motivation, I have to agree with @cpast’s comment. Your question indeed boils down to a reformulation of an existing, one-year-old question. This is underlined by the answer Thomas Pornin provided, which perfectly explains the difference between statistical PRNG and cryptographic PRNG. From my point of view, that pretty much voids your “formulation” argument. $\endgroup$
    – e-sushi
    Jan 6, 2015 at 4:17

5 Answers 5

50
$\begingroup$

"PRNG" means "Pseudorandom Number Generator" which means that a sequence of numbers (bits, bytes...) is produced from an algorithm which looks random, but is in fact deterministic (the sequence is generated from some unknown internal state), hence pseudorandom.

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.

For instance, consider the following generator:

  • There is an internal state s which is a sequence of 20 bytes.
  • The generator produces a long sequence of bytes by 20-byte chunks.
  • To produce the next chunk, the algorithm is: output s, then set s to SHA-1(s).

This PRNG will be very good statistically, but it is trivial to distinguish from true randomness: just take two consecutive 20-byte chunks in the output, and see if the second is the result of SHA-1 over the first. This is not a cryptographically secure PRNG.

Of course, every CSPRNG is a PRNG, but not every PRNG is a CSPRNG. Some non-CS PRNG like Xoshiro can achieve quite high a performance and be adequate in non-cryptographic situations where there is no intelligent attacker to defeat (e.g. physics simulations). Although there also are some known high-performance CSPRNG (e.g. these stream ciphers), a non-CS PRNG may give an edge in contexts where the lack of cryptographic security is not an issue.

$\endgroup$
4
  • $\begingroup$ so for CSPRNG we just process a seed with stream ciphers? where this seed come from? a PRNG?? (my question is more about implementation, what we have to do in code for security? i mean what is best secure way to ask a lib to give us a robust RN to process it with CSPRNG?) $\endgroup$
    – randomness
    Dec 18, 2013 at 20:33
  • $\begingroup$ Sadly we actually had two separate questions suggesting your trivially broken example as a secure stream cipher. A simple block cipher based on the SHA-256 hash function and Is it feasible to build a stream cipher from a cryptographic hash function? $\endgroup$ Dec 18, 2013 at 20:45
  • $\begingroup$ just asking how to seed CSPRNG? a cipher can't generate random stat so we have to generate a seed first, where this seed come from and what we name it? $\endgroup$
    – randomness
    Dec 18, 2013 at 20:54
  • 3
    $\begingroup$ Initial seed for a CSPRNG must come from something "which the attacker cannot know". Usually, this is "true randomness" extracted from hardware event. Typically, the system takes the time (down to the nanosecond, using the CPU cycle counter) at which hardware interrupts occurs, concatenates all these time values, and hashes the lot. Something similar occurs in the CSPRNG provided by usual operating systems (/dev/urandom on Linux, CryptGenRandom() on Windows...). $\endgroup$ Dec 18, 2013 at 20:58
19
$\begingroup$

The key element in the definition of a PRG is the observer (aka distinguisher, algorithm, test, etc) that the PRG is supposed to fool.

A statistical PRG fools a specific set of observers, whereas a cryptographic PRG fools all efficient observers.

This strong definition is essential for cryptography::

The only assumption the designer should make about the adversary is its computational ability, but not its strategy.

In contrast, if you used a statistical PRG in cryptography, you might face a clever attacker employing an unanticipated new strategy that is not in the specific set of strategies the statistical PRG is supposed to fool, rendering the scheme insecure. If a statistical test withstood attacks for (say) $5$ years, it just means the attacker has not yet figured it out. But you never know about tomorrow!

$\endgroup$
1
  • 1
    $\begingroup$ What does "strategy" mean then? $\endgroup$
    – Pacerier
    Feb 17, 2018 at 20:37
15
$\begingroup$

The key difference between the two is that a random number generator used for cryptographic purposes has to stand up to an attacker.

When you use random numbers in statistics, the main thing you care about is that the output sequence "looks random." What that means in practice is that it passes a bunch of statistical tests, showing that the distribution of the numbers it produces is what you'd expect from truly random numbers. All you care about in statistics is the sequence you get from the generator, and whether it's distributed like random numbers are.

A cryptographic PRNG has a different goal: it must satisfy all the statistical randomness tests a statistical PRNG does, but it also needs to be unpredictable. A CSPRNG is designed to resist attempts by a human attacker to predict its next output; it should be hard to tell it from a truly random sequence even if the attacker knows the algorithm used to make it. For instance, if an attacker sees the result of many invocations, it needs to still be hard to predict the result of any future invocation -- for statistics that's not such a big problem (it introduces some bias, but it's not a big deal), but in cryptography you were often using that random number generator precisely so that no one would know what the result was. Naturally, this also means you need to inject true randomness into the process somewhere.

For an example: A good PRNG with a fixed seed is fine for statistics, but utterly awful for cryptography (where the attacker is assumed to be able to learn the seed).

$\endgroup$
11
$\begingroup$
  • A statistical PRNG is designed not to exhibit any statistical abnormalities. That is, an "adversary" who applies statistical analysis to the generated output should not be able to see a significant difference to the properties one expects from a uniformly distributed random source.

    For performance reasons, most statistical PRNGs are based on simple recurrences that are easily recognized in the output stream (if one applies specific knowledge about the algorithm, which is why this doesn't violate the requirement of statistical indistinguishability). In many cases, this leads to a compromise of the generator's internal state at the same time, effectively enabling an attacker to predict any future output. Should someone have the idea to use a statistical PRNG as a stream cipher, this is the reason not to do it.

  • On the other hand, a cryptographic PRNG is required to avoid any kind of detectable regularities, such that it will withstand cryptanalysis using full knowledge of the algorithm. The most important property of a cryptographically secure PRNG is thus

    Indistinguishability. An attacker who applies any probabilistic polynomial-time algorithm to (a) the PRNG's output when initialized with a random seed, or (b) output from a real random source, must not be able to tell these two cases apart except for negligible probability.

    A seemingly different notion of security, which turns out to be equivalent, is

    Unpredictability. Given a sequence of pseudorandom bits from the generator when initialized with a random seed, an attacker using a probabilistic polynomial-time algorithm must not be able to predict the next bit with probability non-negligibly greater than $1/2$.

    From this, it becomes clear that, in contrast to statistical PRNGs, a cryptographic PRNG must never expose the internal state: otherwise, an attacker can just use (a copy of) the generator on the leaked state and thus gain knowledge of the next bit (and all following bits) with absolute certainty. This immediately disqualifies the most widely-used statistical PRNGs: linear congruential generators, linear feedback shift registers, and generalized feedback shift registers like the Mersenne twister; all of whose output essentially is the internal state.

It is particularly unpredictability that shows why it is important to use a cryptographic PRNG: most cryptographic protocols which make use of randomness assume that an attacker is unable to gain knowledge of (pseudo)randomly generated nonces, IVs, keys, and the like, even when they have observed previous (pseudo)random values from the same source. Protocols tend to break horribly when this is not the case.

$\endgroup$
1
  • 1
    $\begingroup$ Re "any probabilistic polynomial-time algorithm"; examples? $\endgroup$
    – Pacerier
    Feb 17, 2018 at 20:41
2
$\begingroup$

Only for the sake of simplicity: a good statistical PRNG can have no explicit seed or a very small seed space (e.g.16 bit). This is clearly not enough for crytographic purposes. The key point is that statistical PRNG doesnt need to be unpredictable, crypto PRNGs need it

$\endgroup$
3
  • 1
    $\begingroup$ Actually, a statistical PRG is unpredictable, but only to a set of distinguishers. A cryptographic PRG is unpredictable to all efficient distinguishers. $\endgroup$
    – epsfooling
    Jan 12, 2015 at 18:15
  • $\begingroup$ @epsfooling, Re "is unpredictable, but only to a set of distinguishers"; But does it need to be? I'd thought that once it passes x number of statistics tests its OK even if its not unpredictable. $\endgroup$
    – Pacerier
    Feb 17, 2018 at 20:46
  • 1
    $\begingroup$ Just for clarification, good statistical PRNGs often use longer seeds. The popular MT19937 version of the Mersenne Twister uses a 32-bit seed (to some other generator) in order to generate the MT's internal 19968-bit seed that consists of 624 32-bit numbers. In theory, you could instead provide your own set of 624 32-bit numbers as a seed for MT19937, bypassing the initialization step. $\endgroup$
    – Mars
    Jun 10, 2019 at 15:51

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