20
$\begingroup$

In most programming languages, there is a module or function in the stdlib for creating random output like random.random() in Python.

Because those functions use a normal PRNG that is not cryptographically secure, over all the years those generators have been used for crypto nonetheless because of the name "random".

Why do not programming languages use only cryptographically secure PRNGs in the stdlib? It's able to produce random output even if not needed for crypto and it's secure if you use crypto.

Is there an advantage of normal PRNGs compared to CSPRNGs? I'd be happy if you could explain it in a way that someone like me without any crypto background can understand, thanks a lot! :)

$\endgroup$
  • 2
    $\begingroup$ This is a better question for the authors of the programming language's standard libraries than for crypto.se. My opinion is that if something goes anywhere near the word ‘random number generator’, then by default it should be a crypotgraphic thing, and anyone aiming to replace it by garbage like the Mersenne twister should have an extremely strong empirically grounded and thoughtful justification for failing to provide cryptographic security. $\endgroup$ – Squeamish Ossifrage Jun 29 '18 at 20:49
  • 1
    $\begingroup$ ‘Why don't guns for amateurs have safety features? Why do those appear only on professionals' guns? Is there an advantage to being shot in the foot?’ $\endgroup$ – Squeamish Ossifrage Jun 29 '18 at 20:53
  • 1
    $\begingroup$ @SqueamishOssifrage What does your gun comment mean please? And what's an amateur's gun? $\endgroup$ – Paul Uszak Jun 29 '18 at 20:58
  • 1
    $\begingroup$ @SqueamishOssifrage Target handguns, like those used at the Olympics, usually do not have manual safeties, or features to prevent the gun from being fired when being dropped, unlike guns made for daily carry (police). This is because they are used in carefully controlled conditions, and such safety features interfere with shooting precision. Right tool for the right job. $\endgroup$ – user71659 Jun 30 '18 at 1:38
  • 1
    $\begingroup$ I would hate it if the bytecode generated by SDCC for a simple 8051 microprocessor needed to go through the effort of generating cryptographically secure random numbers when even LCG is overkill. $\endgroup$ – forest Jun 30 '18 at 6:01
30
$\begingroup$

First, insecure PRNGs are typically faster than CSPRNGs. CSPRNGs based on /dev/urandom (if you're familiar with Linux), for example, have to call the crypto kernel module driver every time. For reference:

the BearSSL implementation of ChaCha20, which can be used as a CSPRNG, on an Intel Xeon CPU at 3.10 GHz, reaches 270.72 MB/s;

an implementation of a Mersenne Twister, which is a typical PRNG, on an Intel Xeon 5160 at 3 GHz, reaches 113.4*32/8=453.6 MB/s;

there are even faster algorithms/implementations. For example, the rand() function in the GNU Scientific Library, according to the same paper, reaches 227.8*32/8=911.2 MB/s. Xorwow, which belongs to the Xorshift PRNG family, reaches 1388.4 MB/s.

Second, writing cryptographic software, including CSPRNGs, is much more complex than writing general-purpose software.

There are also historical reasons. At least until the 1990s, developers, including some developers working on standardizing new programming languages, were afraid to deal with cryptographic algorithms, because the export restrictions on cryptography were severe and not entirely understood by them. Quoting one such developer:

I would not have even considered putting crypto strength randomness into anything that shipped with the browser without getting a huge amount of legal advice from the MSLegal team. I didn't want to touch crypto with a ten foot pole in a world where shipping code was considered exporting munitions to enemies of the state. This sounds crazy from today's perspective, but that was the world that was.

What about more recent programming languages, such as Python?

Some people argue that baking CSPRNGs into programming languages by default would lead to a false sense of security, especially as new flaws arise and when dealing with older software. Say that now, in 2018, random is cryptographically secure. Do developers remember to check, when dealing with older versions, that the old random was actually insecure?

An interesting quote on this matter:

Anyone writing crypto code without reading the docs and understanding what they are doing are surely making more mistakes than just using the wrong PRNG. There may be a good argument for adding arc4random support to the stdlib, but making it the default (with the disadvantages discussed, breaking backwards compatibility, surprising non-crypto users, etc.) won't fix the broken crypto code. It will just give people a false sense of security and encourage them to ignore the docs and write broken crypto code.

See this for more insight on how the Python community was reasoning about implementing a CSPRNG by default.

TL;DR. They are faster and easier to implement. In the past, people were afraid of crypto, because of heavy restrictions. Now, people are afraid of giving a false sense of security.

$\endgroup$
  • 3
    $\begingroup$ Most people don't even need Mersenne Twister-level randomness. A modified version of the C89 RNG that generates 63 bits of randomness per call rather than 15 bits can generate random numbers at around 4GB/sec. $\endgroup$ – Mark Jun 29 '18 at 20:29
  • 6
    $\begingroup$ @Mark Mersenne Twister is a bad RNG. It has one of the coolest sounding names, but it's poor in terms of statistical quality, state size, and throughput. Some more modern (non-CS) PRNGs beat it on all three. I think some CS-PRNGs even beat it on all fronts on a single core but I don't have benchmarks. $\endgroup$ – Future Security Jun 29 '18 at 21:38
  • 1
    $\begingroup$ Another reason is that in some cases, people want reproducible sequences of pseudo-random numbers, for example in tests - the simple generators will usually generate the same sequence given the same starting seed. $\endgroup$ – Erwin Bolwidt Jun 30 '18 at 5:36
  • 1
    $\begingroup$ @daniel Done. It's true that, for simple applications, a 2x speed difference may not matter, but other applications, like Monte Carlo simulations, make extensive use of random numbers. Say you have a project to complete in 90 days on your machine. Does it make a difference if you can complete your simulation in 90 days (using a PRNG) or 180 days (using a CSPRNG)? I'd say yes. Also, if your die-rolling application is tied to actual money (like in a casino), use a CSPRNG. Weak PRNGs are not good in casinos. $\endgroup$ – A. Darwin Jun 30 '18 at 6:53
  • 1
    $\begingroup$ @ErwinBolwidt CSPRNGs will also generate the same sequence given the same starting seed. Just in practice, to make them actually secure, you generally keep feeding in a bit of time-variable physical entropy to the generator. But it would be perfectly possible to use a CSPRNG in “deterministic mode”, in fact I'd reckon that this is also needed in some crypto applications. $\endgroup$ – leftaroundabout Jun 30 '18 at 9:17
1
$\begingroup$

Good question for programming language creators and developers.

If you look at the story behind PEP 506, Adding A Secrets Module To The Standard Library (Python Enhancement Proposal 506), the creator of OpenBSD Theo de Raadt got fed up with developers using the Python "random" module for secret stuff, which is not meant for that, reached out to Guido van Rossum, the creator of Python programming language.

My thought on this is when a programmer requires a module to generate pseudo-randomness in her software, the primary use case is for modeling and simulation and not immediately for security purposes (generating random strings, integers, session tokens and session IDS, etc.)

Hence, majority of programming languages offer a standard PRNG, and a CSPRNG (cryptographically secure) which is meant for security stuff.

One good example is Google's Go Programming Language. A relatively new and definitely modern programming language still offering a regular PRNG package called math/rand (of course, it's deterministic)

And a true CSPRNG package for security stuff called crypto.rand (Yes, the one you should use for generating random stuff for session keys, CSRF tokens.)

CSPRNGs will always be slower than PRNGs in exchange of almost true randomness that can never be achieved in finite computer systems.

$\endgroup$
  • $\begingroup$ Hiya. Not quite sure what that last sentence means though. What's being swapped for what? $\endgroup$ – Paul Uszak Aug 16 at 21:45
  • 1
    $\begingroup$ Hi @PaulUszak! Unlike our universe, computer systems are finite. No matter how strong that math behind CSPRNGs, they still draw entropy from the system(s) where the code is running. Given enough motivation, opportunities and means, a threat actor can potentially obtain access to these systems physically or remotely and manipulate them. CSPRNG modules use common computer OS cryptographic libraries as source - i.e., CryptGenRandom or CNG-API in Windows OS, or getrandom(2) in Linux, and /dev/urandom with other *Nix Systems. Let me know otherwise if I am too pessimistic :-) $\endgroup$ – guerilla7 Aug 16 at 22:08
  • $\begingroup$ "Even a paranoid can have enemies" - Henry Kissinger (maybe). $\endgroup$ – Paul Uszak Aug 16 at 22:21
-2
$\begingroup$

Many pseudo-random generators are designed to be capable of generating reproducible sequences of numbers chosen by specifying a seed value. For most common purposes, seed values need not be very big; even a 16-bit value would suffice unless a program needs more than 32767 different sequences of numbers.

For a pseudo-random generator to be cryptographically secure, however, the range of possible seeds must be much larger--too big to fit in a single number. Further, the value of using a CSPRNG would be limited unless an application has a cryptographically secure means of generating seeds (which, of course, most applications wouldn't).

$\endgroup$
  • 8
    $\begingroup$ Cryptographic pseudorandom number generators can be used with fixed seeds too. In fact, because they are designed for interoperability in protocols over the internet between different types of computers, they are guaranteed to be reproducible, unlike calling, say, the standard library rand in C. $\endgroup$ – Squeamish Ossifrage Jun 29 '18 at 21:01
  • $\begingroup$ Even if each $2^{16}$ seeds resulted in statistically independent output streams, that's not enough bits for typical applications. What applications run fewer than 32 thousand (Or 65K) times? And you have to worry about seed collisions, something that actually becomes probable around a number of seeds generated on the magnitude of $2^{n/2}$ (for an n bit seed), not $2^{n-1}$ or $2^n$ seeds. $\endgroup$ – Future Security Jun 29 '18 at 21:50
  • $\begingroup$ @FutureSecurity: In many cases where seeds are supplied manually, having even a dozen different streams would be plenty. Obviously there are many cases that need more than 32767, and most implementations can handle four billion, but that's not even close to what would be needed for most security-related applications. $\endgroup$ – supercat Jun 29 '18 at 22:08
-2
$\begingroup$

Aside from the performance issue because of slower CSPRNG implementation (which would only affect applications spending a significant portion of CPU time on random numbers), there's also a maintenance issue which would affect many more apps.

Imagine random.random() is implemented as a CSPRNG and is used as such. Now, when a bug is discovered in it, it's a major security flaw for the whole Python. So, instead of a small CSPRNG library, a much bigger Python library has to be distributed as a "security fix", which means it has to be installed right away and servers using it have to be restarted. Typically, when you get a security fix for a library you use, there's no easy way to tell if your app is affected, so servers which don't use random.random() will have to restart anyway.

Worse, if the Python library is distributed as a single package on a given platform, every bugfix in it may become a "security fix".

Also, fixing a crypto-related bug random.random() may break apps which didn't use it for crypto and didn't need a fix in the first place. E.g. it's quite common for some software to rely on a particular pseudorandom sequence for a given seed, which pretty much any fix will change.

$\endgroup$
  • $\begingroup$ "it's quite common for some software to rely on a particular pseudorandom sequence for a given seed" Do you have an example of this, where a program relied on a generic random interface (rather than an explicitly named PRNG interface) to return the same values for a given seed? That'd be a prime example of relying on undefined behavior. $\endgroup$ – Nat Jun 30 '18 at 11:24
  • 3
    $\begingroup$ @Nat The Seed implementation $\endgroup$ – NieDzejkob Jun 30 '18 at 20:24
  • $\begingroup$ @Nat Repeatable test suites with fixed seed are very common. And relying on random to return a particular value is not UB. It's "implementation-specific behaviour" at worst, and is actually well-defined in some languages and libraries, e.g. Java. $\endgroup$ – Dmitry Grigoryev Jul 2 '18 at 7:29
-3
$\begingroup$

They are two completely different things with no overlapping purposes.

You want a uniformly distributed floating point number from 0.0 to 1.0 when you are doing things like random simulations. The random number distribution is more important than the number of bits in the random number. There is no notion of Entropy here. Entropy is a well-defined number of bits of uncertainty. The interface being satisfied is generally going to be:

func(prngState) float // from 0.0 to 1.0, ideally uniformly and randomly distributed

A cryptographic random number generator is giving you a string of bits with a known amount of entropy. Entropy is everything in this situation.

func(cprngState) []byte // n bytes means 8*n bits of entropy in the ideal case

For every bit of entropy, there is a doubling of the space of uncertainty. If you sha256 hash a number from 0 to 7, then there are only 3 bits of entropy -- not 256. 256 is just the number of bits of the result. But you only need to generate 2^3 possibilities to figure out the hash input if there are 3 bits of entropy.

$\endgroup$
  • 4
    $\begingroup$ You can easily use a CSPRNG to generate a floating point number... $\endgroup$ – forest Jun 30 '18 at 6:02
  • $\begingroup$ @foret but this is WHY random number generators used for non-security purposes are not secure. they do not NEED to be secure, so they don't pay the significant cost penalty for being secure. The fact that you can satisfy the interface for a uniform distribution with a secure random number generator makes it sound like there is no reason to have insecure-by-default random number generators; which doesn't answer why it's insecure by default. The interfaces and requirements for the two are different, and have no purposes that overlap. $\endgroup$ – Rob Jun 30 '18 at 15:13
  • 1
    $\begingroup$ The interfaces for the two are the same and the requirements for a CSPRNG are a superset of the requirements for a PRNG. $\endgroup$ – immibis Jul 1 '18 at 10:21
  • $\begingroup$ the interfaces are actually pretty different. if you get 32 random bits from a CSPRNG, first you get an array of bits - the number of bits of entropy you require - back as output. If you were to simply cast those bits to a float32, then you would get a non-uniform distribution when you interpret the floats numerically. if you take 8 random bits cast them to a number and mod them 73, then the lower numbers that wrapped around show up twice as often. the PRNG for a float from (0.0 .. 1.0) requires a uniform distribution and it isn't necessarily stated how many bits of entropy. $\endgroup$ – Rob Jul 3 '18 at 1:16
  • $\begingroup$ the closest thing to trying to satisfy a PRNG with a CSPRNG is to take a number of bits (of entropy), like 24 bits (don't use exponent). Take that number from (0.. 2^24-1) and scale it down to fit uniformly into a float32 (0.0 .. 1.0). The numbers are supposed to be evenly spaced and randomly selected. $\endgroup$ – Rob Jul 3 '18 at 1:21
-3
$\begingroup$

The accepted answer is excellent, but I want to give an abbreviated answer: the more common workload for pseudorandom numbers is one in which you need them fast, and you need to be able to get repeatable sequences in testing. Cryptographically strong pseudorandom number generators have neither of these two properties.

$\endgroup$
  • 3
    $\begingroup$ and you need to be able to get repeatable sequences in testing CSPRNGs provide deterministic output from a seed value. $\endgroup$ – Ella Rose Jun 30 '18 at 20:08
  • $\begingroup$ @EllaRose Although /dev/*random and whatever Microsoft use don't... $\endgroup$ – Paul Uszak Jun 30 '18 at 21:46
  • $\begingroup$ CSPRNGs have both of these two properties (depending on the one you choose). $\endgroup$ – immibis Jul 1 '18 at 10:20

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.