Monday, July 12, 2010

RadioGatún[32] passes all Dieharder tests

Dieharder is a series of tests to test the quality of random numbers. I have installed Dieharder 2.27.12 on my CentOS virtual machine (by virtue of the fact that this is the most recent version of Dieharder with handy precompiled 32-bit binaries) and then started running RadioGatún[32] as a stream cipher through this battery of tests.

The first time I tested RG32 (my shorthand for “RadioGatún[32]”), a couple of tests were marked as poor—which is not surprising, since the full battery is some 74 tests. When a tests is marked as being “poor”, that indicates that the stream of random numbers generated have a 1% or smaller chance of not being random. A good set of random numbers will occasionally fail a randomness test, since well-made random numbers sometimes do not quite look random.

I re-ran the tests that were “poor”, first with the same RG32 seed at a different point in its stream (which resulted in having a “possibly weak” result—a 5% chance the test was not random—for a different test, which is not surprising since there are 20 tests in this section of Dieharder), then with a couple of other RG32 seeds. With the third RG32 seed, none of the 20 tests were marked “poor” or “possibly weak”.

Conclusion: RG32 shows no biases when used as a pseudo-random number generator (PRNG). In practical terms: Deadwood is using a strong random number generator.

While I was testing the quality of RadioGatún’s random stream, I tried to run the tests at CAcert.at, but the server gave me an “Internal server error” instead of test results. I tried with two different sample sizes (one about 130 megs in size; the other about 18 megs in size).

I should note that RG32 is quite fast, even with the code-size-optimized implementation I made for Deadwood. Compiled with -03 in GCC, I got 20 megabytes of numbers in three or four seconds. cat /dev/null gives me 200 megabytes of zeros in the same amount of time.

Update: Using the rg32 seed (hash input) of “dieharder7&rdquo, Dieharder 2.27.12 passes all tests; again, random numbers should sometimes fail a randomness test, but they don’t with this particular seed and particular version of the full Dieharder test suite.