Evaluating Random Number Generators

Introduction

Uncertainty is a critical facet of human life, but recreating entropy in the digital world requires some extra machinations. In every day life, events that seem random to us are often the result of a complicated sequence of events. We might refer to an incident like a sudden change in the weather or running into someone we haven't seen in years as random, but meteorologists and our friend could both explain the circumstances that led to the event in detail. We chalk up what our limited perspective doesn't allow us to understand as fate or serendipity, but the complex chain of events and consequences that drove the event exists nonetheless. In a deterministic environment like software development, it's therefore difficult to recreate that unpredictability without knowing how to replicate it. Random number generators (RNGs) are the driving force behind system fundamentals from security encryption to rolling virtual dice in online games; if one knew, for instance, how a financial firm generated their authentication codes, a bad actor might be able to make an accurate guess and wreak havoc on their system. Artificially manufacturing randomness is complicated: in this article, we’ll first compare tRNGs and pRNGs and their applications. We will then shift our discussion to learn about what qualities constitute a “good” random number.

tRNGs vs pRNGs

While there are numerous ways to generate random numbers, all RNGs fall into one of two categories: true random number generators (tRNGs), and pseudo random number generators (pRNGs). Though both are used in technologies today, you will find that pRNGs are more widespread. This is because many modern-day applications prefer Pseudo-Random Number Generators’ qualities of simplicity, robustness, and reproducibility over the “true” randomness from True-Random Number Generators. Technologies that do use tRNGs require the irreproducibility that tRNGs provide. We proceed to examine both types of Random Number Generators and compare their different use cases.

Fundamentally, pRNGs are created with a deterministic process that takes on the form of some mathematical algorithm. This makes them extremely straightforward to implement. A programmer can simply choose a seed and the algorithm performs a series of mathematical operations on it to generate a string of numbers according to the distribution they want. This robustness becomes crucial for purposes including simulating data, like in medical studies or weather forecasting. One can imagine that an unintentional bias in the random number generation would be detrimental to the outcomes of the study. Furthermore, the concept of setting a seed touches on the reproducibility of Pseudo-Random Number Generators. The deterministic aspect of pRNGs guarantees that a researcher can run existing code and verify the exact result from before. Another example comes from cyber security, where security keys are often a string of random numbers (DeGarmo). The intended user needs to be able to recreate the security key; this is possible with pRNGs since the key can be fully reconstructed with just the seed.

While pRNGs are algorithm-based, tRNGs are rooted in hardware. The vast majority of them rely on using entropy in the environment, such as the noise from temperature measurements or slight jitters from electrical signals. The hardware then detects these signals and outputs the measurements as “true” random values. Since we are dealing with capturing ambient entropy, it is obvious that tRNGs have zero reproducibility. This method also means that the system is very sensitive to noise. Take common thermal-based tRNGs, for example. If the environment suddenly increases in temperature, the distribution of the resulting string of numbers would be vastly different than expected. Clearly, the robustness that was guaranteed with pRNGs is no more. Someone who wanted their random numbers to follow a certain distribution would need to perform extensive post-processing on the generated data, which complicates things more.

One may now ask, “Why would anyone choose a tRNG over a pRNG?” This is a valid question, since we have seen how tRNGs are fickle to work with, difficult to implement, and impossible to guarantee distribution. In some applications, the true randomness quality of tRNGs is absolutely necessary. An example of this is when fairness is required, such as when determining the winner of the lottery. In fact, in the early 2000s when the lottery used pRNGs, the lottery results in several US states were ‘rigged’ by a computer information security director (Buchanan). This was due to the reproducibility of pRNGs. The director hacked into the random number generator software and exploited a loophole to manipulate lottery winners, netting himself over two million dollars (Buchanan). In cases like these, it is easy to imagine why it could be necessary to use True-Random Number Generators. Though they both simulate randomness, rNGs and pRNGs have differing methods and their respective pros and cons. Ultimately, it is up to the application at hand that determines which one should be used.

NIST Tests and Quantifying Randomness

I’ve alluded to randomness as a measurable quality, but how can we quantitatively say that one sequence of bits is “more random” than another? A good starting point is to imagine that in a given sequence of bits, a “random” sequence should have the same amount of 0’s and 1’s, the way a coin flip has a 50% chance of landing on heads or tails. Consider the following sequences of bits:

• 1111111100000000
• 1010101010101010
• 1101011001010100

Although all three sequences contain the same amount of 0’s and 1’s, the first two clearly have a more obvious distribution. Using the above example as a basis, we can consider scaling up to bit sequences that are several orders of magnitudes larger. Naturally, patterns will begin to emerge: do the bits begin to repeat themselves? Are the amount of consecutive ones or zeros doubling? Does the Fibonacci pattern start to show up? If I plotted the points, would a discernible image appear? The more recognizable the bits are, the easier it is to predict them. One such framework which can be used to categorize the quality of random numbers is the National Institute of Standards and Technology (NIST) Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications. The publication is an incredibly detailed technical description of random number generators and fifteen different statistical tests which are considered the industry standard for testing random number generators, and it heavily contributed to this article. A more detailed mathematical description of the tests can be found in the publication, but I'll explain a couple of the simpler tests to expand on the concept of measuring randomness.

The simplest and first test is the frequency test: in a random stream of 1's and 0's, there should be very close a 50% distribution of each bit. there's also a frequency block test; within segments of the data, the bits should also be reasonably distributed. However, as seen above, a sequence that just flips between bits isn't a random sequence. The template tests use a sliding window to check that certain bit patterns do not occur too many times aperiodically throughout the data. Another interesting test is the cumulative sum test, which "walks" through the data (assume 1's and -1's instead of 1's and 0's) and progressively calculates the sum of the bits. To approximate a truly random sequence, the sum should stay around zero within an appropriate standard deviation, depending on the length of the data. Some of the more complicated tests involve taking a Fourier Transform of the data or evaluating the rank of matrices of the bit stream. Again, please refer to the publication for a complete, mathematical explanation, but the goal of the NIST tests is essentially to detect any sort of pattern or regularity or periodicity of the data. The sequence must be complex, unpredictable, and unreproducable. If a sequence of randomly generated bits passes all fifteen of the tests with acceptable p-values, it is then considered random enough for cryptographic and other applications.

We’ll be using the tests as a tool to explore pseudorandom number generators, specifically one you may have used before: Python’s random function. We will write a simple script to generate some random numbers and examine them via the NIST Test Suite.

Code and Results

This is the script I used; please see the Python random function documentation page and this [tutorial] about writing to a file if you want a more detailed explanation.

import sys
import random 

original_stdout = sys.stdout 

#open file
with open('rand1.txt', 'w') as f: 
    sys.stdout = f 
    # generate bit sequence
    for i in range(1000000):
        rnd_num = random.randint(0, 1)
        print(rnd_num)
    sys.stdout = original_stdout 

Essentially, we want to generate around a million random bits and place them in a text file. Once we have generated our bit sequence, we can run the NIST tests on our pRNG data.

When running the NIST tests, follow the instructions listed on page 96 of the publication. The suite generates a user-specified amount of bit streams to run the test on; I chose 10. Here is a table of the outputs from the text file I generated:

Statistical Test	P Values	Pass Rate
Frequency	0.911413	10/10
BlockFrequency	0.350485	9 /10
CumulativeSums	0.122325	10/10
Runs	0.739918	10/10
LongestRun	0.213309	10/10
Rank	0.350485	9/10
FFT	0.739918	10/10
NonOverlappingTemplate	0.739918	10/10
NonOverlappingTemplate	0.911413	8/10
OverlappingTemplate	0.991468	10/10
Universal	0.991468	10/10
ApproximateEntropy	0.739918	9/10
RandomExcursions	N/A	5/5
RandomExcursionsVariant	N/A	5/5
Serial	0.350485	10/10
LinearComplexity	0.739918	9/10

The non-overlapping template test and the random excursion tests are actually ran more than once by the test suite, but I have selected only a couple of those results for clarity of demonstration. Additionally, the random excursion tests do not output p-values, so they are listed as n/a. For 10 bit streams, a passing rate is considered to be 8/10 or above. As seen in the pass rates in the proportions section, our Python random function generated sequence passed the NIST Test Suite! This is not a go-ahead to use the function for cryptographic purposes, as a robustly tested pRNG would need a much larger sample size including variables we are not covering in this article, but it does tell us that the Python random function is, in fact, pretty random. It’s good enough to tell you that if your code is buggy, the Python random function is probably not the source of your problems. The test with the worst pass rate was the non-overlapping template; as this test is run about two dozen times with many different templates, it's not surprising that this is the test with more failures than any other. The frequency test passed with flying colors, which is good given that it's the simplest test of randomness in the suite.

Random number generation is statistically complicated; we must apply mathematical values to the concept of unpredictability. However, robust tests like the NIST test suite can help us analyze quality of randomness and help us locate any patterns or periodic elements of our random number generator. Next time you need to generate a random number, regardless of the application, consider the quality of randomness and all the effort that goes into generating random sequences!

References

https://nvlpubs.nist.gov/nistpubs/legacy/sp/nistspecialpublication800-22r1a.pdf
https://www.geeksforgeeks.org/pseudo-random-number-generator-prng/
https://www.sciencedirect.com/topics/computer-science/mersenne-twister
https://www.synopsys.com/designware-ip/technical-bulletin/true-random-number-generator-security-2019q3.html

Buchanan, P. B. (2018a, August 10). Random numbers. Medium. https://billatnapier.medium.com/random-numbers-1c1b454cafa9#:~:text=A%20lottery%20should%20always%20be,not%20repeat%20or%20be%20predictable.
DeGarmo, R. (2021, July 13). True random vs. pseudorandom number generation. wolfSSL. https://www.wolfssl.com/true-random-vs-pseudorandom-number-generation/