Pseudo Randomness

The first distinction to be made is the difference between a pseudo random number generator (PRNG) and a true random number generator. A pseudo random number generator is just an algorithm that produces numbers that “look” random. Each number occurs with equal frequency and there is no connection between one number generated and another that would help you predict one from the other. For example, while a simple for loop generates numbers that are equally probable 0,1,2,3,4,5,6,7,8,9 and so on, it is a very poor pseudo random number generator because as soon as I tell you the current value is 5 you can work out the that the next number is 6.

Clearly the difficulty here is in defining what we method we can use to predict the values. If you know the algorithm in use you can always predict the next or any value that will be produced. In this sense no pseudo random number generator is truly random. Even though this is obviously the case, pseudo random number generators are useful.

The sequence that a PRNG produces depends on where it is started from. The starting value is usually called the “seed” and starting from a fixed seed always produces the same sequence. There are situations where this is useful and some where it is definitely to be avoided. For example, if you are programming a card game using a PRNG and use the same seed to start it off each time the program is run, the players will be subjected to the same sequence of cards. In this case, you need some mechanism to select a different seed each time the program is run. On the other hand, if you are testing a set of alternatives to see how they perform then using the same sequence of pseudo random numbers for each test is much more informative than using truly random numbers.

Even though pseudo random numbers are generated by an algorithm, we can still perform statistical tests on them and look for statistical relationships that can help with guessing the next number. For example, if the PRNG tends to produce an odd number after an even number then we can use this to improve our guessing of the next number. However, if you know the type of PRNG being used then you might be able to use a small sample of random numbers to work out exactly what is being used and hence predict all of the subsequent numbers exactly. This defect is not shared by hardware random number generators.

There are many approaches to creating a PRNG, but two are particularly important for small machines and form the basis for most complicated algorithms – the Linear Congruential Generator (LCG) and the Linear-feedback Shift Register (LFSR). In both cases, given samples of random numbers from the generator you can work out its exact setup and generate subsequent numbers accurately.

The standard C function rand is an LCG PRNG. The call:

r = rand();

returns the next integer in the sequence. If you want to set a seed then you use:

srand(seed);

If you don’t specify a seed then 1 is used and rand produces a sequence that is so well known it is listed and recognized by The On-Line Encyclopedia of Integer Sequences. It may have random properties, but it is still well known and anyone recognizing it can easily give you any values in the sequence in any order. In fact, the version of rand supplied with GCC is good enough to pass the standard tests of randomness, see later, but it is still unusable as a random number generator to use with mbedtls as its generator is too easy to identify.

Hardware Random Generator

The obvious thing to do to obtain a cryptographic random number generator is to use hardware to produce real physical random numbers. Truly random numbers are not predictable no matter how many samples you take even if you know how they are generated. In this sense a perfect hardware random number generator (HRNG) is what we need. Of course, any physicist will tell you that the only source of truly random numbers is quantum mechanics. Some electronic devices can generate randomness based on quantum effects, but in practice you generally don’t need to be so esoteric. We regularly treat complex physical systems as if they were truly random. When you toss a coin you regard the outcome as random, but in principle if you could measure the initial position of the coin, the force used to propel it into the air and the disposition of the ground, you could work out which side it would land on. In practice, of course, you can’t and there are physical systems that are so sensitive to the initial conditions that, even if you knew them accurately, accurate prediction would be difficult. In this sense even physical sources or randomness only produce pseudo random numbers – if you knew the generating algorithm you could predict them. In practice of course you don’t and you can’t and so hardware generated random numbers are what we need.

In practice, physical sources of noise or entropy can be very simple. For example, you can take readings from an analog to digital converter that isn’t connected to anything or measure the voltage on a reverse-biased diode etc. The problem with all of these ideas is that they are easily spoiled by interactions with the outside world. For example reading data from an unconnected AtoD is vulnerable to whatever coherent signal the input picks up as it acts as an aerial. Similarly timers, often used as sources of random bits, no matter how erratic they tend to be, show short range correlations in output.

In short, actually designing a good physical source of entropy that provides good random numbers is much more difficult than theory suggests. A hardware source of random numbers that has statistical regularities can be predicted in the same way that imperfect pseudo random numbers can.