Statistical tests to evaluate randomness
Random numbers are an essential resource for classical, quantum and post-quantum cryptography, as well as having numerous other applications such as in computer simulation. A random number generator (RNG) is a source of random numbers. A good RNG will only fail very stringent tests but these are difficult to run by unpractised operators. In this service, NPL applies tests of the randomness of the output of an RNG to give confidence in its quality and fitness for purpose.
About this service
NPL takes the data that are the output of an RNG and applies statistical tests to evaluate the randomness of the output. This service offers:
- The possibility to run many different statistical tests, which requires the ability to manage large volumes of data and apply significant computing resources, and allows a comprehensive evaluation of the output of an RNG
- A post-processing and interpretation of the test results obtained that is principled, as we make use of multiple-hypothesis testing to account for the multitude of test results and we apply the tests at the same time to various pseudo RNGs of known pedigree to act as ‘controls’
- Independence and neutrality through our role as a National Measurement Institute.
We offer two standard levels of testing, lightweight and heavyweight. Either can be adapted to the requirements of the customer on request. We are also able to offer customers advice on the physical characterisation of quantum RNGs.
What to expect
We start by agreeing with the customer the statistical tests to be applied. We also agree with the customer the pass/fail criteria for the tests, which are expressed in terms of the risk of incorrectly failing an RNG that is truly random. The data is provided by the customer in the form of a sequence of binary files and usually on a physical data storage device such as a portable hard drive. We upload the data to our High-Performance Computing cluster, run the tests and post-process the test results obtained to give a summary and interpretation of them. We deliver to the customer the test results together with an evaluation report that describes the testing undertaken and presents the summary and interpretation of the test results.
Depending on the volume of available data, we apply statistical tests selected from one or more of the following pre-defined and publicly available batteries: ENT, NIST-STS, and the batteries ALPHABIT, RABBIT, SMALLCRUSH, CRUSH and BIGCRUSH taken from the TESTU01 package.
Lightweight testing
This level of testing requires 8 Gbits of binary data provided as a single 1 GB binary file. The statistical tests run on the data are those included in the batteries:
- ENT, applied to the single bitstream of length 8 Gbits
- NIST-STS, applied to 8,192 sub-bitstreams each of length 1 Mbits
- ALPHABIT, RABBIT and SMALLCRUSH taken from the TESTU01 package, applied to the single bitstream of length 8 Gbits.
Heavyweight testing
This level of testing requires approximately 9 Tbits of binary data, which is most conveniently provided as a sequence of individual binary files having the same size, for example, as 1,500 1 GB binary files each containing 8 Gbits of binary data. The statistical tests run on the data are those included in the batteries:
- ENT, ALPHABIT, RABBIT and SMALLCRUSH applied to each individual file (effectively lightweight testing applied to each file)
- NIST-STS applied to typically ten individual files (effectively lightweight testing applied to a subset of the files to accommodate the long runtimes for these tests)
- CRUSH taken, from the TESTU01 package, applied to bitstreams defined by several non-overlapping sub-sequences of binary files
- BIGCRUSH, taken from the TESTU01 package, applied to the single bitstream defined by the complete sequence of binary files.
This level of testing is more stringent than the lightweight testing. Not only does it include the more stringent tests provided in the CRUSH and BIGCRUSH batteries, but it provides richer information based on an analysis of the test results obtained from applying lightweight testing to the bitstreams contained within the individual binary files. However, it requires appreciably more data to run the tests compared to the lightweight testing.
Batteries of statistical tests
ENT [1] is a small battery of statistical tests that is simple and fast to run. It includes a chi-squared test of the numbers of zeros and ones in a bitstream, and calculations of entropy (with an expected value of one in the case that the output is truly random), the arithmetic mean (with an expected value of 0.5), a Monte-Carlo estimate of π and serial correlation (with an expected value of zero).
NIST-STS [2] is provided by the National Institute of Standards and Technology (NIST) in the US. The battery comprises 15 tests returning 188 test values and allows the size and number of bitstreams to which the tests are applied to be controlled. The focus of the tests is on applications where randomness is required for cryptographic purposes. NIST-STS is one of the most widely used and standardised batteries of statistical tests.
The TESTU01 package of statistical tests [3, 4] contains five pre-defined batteries of statistical tests. The SMALLCRUSH battery is small and fast and may be used as a first step in detecting gross defects in RNGs or errors in their implementation. The battery includes 10 statistical tests returning 15 test values and requires slightly less than 8 Gbits. The CRUSH battery contains more stringent tests. The battery includes 96 statistical tests returning 144 test values and requires close to 1.1 Tbits. The BIGCRUSH battery contains the most stringent tests. The battery includes 106 statistical tests returning 160 test values and requires close to 9 Tbits. The remaining two batteries, ALPHABIT and RABBIT, include, respectively, 9 and 26 statistical tests returning, respectively, 17 and 40 test values. The numbers of bits to be tested by these batteries can be controlled.
Read more
1. Ent: A pseudo-random number sequence testing program
2. A statistical test suite for random and pseudorandom number generators for cryptographic applications
3. TestU01: A C library for empirical testing of random number generators
Don’t see what you are looking for? Our diverse skill set enables us to provide bespoke solutions. Please contact us to discuss your requirements.
Contact us