Hacker News Reader

Comment by SavantIdiot | Hacker News Reader

I've been working with the NIST 800-22 evaluation suite [1] and yes, it is very hard. There are an infinite number of tests to determine if a number is random. Ultimately it comes down to probability that it is a good RNG/PRNG and the application. Ironically, if a PRNG is good enough, it can often be BETTER than a random source (which is why RNGs have a conditioning phase).

[1] https://csrc.nist.gov/Projects/Random-Bit-Generation/Documen...

View on HN

An infinite number of tests yes, it is like trying to find the best possible predictor of a source. No statistical test can prove that a source has full entropy and uniformly distributed, only disprove it. These tests are too often misused and are usually not very useful since they tell us nothing about how much entropy might be in the sample, and entropy sources are always biased anyway and fail the tests, and if you condition them then they will always pass the test even if not random at all. A better method is to develop a stochastic model of the entropy source and attempt to estimate bounds on the entropy, which is still generally not feasible. The statistical tests can then be used as a sanity check to verify your entropy estimates. The RNG needs a conditioning phase, or entropy extractor to transform the output into a distribution that is indistinguishable from uniform as is needed in cryptographic applications and you should always include this stage because virtually no physical entropy source has a uniform distribution. The best thing to do is to try to gather as much entropy as you can from sources and gather maybe 10x what you think you need and then put it through an entropy extractor like a cryptographic hash function to generate a PRNG seed then use the PRNG.

> No statistical test can prove that a source has full entropy and uniformly distributed, only disprove it.

It can't disprove it either. It can only say if it is "likely to be random" or "appears to be random".

A perfectly random source could generate a string of 1M zeros, and most statistical tests would fail it. But that is not proof that it isn't random. A second test would likely not generate all zeros and would likely pass.

> A perfectly random source could generate a string of 1M zeros,

I you sample the thermal noise of the transistor used in your RNG too quickly you can get 1M zeroes. :)

Reply on news.ycombinator.com