# What tests can I do to ensure my random number generator is working correctly?

In the past I have used the Chi-squared test to check the statistical randomness of my generator. Is this a good test to use? Are there other tests?

• There are no tests that can prove your PRNG works random - only those that can prove the opposite. – asd Aug 27 '11 at 21:21
• @asd To be pedantic, a test suite can show overwhelming probability that a number stream is from a bad PRNG/DRBG, no amount of testing can prove that it isn't random, it can suggest it very strongly. Dieharder for example is created with the knowledge in mind that it may take a lot of testing before you can show the PRNG is probably not random. Likewise, only testing 10MB of data may give you the false impression that true random isn't just that. – Iam Nick Feb 29 '16 at 19:53
• Johnston's Random Number Generators focuses mainly on cryptographically secure PRNGs, and has a great deal of material on testing. – Mars May 8 '19 at 17:59

Section 5.4 "Statistical tests" of Handbook of Applied Cryptography lists several such tests. However, note that if you're after a provably secure PRNG, such tests are far from being perfect.

For a provably secure PRNG, you need to formally prove the indistinguishability of its output from a truly-random sequence. See chapter 3 of Foundations of Cryptography for more info.

Checking statistical randomness is a semi-good test. What I mean by that is that if a given PRNG does not look good statistically, then it is utterly proven to be pure junk. On the other hand, good statistical randomness does not tell you much with regards to cryptographic security. Cryptographic security is about whether the PRNG output could be predicted by a sentient attacker who knows the in and outs of your algorithm (but not its internal state). Statistical randomness is about whether the PRNG output could be predicted by a trained monkey.

"Diehard tests" used to be popular for testing non-cryptographic PRNG. During the AES competition (a dozen years ago), NIST ran them on all AES candidates, and found nothing, and the general opinion among cryptographers was that it was mostly a waste of time.

A Linear Feedback Shift Register has handsome results with Diehard -- and using it for cryptography is immediate failure.

• Are you saying that verification of the design should be sufficient and that statistical tests are insufficient to verify operation? – this.josh Aug 13 '11 at 4:44
• It does not harm to run statistical tests; if they detect a bias then you can forget your design, and restart from scratch. But almost all weak designs will pass the tests with no bias. To verify if a cryptographic algorithm is secure, the only known efficient test is to have at least a few dozen cryptographers try to break it for a few years. – Thomas Pornin Aug 13 '11 at 4:49
• NIST has its own test suite, called "Statistical Test Suite" (STS). It is downloadable from csrc.nist.gov/groups/ST/toolkit/rng/documentation_software.html. – M.S. Dousti Apr 23 '12 at 19:36
• dieharder includes the diehard tests and can be run easily on Ubuntu without compiling or anything. – endolith May 1 '12 at 15:42
• @this.josh Although this is an old question, the answer would be yes, if you replace "should be" with "is the only way". Statistical tests prove nothing about security at all. Here's a metaphore: Say you want to find out if a car can go beyond 220 km/h or not. The equivalent of a statistical test would just be able to tell if that car has wheels or not. It doesn't adress the question, and it can only filter out those which could never ever possibly be secure. – tylo Nov 4 '16 at 17:05

What tests can I do to ensure my PRNG is working correctly?

That depends on what exactly you mean by “working correctly”.

You can do statistical tests to check for various statistical flaws your random number generator might be subject to, but you have be aware of the fact that statistical testing cannot serve as a substitute for cryptanalysis… meaning: when it comes to cryptographic security, you’ll have to dive into cryptanalysis, like I described in another answer to a somewhat related question.

Are there other tests?

Of course… besides the Chi-squared test you already know and mentioned in your question, there are whole batteries of statistical tests available! All you have to do is to pick your favorite poison:

• Dieharder
http://www.phy.duke.edu/~rgb/General/dieharder.php

Dieharder – my personal favorite – incorporates all of George Marsaglia's Diehard tests, as well as all the tests from the NIST STS (Statistical Test Suite developed by the National Institute for Standards and Technology), and some additional tests developed by rgb.

• TestU01
http://simul.iro.umontreal.ca/testu01/tu01.html

Another battery of tests, comparable to Dieharder. It provides general implementations of the classical statistical tests for random number generators, as well as several others proposed in literature, and even some original ones. Some claim that – sooner or later – TestU01 will make every RNG fail at least one of it’s test, no matter what RNG you throw at it. But failing a test does not immediately indicate a flaw in the individual rng, as some tests will produce more exact results when adhering to the specific requirements of those tests (eg: feeding them enough RNG output).

• This is the official battery of statistical tests which NIST provides. The STS (Statistical Test Suite) is available as a download via the NIST website and details about it are described both on their website as well as in their related paper "NIST SP 800-22, A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications" (PDF).

• Diehard
http://www.stat.fsu.edu/pub/diehard/

This is what I would call the “old classic”. Diehard represents a battery of statistical tests, developed by George Marsaglia and first published in 1995 on a CD-ROM of random numbers. While Diehard itself may have come of age, the tests surely haven’t. Both Dieharder and TestU01 include Marsaglia’s tests.

There might be other solutions out there which may or may not be interesting to look at, but – to limit the scope to a usable level – I decided to only mention some of the (more prominent) statistical test suites.

Tests of randomness with only data as input can give proof of non-randomness, but never a credible indication of randomness unless their result is coupled with an analysis of how the random data tested has been generated. Without such knowledge, such tests give a falsely reassuring PASS, or a FAIL.

Illustration: consider the PRNG that outputs 512-bit blocks computed as the HMAC-SHA-512 of the previous block under some key. That pass any randomness test for one not knowing the key, yet is trivially predictable from past output with that knowledge.

In cryptography, randomness tests with PASS result can only be useful when and if we have a model of the source tested. This is at the heart of the AIS 31 methodology of Common Criteria evaluation for True Random Numbers Generators; see there (under AIS 31; in German, but with links to many documents in English and a Reference implementation of the statistical tests).

This AIS 31 methodology is routinely used in things like Smart Cards, and referenced in certification reports like this and this. It is made some model matching the device, and justified that per that model, any likely defect that do not raise alarm won't result in using a significantly predictable bitstream. Typically there is:

• a TRNG based on some analog phenomenon, e.g. sampling of a noise source, delivering a bitstream that can be sampled for testing purposes;
• hardware or/and software testing that source, at startup and/or runtime, in order to check that this source delivers entropy; including, at least, some test that raise alarm if anything makes that source totally defective (that could be an attacker with a needle, a laser, evaporation of some liquefied gas..);
• a hardware or/and software conditioning of the output of that source, into another bitstream, that won't have discernible bias even if the source is only passable; that conditioned bitstream can be used e.g. as source of randomness for DPA countermeasures, or a key generator.
• possibly, an additional test that conditioning works as intended.
• Thanks for porting over you answer from the dupe Q. Just wanted to ping you, asking if you would be willing do so. Spares me from bugging you via chat... ;) – e-sushi Nov 4 '16 at 16:49