# What does it mean for a random number generator to be cryptographically secure?

I've never heard a good answer. I'd like to hear details about:

• What are the criteria that make an RNG cryptographically secure?
• Why must your RNG be cryptographically secure? I.e., what are the consequences if it is not?
• Examples of secure and insecure RNG's
• Would a non-pseudorandom generator be cryptographically secure? E.g. one based on radioactive decay of a particle.

What are the criteria that make an RNG cryptographically secure?

In short, a DRBG [deterministic random bit generator] is formally considered computationally secure if a computationally-limited attacker has no advantage in distinguishing it from a truly random source.

What does this mean? Given a DRBG F and a truly random oracle G, let A be a probabilistic "attacker" that accepts F or G and outputs 1 or 0 after making queries to the function it was given. We define the attacker's advantage Adv to be |Pr[A(F)=1] - Pr[A(G)=1]|. If Adv is non-negligibly more than zero, the DRBG is considered broken. In this definition, note that it doesn't matter what returning 1 or 0 "means", just that we care only if A has a different probability of returning one or the other when given F and G.

In English, if there exists a computable function that can reliably tell the difference between a black-box DRBG and a black-box truly random function, then we consider it a break of the DRBG.

Why must your RNG be cryptographically secure? I.e., what are the consequences if it is not?

This is probably far too broad a scope for a question like this. In some cases it doesn't have to be. In some cases even a slight weakness can cause a near-total loss of confidentiality or authenticity. The implications of a weak RNG are completely dependent upon the system and context in which it is used.

Examples of secure and insecure RNG's

There are multiple kinds of DRBGs, intended for different purposes.

Yarrow and, later, Fortuna are algorithms that accept as input entropy sources of unknown quality, mix them, and produce entropy streams with strong guarantees as output. They have self-healing properties that resist injection attacks; even if an attacker controls almost all of the inputs, after a finite amount of time, the outputs will become indistinguishable to the attacker.

This is an extremely useful property for system RNGs such as those used by operating system kernels and provided to userspace through /dev/urandom, getentropy(2), and CryptGenRandom() (note: these interfaces may or may not actually use Yarrow or Fortuna, they are just examples of the types of system RNGs those algorithms were designed for).

Stream ciphers like ChaCha20 or block ciphers in streaming modes like CTR are really just cryptographically-seeded DRBGs. These algorithms aren't designed or intended to defend against an attacker injecting predictable inputs as the aforementioned algorithms were, but they produce nearly-infinite streams of randomness at very high speed given only a small initial random key and IV. These streams can then be XORed against a plaintext to produce a cryptographically-strong ciphertext. Even better, these algorithms are typically seekable; given a key, IV, and long ciphertext, you can generally seek far into the ciphertext and decrypt individual bits without needing to compute the entire stream.

I won't list insecure DRBGs here. There are simply too many to list, and the general assumption should be that a DRBG is not secure unless demonstrated otherwise.

Would a non-psuedorandom generator be cryptographically secure? E.g. one based on radioactive decay of a particle

Non-pseudorandom generators are the only generators that are even capable of being information-theoretically secure, which is a significantly stronger metric than computational security. With a computationally-secure DRBG, a small seed of n bits is expanded into a larger cryptographic stream; that larger stream still is only one selection of at most 2^n possible streams.

Quantum sources of randomness such as radioactive decay and thermal noise are by physical definition truly random.

• Note that you may have to post-process output from physica randomness sources to get a properly distributed random bit(string) from them. Aug 5, 2016 at 18:23
• It's worth noting (wikipedia does, but I like to see it not behind a link) that "computationally secure" in an RNG is, much like "secure" in a cryptosystem, the kind of thing that's only really proven in the negative. Either we know of an algorithm that breaks it, or we know that we don't know of one. We can build on top of problems that we think are unlikely to have tractable solutions, but there's a dearth of proofs, at least until someone comes through with P?=NP. Aug 6, 2016 at 6:02
• DRBG is not the standard terminology, as it was coined by NIST and generally refers to a CSPRNG combined with entropy estimators and functionality for catastrophic reseeds, etc. CSPRNG (Cryptographically-Secure PseudoRandom Number Generator) is the most common term.
– forest
Apr 4, 2019 at 3:32

I tried to use mostly non-jargon to make it more understandable than the current top answer.

What are the criteria that make an RNG cryptographically secure?

• Given all outputs so far, there must not be any algorithm that predicts future outputs with anything better than guessing. If you can say "there is a 50.0001% chance the next bit is going to be 1 instead of 0", it is not a CSPRNG.
• One cannot compute previous outputs either, even when given an infinite number of outputs after the first output.

Why must your RNG be cryptographically secure? I.e., what are the consequences if it is not?

Imagine you run a lottery and someone checks if you use the Mersenne Twister algorithm (a very common algorithm because of its speed to quality ratio). After about 600 lottery drawings, that person will be able to predict the next winning number.

This is because a Mersenne Twister is not a CSPRNG but "only" a PRNG. It was designed to be fast and have good randomness, but not to be secure against people trying to compute its internal state based on the outputs. The algorithm is great for video games and simulations that depend on random events. It's a terrible choice for running a lottery, hosting online poker games (shuffling the deck will become predictable), generating random passwords or security keys used for HTTPS, etc. There are well-known cases of people using a PRNG (not a CSPRNG) and being outguessed by others, losing a lot of money (or information, in case of compromised encryption).

Examples of secure and insecure RNG's

Insecure:

• rand() = (seed*=7) % 100 (exceedingly simple, but just to give a concrete example).
• Random/random/rand packages or functions, in all programming languages that I know of: C, Java, PHP, C#, Python, JavaScript, etc. This is by design because one often just needs random sampling and there is no security impact if someone guesses the output.
(Personally, I think we should rename those functions to something that makes the difference clear, like secure_random() and fast_insecure_random(), given how often the two have been confused.)
• Anything designed by me or, since you're reading this question, you.

Secure:

• Algorithms used for /dev/urandom and CryptGenRandom, for example.
• The algorithms Yarrow and Fortuna, but you need to feed them entropy, so relying on the operating system to collect that is better.
• random_bytes(n) in PHP is secure, but be careful when you do modulo on it: doing $n = ord(random_bytes(1)) % 12 to get a random number from 0 through 11 is not secure (more info here), you should use random_int(0,n) for that. • A dice throw or a deck of cards, given a good die or well-shuffled cards. Would a non-pseudorandom generator be cryptographically secure? E.g. one based on radioactive decay of a particle There is no known method to predict decay so, yes, that is by definition cryptographically secure. Such things are considered true randomness, as opposed to the pseudo-randomness that we generate with our pseudo-random number generators (algorithms). The caveat is that you have to use the true random source properly. For example, if one particle decays (on average) every 30 nanoseconds and you write down the current time every time it happens, this number is not very random because the time is ever-increasing and the next event will almost certainly be less than X nanoseconds after the previous one. An attacker can guess the few possible values between 0 and X. Only the timing variation from each decay event can be used, for example by taking the last digit of the nanosecond in which the particle decayed. That would give a uniform distribution from 0 through 9, so a couple bits of entropy/randomness... if and only if your clock is precise to that nanosecond and has no interruptions that an attacker could learn of, which might be hard to verify. So while it's truly random, designing methods to extract the entropy from such sources is not necessarily intuitive or easy. Hope this helped! Comment if there is anything I can clarify. • Your 50.00...1% point seems a bit vague. Lack of bias is a good property of any RNG, but there are trivial algorithms to unbias it (Neumann, so long as events are independent). Also, an RNG where you had a 70% chance to guess the output correctly could still be securely used, just the strength is halved (one bit of "secure" entropy per 2 bits output). I think the major distinguishing factor is if it's just security-through-obscurity: if someone knows the algorithm and whatever state leaks out, can they reduce the secure entropy to 0. Aug 5, 2016 at 20:12 • @NickT A biased RNG may be a suitable entropy source, but it isn't a cryptographically secure RNG. A cryptographically secure RNG is unbiased. There's no reason to believe that a biased RNG would have independent events; unbiasing an RNG requires crypto, and assembling a biased entropy source and a CSPRNG is how you get a cryptographically secure RNG. Aug 5, 2016 at 21:28 • Great answer, thanks. 'Google' verb alone is ambiguous, my first reaction to this and being outguessed by others, losing a lot of money. Once again, google. was 'when did google do that?!' Aug 6, 2016 at 12:12 • You said "doing something like$n = ord(openssl_get_random_pseudo_bytes(1)) % 12 to get a random number from 0 through 11 is not secure". Exactly why? Please explain. Aug 7, 2016 at 15:18
• @user40602 It's explained here on Stackoverflow: Why do people say there is modulo bias when using a random number generator?. I searched for "modulo random" to find this answer as the top suggestion on duckduckgo.
– Luc
Aug 7, 2016 at 15:35
• What are the criteria that make an RNG cryptographically secure?

There are many subtle security properties that can be specified for a pseudo-random number generator, but we can dumb it down to three categories. Given an attacker who is computationally limited (can only perform a limited amount of computation):

1. Computational security: An attacker who sees some of the PRNG's outputs, but not its seed or state, should not be able to predict other outputs (neither earlier nor later ones).
2. Forward secrecy: If an attacker does see the state of the PRNG at one point in time, they are nevertheless unable to reconstruct earlier outputs. This is normally achieved by taking care that the PRNG transforms its state in a "one-way" manner that's cryptographically hard to reverse.
3. Prediction resistance: If an attacker sees the state of the PRNG at one point in time, they are only able to predict its future output during a very limited time window. This is achieved by collecting entropy from external sources and using it to scramble the PRNG's state at short intervals.

Note that the first is the bare minimum that a CSPRNG must offer. The second and the third are desirable in applications that:

• Generate private (one-party) secrets, like keys that are not shared between two parties;
• Generate public values that need to be unpredictable (e.g., initialization vectors for CBC encryption).

But they are not desirable in some applications, e.g., in stream ciphers (where two parties use an the same CSPRNG and seed expand a shared secret). Those just want #1.

Also, RNGs that meet just #1 or just #1 and #2 are still relevant because PRNGs that meet all three are often "built like an onion"—the innermost layer meets only #1, a middle layer adds #2 on top of it, and an outer layer takes care of #3. See Ferguson et al's chapter on the Fortuna PRNG (available online; here's a direct link to the PDF).

• Why must your RNG be cryptographically secure? I.e., what are the consequences if it is not?

If the RNG is insecure, an attacker who watches a subset of its output will be able to reconstruct part (if not all) of its future or past output. For example, many cryptographic protocols (e.g., SSL, SSH) work something like this:

1. Alice and Bob each randomly choose an ephemeral private/public key pair;
2. Alice and Bob execute a Diffie-Hellman key exchange with these ephemeral key pairs, to obtain a shared secret key;
3. Alice and Bob then exchange messages encrypted with that shared secret key.

One algorithm commonly used for #3 is CBC mode, which uses randomly generated initialization vectors ("IVs") that are transmitted in the clear. If the RNG is bad, an eavesdropper might be able to backtrack from the IVs back to Alice and Bob's randomly-generated ephemeral private keys, reconstruct the Diffie-Hellman exchange, and decrypt the messages. Ouch!

• Examples of secure and insecure RNG's

One way to gain an appreciation of how insecure common PRNGs can be is to see example programs that crack them from just observing their output. This series of blog entries has some really nice analysis of how two common RNGs (java.util.Random and the Mersenne Twister) can be cracked. The most dramatic example is that it's very easy to predict the output of java.util.Random from just seeing two consecutive ints that it produces. (But beware, the code in the series is not quite right—here's my fixed version of the first article's example.)

As for an example of a secure RNG that illustrates the three properties I mention above, let me link the Fortuna RNG once more.

• Would a non-psuedorandom generator be cryptographically secure? E.g. one based on radioactive decay of a particle

This question is either a trivial "yes" or hard "no," depending on how you look at it. A truly random generator of unbiased, independent bits would trivially be secure. The challenges are that:

• Real-world noise sources often are biased (the probability of a 1 is different from that of a 0) or non-independent (the probability of a 1 depends on previous outcomes).
• True random number generators need therefore to filter the noise source's output to extract unbiased, independent bits. This can be tricky, and thus could be done wrong, in which case the output is more predictable than you would expect.
• An actual device for doing this has engineering challenges to overcome as well. For example, is it possible that the TRNG will fail in a way that's silent to a naïve user but a clever attacker can detect and exploit? (Always assume the attacker is cleverer than you!)
• What are the criteria that make an RNG cryptographically secure?

Suppose that, at any given time, your RNG chooses a number out of $n$ many possible numbers.

Also suppose that $x_t$ is some number that was generated by your RNG at time $t$. So $x_0$ is generated first, then $x_1$ is generated later, and so on.

Let's say that $X_t$ is a random variable that takes values in the set of outputs that your RNG makes at time $t$.

Then, I think, we can say that this RNG is cryptographically secure iff: $$\Pr(X_t = x_t \big| X_0=x_0, X_1=x_1, \ldots, X_{t-1}=x_{t-1}, X_{t+1}=x_{t+1}, \ldots) = \frac{1}{n}$$

I.e. knowing the past or future numbers does not help you to predict the current number.

In my view, requiring computational security is unnecessary. Instead, we should leave choosing $n$ to be open and let to be chosen by the higher-level cryptographic algorithms (e.g. symmetric ciphers, asymmetric ciphers, hashing functions, etc). If they need more randomness, they can concatenate multiple random outputs such as $x_0 || x_1 || x_2|| \ldots || x_t$.

• Why must your RNG be cryptographically secure? I.e., what are the consequences if it is not?

Now you need to look at specific algorithms that offer basic security services. E.g. look at symmetric ciphers, asymmetric ciphers, or hashing functions. Additionally, look at how they are used, such as offering security services such as data integrity, data authenticity, and data confidentiality.

Once you do that, you will realize that lack of adequate randomness means lack of adequate success of your security services.

More specifically: undesired parties will have an easier life decrypting your messages.

One example is: Enigma. Because Enigma didn't make good use of randomness, such as German operators failed to adequately shuffle their rotary disks, plus other mistakes, it was possible to decrypt German messages really quickly, and eventually cause Germany to lose WW2 a bit sooner than otherwise.

• Examples of secure and insecure RNG's.

Security is a relativistic term. Randomness -too- is a relativistic term as well. The goal is to ensure that your adversary can predict your sequences only at a probability of $\frac{1}{n}$, where $n$ is the space of outputs that they try to predict. Anything that ensures this probability is secure.

If you look at the proof for perfect secrecy of the one-time pad, you will see the use of $\frac{1}{n}$ the probability criterion to define perfect secrecy. It all boils down to achieving a probability of prediction equal to $\frac{1}{n}$.

But in absolute terms, all these real-life sensors are in my view not secure. In other words, none of these real life sensors, such as radio active sensors, or whatever fancy sensors that sample things from the outer space, all are not absolutely secure. Because an adversary/attacker could also sense the same source, or a source near enough to the source, to increase the prediction probability such that it is higher than $\frac{1}{n}$.

There is one RNG source that is possibly secure in absolute terms: the quantum randomness.

Some say that the quantum randomness are absolutely random, no matter how fancy your sensors get. It is unknown if this claim is true. But some physicists think that it is probably true.

If you find a source that relies on quantum randomness such that its output follows the uniform distribution $U(0, n)$, then this is the best possible RNG you can ever get.

• Would a non-psuedorandom generator be cryptographically secure? E.g. one based on radioactive decay of a particle

If they satisfy: $$\Pr(X_t = x_t \big| X_0=x_0, X_1=x_1, \ldots, X_{t-1}=x_{t-1}, X_{t+1}=x_{t+1}, \ldots) = \frac{1}{n}$$ then yes, else no.

• Could someone please comment on why this got down votes, plus one vote for deletion? I want to learn. If there is any error in my post, kindly state it. Aug 14, 2016 at 14:22
• Why $X_{t+1},...$ ? I'd expect for every $t$ and every prehistory $x_0, ... x_{t-1}$ and $x_t$ the probability $\frac{1}{n}$, where $n=|\{X\}|$ is the number of possible values. This would imply uniform distribution. May be this does not yet imply independence of the sequence of random variables (which I would require). The construction of a parameterized algorithm with $t$ independent random variables $\{X_1,...,X_t\}$ leads to a parameter set (=seed) of same length, i.e. such algorithm is equivalent to a stream cipher following Laws of large Numbers. Feb 19 at 0:07
• @SamGinrich - Uniform distribution is not enough, as the sequence $0,1,2,\ldots$ is also uniform. It must be both uniform, and not predictable by an adversary. The adversary could be defined differently based on the context. E.g. an adversary could be someone that's not entrusted with the seed or the key. Or, the adversary could be anyone inside this universe (e.g. if quantum randomness is used). Feb 19 at 13:40
• "not predictable" is a didactic measure, I'd leave this out in the first loop. Independence if reasonable en.wikipedia.org/wiki/… Feb 19 at 15:44

RNGs are secure in that they are as random as possible. This means that they:

1. Don't repeat. Early encryption relied on using "random" numbers from a large tape. Eventually people were able to know with certainty what the next random number read from the tape would be, because the tape looped.

2. Don't have predictable patterns. The sequence 3141592 seems random until you add a decimal point: 3.141592 (pi silly).

3. Aren't subject to analysis given a large enough sample. This goes with the first one. A "random" number generator should not return numbers that are able to be determined by a statistical analysis of a large sample. For example, many video-games use random numbers derived in part from the system time. While this is fine for a game, statistical analysis would reveal patterns between the time the number was generated and its value.

4. Rely on entropy. Entropy is a way of getting randomness from some outside source. Conventional (albeit not quantum) computers can't possibly generate a random number, because any equation that can be represented in binary bits relies on an input and an output, and the output will always be the same for the same input. Operating systems that implement cryptographic programs therefore rely on entropy pools. For example, the Linux kernel has (at most) 4096 bytes of entropy in /dev/random at any given time, generated from real-world actions like mouse movements and keyboard presses. Or if you've ever used encryption software like TrueCrypt, you provide entropy by moving your mouse as randomly as possible within the window.

So, why does it matter?

Take one-time pads (OTPs) for example. In an OTP, every character in a message is shifted by a random number of characters in the alphabet according to the random key. This key is then used by the person receiving the message to "unshift" the letters and decode the message. See Wikipedia; https://en.wikipedia.org/wiki/One-time_pad

If someone could predict from a previous key or otherwise know/be able to predict the next group of random numbers, they could predict the keys for future messages, making the whole thing insecure. So, if your RNG isn't secure, your encryption could be useless as an attacker could simply predict and generate their own keys.

Examples of secure RNGs are Linux's /dev/random (not to be confused with /dev/urandom, but that's another post entirely) and Microsoft's cryptographic service provider: https://msdn.microsoft.com/en-us/library/system.security.cryptography.rngcryptoserviceprovider(v=vs.110).aspx (Although it is probably worth noting that Microsoft's encryption API has been backdoored by the NSA).

Insecure RNGs would include those included by default in scripting languages like python. Although python does have cryptographically secure RNG libraries, its normal random functionality is used in things like game design. It should also be noted that random data takes a long time to generate. /dev/random on Linux could take days to fill up. If you're playing a game it doesn't matter as long as it is fast.

And radioactive decay would be a suitable source of entropy and therefore random data, as radioactive decay is (as far as modern physics can tell us) completely random due to the properties of quantum mechanics. So yes, if you were really paranoid you could hook a Geiger counter up to an old smoke alarm and generate truly random numbers to your hearts content. Kind of beautiful actually.

• Please don't spread more FUD about /dev/urandom. Aug 5, 2016 at 17:10
• No need to delete the answer. There's just far too much misinformation surrounding /dev/urandom out there already and it's best not to add to that when possible. /dev/urandom isn't actually derived from /dev/random at all — they actually operate in parallel, using the same de-biased and whitened randomness pool. This diagram from the linked article may be helpful. Aug 5, 2016 at 17:53
• Huh, well it appears you're correct. Thank you for the encouragement and diagram.Cryptography isn't my forte which is why I initially deleted the post out of self-doubt. But once again, knowledge has triumphed over ignorance and fear. Aug 5, 2016 at 19:32
• @StephenTouset I read that link this morning and then was looking into things just out of curiosity. I put /dev/random and /dev/urandom through a statistical analysis for randomness, and /dev/urandom is surprising not random on a Mac. For /dev/random, the correlation was -0.0048 for a set of 100 points and -0.0418 for /dev/urandom. That either means that the "FUD about" link is incorrect of my Mac creates a significantly different result. Then again, I only did 100 points. Aug 6, 2016 at 19:11
• @bdegnan I believe Mac uses Yarrow for randomness, which is indistinguishable from random data. Note that, on Mac OSX, /dev/urandom and /dev/random are actually identical. There is no difference between the two.
– forest
Mar 22, 2018 at 18:33

Why must your RNG be cryptographically secure? I.e., what are the consequences if it is not?

Because there's only one unbreakable cipher method — one time pad. If RNG fails to mask clear text as good as one time pad would have done, the result is more and more vulnerable to crypto analysis.

• Most of the time RNGs are not used for OTP (but for something more practical), so this answer addresses only a small part of the issue.
– otus
Aug 7, 2016 at 18:56
• @otus, should be quite obvious that every crypto algorithm can be thought as gamma being applied to input. And almost every crypto algorithm's essence is how to generate gamma using the key and RNG. Aug 8, 2016 at 1:23