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 Pseudorandom Number Generators for Cryptographic
Applications, as described in
NIST Special
Publication 80022 (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
800200.
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 
nonOverlapping 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.
Pseudorandom 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 80022
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.
 Monobit Frequency
 Block Frequency
 Cumulative Sums
 Runs
 Longest Run of Ones
 Binary Matrix Rank
 DFT Spectral
 Nonoverlapping Template Matchings
 Overlapping Template Matchings
 Maurer's Universal Statistical
 Approximate Entropy
 Random Excursions
 Random Excursions Variant
 Serial
 LempelZiv Compression
 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 BlumBlumShub, 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
Generator  % tests failed  Generator flaws 
LavaRnd 
0.175% 
(none) 
BlumBlumShub 
0.192% 
(none) 
ANSIX9.17 
0.196% 
(none) 
SHA1 Generator 
0.196% 
(none) 
MicaliSchnorr 
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
pseudorandom number
generators that can suffer from seed generation,
seed disclosure, and seed search attacks.
LavaRnd's
chaotic
source, which is both nondeterministic and
generates a large range of values, cannot suffer from these problems.
Medium Quality Random Number Generators
Generator  % tests failed  Generator flaws 
BSD libc random 
0.199% 
DFT Spectral (uniformity)
Overlapping TemplateMatchings (uniformity)
LempelZiv Compression (uniformity)

DES 
0.200% 
LempelZiv Compression (uniformity)

Quadratic Congruential II 
0.206% 
DFT Spectral (uniformity) 
OS X 10.3.5
/dev/random 
0.207% 
DFT Spectral (uniformity)
RandomExcursion (uniformity)
LempelZiv Compression (uniformity)

BSD libc rand 
0.209% 
DFT Spectral (uniformity)
LempelZiv Compression (uniformity)

FreeBSD 5.2.1
/dev/random 
0.210% 
DFT Spectral (uniformity)
RandomExcursion (uniformity)
LempelZiv Compression (uniformity)

Linux 2.4.18
/dev/random 
0.212% 
DFT Spectral (uniformity)

Solaris 8 /dev/random
patch 10852818 
0.213% 
LempelZiv Compression (uniformity)

Linear Congruential 
0.216% 
DFT Spectral (uniformity)
LempelZiv Compression (uniformity)

Linux 2.4.2120.EL
/dev/urandom 
0.216% 
DFT Spectral (uniformity)
LempelZiv 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
Generator  % tests failed  Generator 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)
LempelZiv 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)
LongRun (uniformity)
Overlapping Template Matchings (uniformity)
LempelZiv Compression (uniformity)

Microsoft VB.NET v2.0
Windows XP
noncryptographic 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)
LempelZiv Compression (proportion)
LempelZiv Compression (uniformity)

Microsoft VB.NET v2.0
Windows XP
noncryptographic 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)
LempelZiv Compression (proportion)
LempelZiv Compression (uniformity)

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