25
$\begingroup$

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.
$\endgroup$
29
$\begingroup$

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.

$\endgroup$
  • 10
    $\begingroup$ Note that you may have to post-process output from physica randomness sources to get a properly distributed random bit(string) from them. $\endgroup$ – SEJPM Aug 5 '16 at 18:23
  • 5
    $\begingroup$ 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. $\endgroup$ – hobbs Aug 6 '16 at 6:02
  • $\begingroup$ 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. $\endgroup$ – forest Apr 4 at 3:32
14
$\begingroup$

I tried to use mostly non-jargon beyond what the question already mentioned, to keep the answer understandable.

What are the criteria that make an RNG cryptographically secure?

From en.wikipedia.org/wiki/CSPRNG:

  • there may be no algorithm that predicts the next output with anything better than guessing. If you can say "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 given an infinite amount 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 guesses you use the Mersenne Twister algorithm (the most 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 "just" a PRNG. This is not a design flaw: 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 its 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, etc. There are well-known cases of people using a PRNG (not a CSPRNG) and being outguessed by others, losing a lot of money.

Examples of secure and insecure RNG's

Insecure:

  • f(x) = x^2 (exceedingly simple, but just to give a concrete example).
  • Random/random/rand packages or functions, in all programming languages that I know of, such as C, PHP, C#, Python, and JavaScript. Once again, this is by design because one often just needs random sampling and it doesn't matter if someone outguesses you. (Personally I think it's time we renamed them to something like secure_rand() and fast_insecure_rand() given how often the two have been confused, but alas.)
  • Almost certainly anything you and I personally designed.

Secure:

  • Algorithms used for /dev/random and /dev/urandom
  • The algorithms Yarrow and Fortuna
  • openssl_get_random_pseudo_bytes(n) in PHP, though be careful when you do modulo on it, doing something like $n = ord(openssl_get_random_pseudo_bytes(1)) % 12 to get a random number from 0 through 11 is not secure.
  • A dice throw, given a good die.

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

Such events can currently not be predicted and are generally considered true randomness, as opposed to pseudo-randomness (and algorithms that generate such pseudo-random numbers). So yes, by definition they would be cryptographically secure.

The obvious caveat is that you have to use the source properly. If you observe the decay of a particle and write down the time, that is not a good source because the time is ever-increasing and the next event will almost certainly be less than X (milli)seconds after the former (this will be a known property of the method you use). An attacker can guess the few options between 0 and X. Only the few bits of randomness that give the desired distribution can be used, for example by taking the last digit of the nanosecond in which the particle decayed. Unless particles decay within nanoseconds of each other (they might, I'm not a physicist), that would give a uniform distribution from 0 through 9.

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Nick T Aug 5 '16 at 20:12
  • 2
    $\begingroup$ @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. $\endgroup$ – Gilles 'SO- stop being evil' Aug 5 '16 at 21:28
  • $\begingroup$ 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?!' $\endgroup$ – Estus Flask Aug 6 '16 at 12:12
  • $\begingroup$ 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. $\endgroup$ – user40602 Aug 7 '16 at 15:18
  • $\begingroup$ @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. $\endgroup$ – Luc Aug 7 '16 at 15:35
7
$\begingroup$
  • 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!)
$\endgroup$
-2
$\begingroup$

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.

$\endgroup$
  • 8
    $\begingroup$ Please don't spread more FUD about /dev/urandom. $\endgroup$ – Stephen Touset Aug 5 '16 at 17:10
  • 4
    $\begingroup$ 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. $\endgroup$ – Stephen Touset Aug 5 '16 at 17:53
  • 2
    $\begingroup$ 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. $\endgroup$ – Verbal Kint Aug 5 '16 at 19:32
  • 1
    $\begingroup$ @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. $\endgroup$ – b degnan Aug 6 '16 at 19:11
  • 1
    $\begingroup$ @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. $\endgroup$ – forest Mar 22 '18 at 18:33
-2
$\begingroup$
  • 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.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – caveman Aug 14 '16 at 14:22
-3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – otus Aug 7 '16 at 18:56
  • $\begingroup$ @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. $\endgroup$ – poige Aug 8 '16 at 1:23

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.