How good is LavaRnd?

To measure the quality of LavaRnd we used A Statistical Test Suite for Random and Pseudo-random Number Generators for Cryptographic Applications, as described in NIST Special Publication 800-22 (with revisions dated May 15,2001), in a specific test suite configuration that we refer to as the billion bit test suite.

Test Parameters

For our billion bit test suite, we used test parameters recommended by the NIST Special Publication 800-200. In the case where two or more different tests recommended different minimum values for the same parameter, the largest minimum value was chosen. In all other cases the guidelines were clear, unambiguous, and did not conflict with regard to recommended values. The following table summarizes the test parameters:

Note that streams refers to the number of test cycles and bit length refers to the size of the output buffer that each random number generator is expected to fill before a test can commence.

Billion Bit Test Suite

Types of Statistical Tests

The test suite referred to by the NIST Special Publication 800-22 performs the following types of tests. Note that several of these produce more than one result. In particular, these 16 types of tests typically produce 179 results per test cycle per generator.

1. Monobit Frequency
2. Block Frequency
3. Cumulative Sums
4. Runs
5. Longest Run of Ones
6. Binary Matrix Rank
7. DFT Spectral
8. Nonoverlapping Template Matchings
9. Overlapping Template Matchings
10. Maurer's Universal Statistical
11. Approximate Entropy
12. Random Excursions
13. Random Excursions Variant
14. Serial
15. Lempel-Ziv Compression
16. Linear Complexity

As supplied by NIST, the Approximate Entropy test was flawed in that every random number generator failed the test type every time. Even the Blum-Blum-Shub, proved to be a cryptographically strong random number generator consistently failed this type of test. As a result, our billion bit test suite ignored Approximate Entropy failures.

Ranking methodology

Failures reported by tests can be divided into 3 categories:

• proportional failures

  This type of failure occurs when a generator fails a type of test too often. The NIST guidelines define a tolerance, a level of confidence, beyond which a sample of generator output can be said to not have come from a true random source.

  A generator with a proportional flaw cannot be cryptographically strong.

• uniformity failures

  This type of failure occurs when a generator fails in an inconsistent way. A generator can pass a type of test often enough to avoid being declared proportionally flawed, but be declared a uniformity failure due to otherwise inconsistent behavior. For example, having a few spectacular failures occur could produce a uniformity failure declaration. A generator that experiences periods of poor statistical performance between periods of otherwise excellent statistical performance would likely be declared a uniformity failure.

  Cryptographically strong random number generators are consistent and will not exhibit statistically significant uniformity failures.

• % of test failed

  A finite amount of generator output from any generator will sometimes fail a test. Even chunks of random data from a true random source will sometimes fail a test. The existence of a failure does not mean that the generator is flawed.

  A cryptographically strong random number generator will infrequently fail a test.

Random Number Generator Quality Classifications

We classify a high quality random number generator as a generator without any proportional or uniformity flaws. Cryptographically strong random number generators and Cryptographically sound random number generators are high quality generators.

We classify a generator with only a few uniformity flaws and no proportional flaws to be of medium quality. Such a generator cannot be said to be to Cryptographically strong.

An abundance of uniformity flaws or the existence of proportional flaws in a generator classifies it as being of poor quality.

Rankings

Here we present the random number generators grouped by quality classification as a result of performing the tests.

Random number generators that have a similar number and types of flaws may be regarded as being similar in quality. A generator that shows 1 to 3 uniformity flaws may be regarded as being of similar in quality to another generator that also shows 1 to 3 uniformity flaws.

Proportional flaws are more serious than a uniformity flaws. A generator that has 2 uniformity flaws is likely to be better than a generator that has 1 proportional and 1 uniformity flaw.

We present the % tests failed column to help finely distinguish between generators within a given quality group. Differences between the % tests failed values are far less important than the differences in the type or number of generator flaws discovered. For example, a generator with 0.199% tests failed and no flaws should be regarded as having a noticeably higher in quality than a generator with 0.193% tests failed and a uniformity flaw.

Each of the random number generators were subjected to at least 8 billion bit test runs. Each billion bit test run tests 1 billion (1000 million) bits of a generator. The results below are a result of testing at least 8 billion (8000 million) bits of random number generator output.

The % tests failed column represents an average of all of the billion bit test runs. The generator flaws column lists the complete list of proportional and uniformity flaws that were detected during the multiple billion bit test runs.

High Quality Random Number Generators

The high quality random number generators listed above did not exhibit any proportional or uniformity flaws over the course of 8 (or more) billion (8000 or more million) bits of output.

In addition to LavaRnd being at the top of the high quality classification, we note that it is unique among the generators tested. All of the other generators in this classification are pseudo-random number generators that can suffer from seed generation, seed disclosure, and seed search attacks. LavaRnd's chaotic source, which is both non-deterministic and generates a large range of values, cannot suffer from these problems.

Medium Quality Random Number Generators

The existence of uniformity flaws indicates that the medium quality random number generators listed above are not cryptographically strong random number generators.

Poor Quality Random Number Generators

The multitude of flaws found in these generators suggest that they should not be used when statistical quality is an issue.