Cryptographic Random Generator

Now that we have considered the two major types of random number generators and their strengths and failings we can consider what would make a good generator. A cryptographic random number generator (CRNG) is usually defined as one where it has been proved that any algorithm that can predict the n+1 value with a better than 50% chance of being right given n values has to take more than polynomial time. The idea is that even if there is a prediction method it will be so slow as to be impractical.

A second condition requires that even if part of its internal state has been revealed or guessed then it should be impossible to reconstruct the sequence. This means that a congruential generator is ruled out on both counts, as is an LFSR. Just appearing to be random isn’t enough to be a CRNG. You have to have a cast iron guarantee that no matter how many samples are gathered you cannot deduce the algorithm used to generate them in anything like a reasonable time.

A CRNG not only has to pass the first test of appearing to be random, it also has to not reveal details of how the values are generated. It might seem that any algorithmic method of generating random number cannot be a CRNG as there is an algorithm to be discovered. There are provably secure CRNGs based on mathematical problems known to be hard to solve. For example, the Blum Blum Shub algorithm produces a sequence based on the quadratic residue problem which is not solvable in polynomial time. In this case having a sample from the sequence is provably difficult to reverse engineer in the sense that it would take an attacker too long to go from values in the sequence to the parameters of the mechanism that created it.

In short, algorithmic CRNGs do exist. However, while it is good to know that such things exist they are mostly not practical for IoT use due to their computational demands.

An additional consideration, not normally discussed in the literature, is that in many cases an IoT device is in the hands of the end user. That is, IoT devices are generally not physically secure. What this means is that if you program a cryptographically sound random number generator then it is only a matter of time before someone reverse engineers your device and the details of the generator are accurately known including the configuration parameters. This means that any PRNG, CRNG or not, is insecure when installed in an IoT device.

The only practical approach is to make use of an algorithm to improve the statistical qualities of an HRNG. In this case you can make the argument that the good statistical qualities makes it hard for an attacker to guess the next number and even if they had a set of numbers from the sequence the hardware generated component makes this knowledge useless in predicting future values.

What all this means is that, contrary to what you will often read, for an IoT device the task is not to install a CRNG that is provably secure, but to improve any HRNG sufficiently to make it pass a battery of statistical tests of randomness.

There are three general approaches to enhancing a hardware source of randomness:

1. You can use a randomness extractor – an algorithm that makes the HRNG even more random. For example, you could XOR the output of the HRNG with the output of a good PRNG. Even if you know the details of the PRNG you still can’t reliably predict subsequent numbers.

2. Hash functions and encryption methods are designed to break up patterns in the source text and these can be applied to the output of a HRNG to improve its statistical properties. This is the reason you will often encounter the strange idea of encrypting or hashing hardware generated random numbers. You can use multiple HRNGs and combine them together to produce numbers with better statistical properties. This is often called using an entropy pool and it is an approach that has become very popular – Linux uses it, for example, to implement dev/random and dev/urandom.

Testing Random Numbers

Before you decide to use any random number generator you need to either test it yourself or rely on tests already performed to confirm that it is indeed generating random numbers. The only problem with this is that there are a number of libraries of testing software and they are are poorly supported. The best known are diehard, dieharder and the NIST. None of them are particularly easy to use, but at least if your random numbers pass enough of the NIST suite you can claim that you are using something that passes the National Institute of Standards and Technology.

To test random numbers you need to generate a large sample – 100,000 or more and consider the potential weaknesses of the generator according to the tests that they fail.