The Basics of Crypto 2: How Random Are Random Numbers?

In this instalment we will be covering random numbers, why they are necessary, what we use them for, a brief bit of an explanation about how they are generated and a short explanation about the difference between cryptographic and non-cryptographic random number generators.

Randomness is found everywhere in cryptography, in fact without randomness modern cryptography would be useless as all operations would predictable and therefore insecure.

What is Randomness?

In cryptography there are no random bits, any string of bits can be a randomly generated string provided the probability of that string being correct is equal to the probability of every other potential string of bits being the correct string.

As such what is random is actually the process which produces the bits in question. So when we say random data what we mean is randomly generated data.

In order to gauge the randomness of a string we asses the probability distribution of the potential outputs. Probability distribution is evaluated by assessing the potential of each potential output to be the result of the randomness generator and giving it a value between 0 and 1. All the potential outputs must add up to 1. So as an example when flipping a coin both sides have a 1/2 chance of being the result of the coin flip and the addition of these values equals 1.

At a very basic level you can think of a dice as a random number generator, it generates numbers between 1-6 with a uniform probability distribution. This means that each number between 1-6 has an equal chance of being the result of any dice roll (1/6 for every possible outcome).

However if the dice was weighted to favour 6's in such a way that 50% of the rolls resulted in 6 being the result then the probability distribution would not be equal between all the numbers and as such it would not be a uniform probability distribution. As such the probability distribution would be more like (6) 5/10 + (5) 1/10 + (4) 1/10 + (3) 1/10 + (2) 1/10 + (1) 1/10 the sum of all probabilities is still equal to 1 but they are not all the same value and as such they are not uniform.

Entropy is something we will touch here lightly, it is essentially a method for measuring the predictability of a system. Higher entropy means less predictability. So if you have a uniform distribution of probability entropy is at it's maximum as no possible output is more likely than any other possible output. However if probability is not uniform then entropy will be lower.

Random Number Generators

So were going to cover two things that work in tandem to generate the random strings we use in cryptographic operations. Random number generators (RNG) and Pseudo random number generators (PRNG). Essentially RNG's create truly random data and PRNG's take these seeds and turn them into larger sets of randomised data.

RNG's produce random values relatively slowly from analogue inputs (such as I/O devices, disk activity and similar sources). PRNG's produce random looking data from the random values produced by RNG's quickly. In short PRNG's transform a few unreliable random bit's of data into a long string of reliable pseudorandom data suitable for use in cryptographic applications.

PRNG's generate pseudorandom data from a pool of data created by the RNG called the entropy pool. In order to help remove any statistical bias from the entropy pool the PRNG will on each update reorder the entropy pool. In order to generate pseudorandom data the PRNG uses a deterministic random bit generator (DRBG) which takes a set of bits from the entropy pool and uses that set to create a much longer set of bits. This process as the name suggests is deterministic and not random and as such given a set of inputs the output will always be the same. In order to avoid repetition the PRNG ensures the DRBG never receives the same input set twice. Essentially the PRNG ensures that the inputs provided to the DRBG have high entropy and are never repeated. This is an extremely basic overview of how a PRNG works, for a much more detailed overview consider reading this.

Ideally PRNG's should ensure that previously generated random data is unrecoverable and predicting the random data to be generated should be impossible. This is achieved by regularly refreshing the entropy pool in a way that is irreversible and through regularly updating the values in the pool and the seeds passed to the DRBG.

Differences Between Cryptographic and Non-Cryptographic PRNG's

The major differences between cryptographic and non-cryptographic PRNG's is that non-cryptographic PRNG's are only concerned with the uniformity of the data generated. A non-cryptographic PRNG will produce output's with a uniform probability but they will be predictable and as such are unsuitable for cryptographic applications. However they are fine for use in things like video games and other similar applications.

Given a small data set from most non-cryptographic PRNG's it is possible to predict the next set of values from that PRNG as such it is advisable to always use a cryptographic PRNG in cryptographic systems.

Hardware RNG's

We will briefly cover hardware RNG's here. In short a hardware RNG is usually faster than a software RNG as it creates a constant string of random data by having a specific circuit that jump's between 0 and 1. This data is then dumped into a register in sets of 32 or 64 bits. Intel has a hardware RNG in it's Ivy Bridge microarchitecture released in 2012, the RNG circuits in this architecture generates it's random bits based on thermal noise fluctuations at a frequency of 800 MHz. Hardware PRNG's are considered some of the best RNG's available, there is some good information behind this which can be found here,