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 (for example, 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. It might be possible to convert a PRNG that isn’t high-quality 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)8. 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

  1. Salmon, John K., Mark A. Moraes, Ron O. Dror, and David E. Shaw. “Parallel random numbers: as easy as 1, 2, 3.” In Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis, pp. 1-12. 2011. 

  2. Agner Fog, “Pseudo-Random Number Generators for Vector Processors and Multicore Processors”, Journal of Modern Applied Statistical Methods 14(1), article 23 (2015). 

  3. A permutation function (or bijection) is a reversible mapping from N-bit integers to N-bit integers. Examples include: JSF64 by B. Jenkins; MIX and MIX-i (part of Tyche and Tyche-i); the Romu family by Mark Overton; block ciphers with a fixed key; mixing functions with reversible operations as described in “Hash functions” by B. Mulvey. 

  4. As P. Evensen shows, the choice of constant can matter for a given permutation function. 

  5. Blackman, D., Vigna, S., “Scrambled Linear Pseudorandom Number Generators”, 2019. 

  6. J. D. Cook, “Using one RNG to sample another”, June 4, 2019. 

  7. von Neumann, J., “Various techniques used in connection with random digits”, 1951. 

  8. Schaathun, H.G. “Evaluation of Splittable Pseudo-Random Generators”, 2015; Claessen, K., et al. “Splittable Pseudorandom Number Generators using Cryptographic Hashing”, Proceedings of Haskell Symposium 2013, pp. 47-58.