Random Number Generator

Table of contents

Open Table of contents

What it is

A Random Number Generator is a function one can invoke to get access to a random value that has specific “randomness” properties.

Generally speaking, there are three different types of Random Number Generators, all of which provide different guarantees when it comes to their statistical properties.

True Random Number Generator (TRNG)

Speed: Slow

Unpredictability: High

Deterministic: No

The True Random Number Generator ensures that an output of values generated from it can’t be reproduced.

If, for example the binary output after 10 invocations is 1011001101 it’s (almost) impossible to generate the same sequence of bits when invoking it 10 times again.

The chance of success can be computed with the following formula (where nn is the bit length):

12n\frac{1}{2^{n}}

So in our example, the likelihood of generating the same bit sequence would be:

1210=11024≈0.0009765625\frac{1}{2^{10}} = \frac{1}{1024} \approx 0.0009765625

which is very small.

True Random Number Generators are usually based on physical processes such as throwing a dice, flipping a coin, measuring the temperature of your CPU, measuring radioactive decay, etc.

While data gathered through a True Random Number Generator is highly unpredictable, it might exhibit low entropy. Therefore TRNG data from different sources are oftentimes fed into a Randomness Extractor which transforms the data in a way that it has high entropy.

Pseudorandom Number Generator (PRNG)

Speed: High

Unpredictability: Low

Deterministic: Yes

A Pseudorandom Number Generator generates a sequence of random numbers based on an initial seed value. Furthermore the sequence it produces depends on such seed value and is therefore deterministic.

PRNGs usually strive for good statistical properties that enforce an approximation of random behavior when generating a sequence of values.

However, given their dependence on a seed value and their determinism, they’re never truly random.

PRNGs can be found in many software libraries and provide “good enough” randomness for applications such as games and simulations. As soon as you step into the Cryptography territory you should take a pause and double check if you’re working with a Pseudorandom Number Generator or Cryptographically Secure Pseudorandom Number Generator which is what you always want in that case.

Cryptographically Secure Pseudorandom Number Generator (CSPRNG)

Speed: High

Unpredictability: High

Deterministic: Yes

The Cryptographically Secure Pseudorandom Number Generator is an enhancement of the Pseudorandom Number Generator in that it still takes a seed value as input but generates an output sequence that’s “unpredictable”.

Unpredictability here means that the CSPRNG enforces certain, statistical properties for random looking bit sequences while also ensuring that given a random bit from the generated sequence one cannot determine the sequence’s previous bit(s) or the following ones with higher than 50% chance.

The “unpredictable” behavior is what turns a PRNG into a CSPRNG. When working on software that incorporates Cryptography, always make sure that you’re using a CSPRNG and NOT a PRNG.

Interestingly, multiple Random Number Generators can be used together to generate random values that share the security characteristics of their individual generators. Generating random values with the TRNG, for example is expensive and slow as it depends on physical processes. However a random value from a TRNG can be used as the seed value for a CSPRNG which can then be used to generate arbitrary sequences of random values efficiently.

Security Properties

Generally speaking, every Random Number Generator (RNG) should produce values that are indistinguishable from random.

To do so, computational RNGs have some internal state they use to derive the next random value. Ideally an attacker has no access to the internal state. But even if the internal state is leaked, there are two security properties an RNG might exhibit which make it impossible for an attacker to predict the next random value or recover old random values.

Forward Secrecy

With Forward Secrecy it should be impossible for an attacker to recover old values given access to the internal state of the RNG.

Backward Secrecy

Backward Secrecy ensures that the next random value can’t be generated when the attacker has access to the internal state.

This is oftentimes implemented through re-seeding where the seed of the RNG is rotated. Note that re-seeding breaks the deterministic guarantees an RNG might exhibit.

Proper Usage

The following is a list with things to keep in mind when using Random Number Generators to derive randomness for applications.

PRNG vs. CSPRNG

This was already discussed above, but it’s worth highlighting again. There’s a major difference between Pseudorandom Number Generators (PRNGs) and Cryptographically Secure Pseudorandom Number Generators (CSPRNGs).

If you need some randomness in a cryptographic application, always make sure that you’re using a cryptographically secure version.

Forking Processes

If you’re running a process that generated some randomness via a Random Number Generator you might run into the issue where a fork of such process will inherit the randomness from its parent.

In this case you should ensure that new randomness is generated whenever you fork into a new child process.

Virtual Machines

When you’re dealing with Virtual Machines you should take special care when it comes to cloning them. A cloned virtual machine might clone the randomness it generated as well.

If you’re unsure, you should double-check if that’s the case or whether the hypervisor you’re using helps in mitigating this.

Low early boot entropy

Given that most Cryptographically Secure Pseudorandom Number Generators rely on True Random Number Generators for their seed values, it’s usually the case that there’s low entropy after a reboot because there wasn’t enough time to observe physical phenomena to derive randomness.

Depending on your use case, it could be useful to force the application you’re building to wait until enough randomness was observed.

References

The following resources have been invaluable for me to learn the concepts discussed in this article.

You should definitely give them a read if you want to dive deeper into the topic.