peteroupc.github.io

Testing PRNGs for High-Quality Randomness

Peter Occil

According to my document on pseudorandom number generator (PRNG) recommendations, a high-quality PRNG, among other requirements—

generates bits that behave like independent uniform random bits (at least for nearly all practical purposes outside of information security)[,]

a requirement called the “independence requirement” in this short document.

To determine whether a PRNG meets the independence requirement, its output should be sent to the PractRand program by Chris Doty-Humphrey and show no failures (“FAILs”) in the PractRand tests at 1 TiB (2^40 bytes) or greater. For more information, see “How to Test with PractRand” by M. E. O’Neill.

Random number streams. Many PRNGs use different strategies to produce nearby sequences (or streams) of pseudorandom numbers. But not every strategy produces independent streams. To determine whether nearby sequences of the PRNG meet the independence requirement, the output sent to PractRand should be formed by interleaving the outputs of those sequences (e.g., one output from the first sequence, one output from the second, another output from the first, another from the second, and so on).

There are several kinds of nearby sequences to test for this purpose:

The leapfrogging technique involves assigning N processes each a PRNG that differs from the last by 1 step, then having each such PRNG advance N steps, where N is the number of PRNGs, each time it generates a random number. However, note that testing nearby sequences produced by leapfrogging is redundant with testing the regular PRNG sequence without streams.

Hash functions and counter-based PRNGs. In general, a counter-based PRNG produces pseudorandom numbers by transforming a seed and a counter; with each number, it increments the counter and leaves the seed unchanged (Salmon et al. 2011)(1). The seed and counter can be transformed using block ciphers, other permutation functions, or hash functions. In general, counter-based PRNGs that use hash functions (such as MD5, SHA-1, MurmurHash, CityHash, xxHash) will meet the independence requirement if the following hash stream (for that hash function) doesn’t fail the PractRand tests at 1 TiB or greater:

  1. Write out the hash code of seed || 0x5F || counter (the || symbol means concatenation).
  2. Write out the hash code of (seed+1) || 0x5F || counter.
  3. Add 1 to counter and go to the first step.

In general, a hash function without PractRand failures is worthy of mention if it’s noncryptographic and faster than hash functions designed for cryptography, such as MD5 and the SHA family.

Combined PRNGs. As G. Marsaglia (in KISS), D. Jones (in JKISS), and A. Fog (2015)(2) have recognized, combining two or more PRNGs of weaker quality often leads to a higher-quality PRNG. A PRNG that isn’t high-quality could be converted to a high-quality PRNG in one of the following ways:

Other combinations and transformations. There are other ways to combine two PRNGs, or to transform a single PRNG, but they are not preferred ways to build a high-quality PRNG. They include:

Splittable PRNGs. A splittable PRNG consists of two operations: a split operation to create multiple new internal states from one, and a generate operation to produce a pseudorandom number from a state (Schaathun 2015; Claessen et al., 2013)(7). The Schaathun paper surveys several known constructions of splittable PRNGs. Some of the constructions can be used by any PRNG, but do not necessarily lead to high-quality splittable PRNGs.

The Schaathun paper suggests the following four random number sequences for testing purposes:

Notes