Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
I've never heard a good answer. I'd like to hear details about:
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.
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?
From en.wikipedia.org/wiki/CSPRNG:
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.secure_random() and fast_insecure_random(), given how often the two have been confused.)Secure:
/dev/urandom and CryptGenRandom, for example.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.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.
- 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):
Note that the first is the bare minimum that a CSPRNG must offer. The second and the third are desirable in applications that:
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:
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:
- 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.
RNGs are secure in that they are as random as possible. This means that they:
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.
Don't have predictable patterns. The sequence 3141592 seems random until you add a decimal point: 3.141592 (pi silly).
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.
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.
/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$
Aug 5, 2016 at 17:53
/dev/urandom and /dev/random are actually identical. There is no difference between the two.
$\endgroup$
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.
