Hacker News Reader

Comment by nullc | Hacker News Reader

The design approach of just iterating until it passes a suite of statistical tests is ... not the best.

The issue is that the common suites of statistical test don't include every credible statistical test at their level of complexity.

Essentially as you retry against the tests you expend their utility, producing a result that is guaranteed to pass them as a byproduct of your process. ... but may in fact be extraordinarily weak to yet another reasonable statistical test (and/or broken in some practical application) that no one has yet thought to include in the test suite.

View on HN

Very true. Sadly, this is the main approach the non-cryptographic PRNG community has at the moment.

On the plus side, those tests are fairly extensive and brutal nowadays. They detect anomalies in cryptographic algorithms that were still used a decade ago, such as arc4random().

But one thing I hint at at the end is that I hope, and anticipate, to see more accurate quality measurement tools in the future.

A partial workaround is to reserve one or two of the tests until your PRNG passes the others.

If it passes the remainder on the first try, you might be on to something.

If it fails, you've got a problem: tweaking until it passes isn't going to help you.

I like your design, simple and elegant.

One thing I did when designing random functions is run them against DieHarder and Practrand, but then also against SMHasher, you just have to use some construction to fold the key into the state. I think that's a useful somewhat orthogonal way to test. have you considered this?

One alternative would be to attempt to select an analyzable structure which you could show through analysis should have good randomness properties. Potentially add a limited number of tweaks or parameters with the aid of just one or two general statistical tests (and perhaps a collection of pants-on-head stupid tests just to avoid wasting time on stuff that is utterly broken).

After that, you try with the complete suite and unless the result reaches a predetermined passing criteria you declare the design as flawed and go back to step 1 rather than continuing to tweak (as the result of continued tweaking will inevitably be a pass even if the design is poor).

Unfortunately, high performance and even 'good random-like behavior' may be at odds with having a construct which is transparent enough to be able to justify its performance from analysis rather than running it. :(

On the other hand, some tests could be aligned enough with the needs of a specific application and prove that a PRNG is good, not only probably good.

For example, if a game uses a PRNG to "stretch" a random seed for procedural generation purposes conditional probabilities are important (to avoid spurious correlations between features) but period is completely irrelevant (even a relatively short period would be many orders of magnitude larger than output size).

Yes, this seems like a relatively fundamental flaw. Even if the confidence of these statistical tests is something like p=0.000005, throwing enough experiments onto them almost ensures you get a false positive.

Why can't we check for overfitting using the usual ML techniques?

We know the tests are overfitting. That's not really a problem we can worry about too much; the tests can't be perfectly comprehensive and also finite. The problem is that we're using to use the model to tell us something about adversarial input.

I've always wondered, why not just run 10 different random number generators at once and ping pong between them or blend them or something?

That gets you the weaknesses of all of them modulo your selection criterion ... some of the time.

Depends on which method is utilized. “Ping ponging” would have issues as you’d run into all the problems of all of them.

Depending on how the “blending” is done and whether the algorithms are truly independent of each other, combining them is definitively more secure than any of them individually. The Linux kernel let’s you do this through writing to /dev/random. The written bytes get added (in part) to the entropy pool.

"Blending" multiple of them per iteration slows you down!

You can do that, but you will lose the "speed" part, obviously.

Reply on news.ycombinator.com