Home
Eruption - What is LavaRnd?
Obsidian - FAQ
Lava - Demos
Lavaologists - About us
Strata - New and old stuff
Magma - Download
Bedrock - Developers

How good is LavaRnd?

Detailed Description of Test Results and Conclusions

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:

Test Parameter Value
bit length 1000000
blockFrequency Block Length 10
non-Overlapping Template Block Length 9
overlapping Template Block Length 10
universal Block Length 7
universal Number Initialization Steps 1280
approximate Entropy Block Length 14
serial Block Length 16
linear Complexity Sequence Length 5000
word Length 10
streams 1000

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

Our billion bit test suite subjected generators to 1,000 different test cycles. Pseudo-random number generators were given a unique seed at the start of every cycle. Each test cycle tested 1 million bits of random numbers which produced on average 179 statistical results. A single run of the billion bit test suite will perform approximately 179,000 statistical test results against a billion (1000 million) bits of random data.

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

High Quality Random Number Generators
Generator% tests failedGenerator flaws
LavaRnd 0.175% (none)
Blum-Blum-Shub 0.192% (none)
ANSI-X9.17 0.196% (none)
SHA-1 Generator 0.196% (none)
Micali-Schnorr 0.199% (none)

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

Medium Quality Random Number Generators
Generator% tests failedGenerator flaws
BSD libc random 0.199% DFT Spectral (uniformity)
Overlapping TemplateMatchings (uniformity)
Lempel-Ziv Compression (uniformity)
DES 0.200% Lempel-Ziv Compression (uniformity)
Quadratic Congruential II 0.206% DFT Spectral (uniformity)
OS X 10.3.5
/dev/random
0.207% DFT Spectral (uniformity)
Random-Excursion (uniformity)
Lempel-Ziv Compression (uniformity)
BSD libc rand 0.209% DFT Spectral (uniformity)
Lempel-Ziv Compression (uniformity)
FreeBSD 5.2.1
/dev/random
0.210% DFT Spectral (uniformity)
Random-Excursion (uniformity)
Lempel-Ziv Compression (uniformity)
Linux 2.4.18
/dev/random
0.212% DFT Spectral (uniformity)
Solaris 8 /dev/random
patch 108528-18
0.213% Lempel-Ziv Compression (uniformity)
Linear Congruential 0.216% DFT Spectral (uniformity)
Lempel-Ziv Compression (uniformity)
Linux 2.4.21-20.EL
/dev/urandom
0.216% DFT Spectral (uniformity)
Lempel-Ziv Compression (uniformity)

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

Poor Quality Random Number Generators
Generator% tests failedGenerator flaws
Quadratic Congruential I 0.704% Monobit Frequency (uniformity)
Monobit Frequency (proportion)
Cumulative Sums (uniformity)
Cumulative Sums (proportion)
Runs (uniformity)
Runs (proportion)
Modular Exponentiation 0.749% Monobit Frequency (uniformity)
Monobit Frequency (proportion)
Cumulative Sums (uniformity)
Cumulative Sums (proportion)
Block Frequency (uniformity)
Nonoverlapping Template Matchings (uniformity)
Runs (proportion)
Using BSD libc random to
seed another BSD libc random
0.881% Cumulative Sums (uniformity)
DFT Spectral (uniformity)
DFT Spectral (proportion)
Maurer's Universal (uniformity)
Maurer's Universal (proportion)
Cubic Congruential 1.219% Monobit Frequency (uniformity)
Monobit Frequency (proportion)
Cumulative Sums (uniformity)
Cumulative Sums (proportion)
Runs (uniformity)
Runs (proportion)
DFT Spectral (uniformity)
DFT Spectral (proportion)
Nonoverlapping Template Matchings (uniformity)
Nonoverlapping Template Matchings (proportion)
Block Frequency (uniformity)
Lempel-Ziv Compression (uniformity)
XOR Generator 1.326% Block Frequency (uniformity)
Block Frequency (proportion)
Binary Matrix Rank (uniformity)
Binary Matrix Rank (proportion)
Nonoverlapping Template Matchings (uniformity)
Nonoverlapping Template Matchings (proportion)
Maurer's Universal (uniformity)
Maurer's Universal (proportion)
Serial (uniformity)
Serial (proportion)
Linear Complexity (uniformity)
Linear Complexity (proportion)
Long-Run (uniformity)
Overlapping Template Matchings (uniformity)
Lempel-Ziv Compression (uniformity)
Microsoft VB.NET v2.0
Windows XP
non-cryptographic PRNG
Low order byte octet
Seed every 256 bytes
28.657% Monobit Frequency (proportion)
Monobit Frequency (uniformity)
Block Frequency (uniformity)
Cumulative Sums (proportion)
Cumulative Sums (uniformity)
Runs (proportion)
Runs (uniformity)
Longest Run of Ones (proportion)
Longest Run of Ones (uniformity)
DFT Spectral (proportion)
DFT Spectral (uniformity)
Nonoverlapping Template Matchings (proportion)
Nonoverlapping Template Matchings (uniformity)
Overlapping Template Matchings (proportion)
Overlapping Template Matchings (uniformity)
Serial (uniformity)
Lempel-Ziv Compression (proportion)
Lempel-Ziv Compression (uniformity)
Microsoft VB.NET v2.0
Windows XP
non-cryptographic PRNG
Low order byte octet
Seed once
31.672% Monobit Frequency (proportion)
Monobit Frequency (uniformity)
Block Frequency (uniformity)
Cumulative Sums (proportion)
Cumulative Sums (uniformity)
Runs (proportion)
Runs (uniformity)
Longest Run of Ones (proportion)
Longest Run of Ones (uniformity)
DFT Spectral (proportion)
DFT Spectral (uniformity)
Nonoverlapping Template Matchings (proportion)
Nonoverlapping Template Matchings (uniformity)
Overlapping Template Matchings (proportion)
Overlapping Template Matchings (uniformity)
Serial (uniformity)
Lempel-Ziv Compression (proportion)
Lempel-Ziv Compression (uniformity)

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

SourceForge.net Logo
Home  |   LavaRnd?  |   FAQ  |   Demos  |   About us  |   New & Old  |   Download  |   Developers  |   Tour