Tell me more ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.
up vote 6 down vote favorite
1

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?

share|improve this question
Hmm. Either you're talking about the statistical or cryptographic aspects of randomness. If the latter, you should make it clear. If the former, this is probably the wrong forum and the answers reflect that. – Jason S Aug 13 '11 at 1:37

3 Answers

up vote 5 down vote accepted

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.

share|improve this answer
up vote 3 down vote

There are no tests that can prove your PRNG works random - only those that can prove the opposite.

share|improve this answer
up vote 11 down vote

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.

share|improve this answer
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
3  
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. – Sadeq 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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.