How to test a random number generator (2010)
johndcook.com
johndcook.com
It seems to me that any new non-cryptographic PRNG should be required to test itself in this manner, or else provide a very good excuse.
> In empirical testing, a classic is the Diehard program by Marsaglia. That program is badly outdated today and should not be used anymore, but it was, so far as I know, the first real standardized battery of such tests.
More information is available on their website: http://pracrand.sourceforge.net/PractRand.txt.
- L'Ecuyer's TestU01 (with SmallCrush, Crush, BigCrush), and
- Doty-Humphrey's pracrand with its PractRand suite
The problem is that these test suites are not very comprehensive and while they're OK for discerning an obviously broken RNG, they're not good to vouch for an RNG in general. That is to say, it is fairly easy to write an RNG that passes these test suites despite having some very predictable and easily detectable patterns that you'd find if only you wrote a test that looks for that particular pattern. Kinda like these suites have hyperplane tests to detect LCGs.
There's an old saying about anyone being smart enough to invent crypto they are not smart enough to break themselves. As far as designing RNGs goes, doing one against existing test suites is pretty low bar. I think we can afford a little more theory backing non-cryptographic PRNGs too.
I wouldn't give these test suites so much credit; they're tools for detecting known flaws or broken implementations. That's all.
For the theory around periods, distribution and jumping it can just refer to these properties for LCG's, which are very well studied.
Testing an RNG design against the statistical test suites TestU01 and PractRand seems on first intuition the be the wrong way to go about it. First you should have a theory behind the RNG, and only then test it.
And to me it seems PCG does just that. The various output functions are carefully designed. Which bits are the best and which are the weakest for an LCG? The worst bits are dismissed. How can the best bits be used to pick permutations of the remaining bits? The output functions are well designed, but you will have to watch the video or look at the C++ source to see the theory behind them.
Then just about all known tests and theory to differentiate between true randomness and the results of an RNG are applied. Which are handily packed into test suites. That is the way to look at these tests. Not some sort of specific, arbitrarily chosen test. This is not the situation of Javascript engines that may get optimized to much for some arbitrary benchmark.
And those test where run against severely weakened versions of PCG, just to be sure the tests don't accidentally pass.
But you have a good point: designing solely against test suites is not a good idea. A result are Xorshift128+ and Xoroshiro128+. Even with some theory behind it, they are the result of varying constants until they do not fail any test on BigCrush too consistently. It may even sometimes pass, and that is what is claimed on for example Wikipedia. But along comes another test suite, PractRand, and it fails within a second of testing. It is optimized for BigCrush, but not really statistically good.
Unless the competition is actually using rigorous mathematics to talk about their statistical quality, and as far as I can find they are simply not[1], being empirically better is the only thing to argue about! Thus if O'Neil's approach finds weaknesses in the competitor's tested generators earlier[2], it's a stronger test.
Even from the angle of unknown, theoretical attacks, competitors almost always build on trivially invertible functions, so you cannot expect them to be robust against generalized tests. The inverse transformation is always weak, so if this is trivial they cannot be robust against general classes of correlations.
Unless you can actually show a (useful) non-cryptographic RNG that makes good justifications for its strength in formal terms, which I doubt you can, you're basically left with the fact that the PCG family is the only robustly vetted family in practice.
If that isn't good enough for you, there's always ISAAC.
[1] https://cs.stackexchange.com/questions/50059/why-is-the-mers...
[2] http://www.pcg-random.org/posts/visualizing-the-heart-of-som...
Also, I think the final line in this text (”Correct generators usually pass tests, and buggy generators usually fail.”) is at least dangerously misleading.
Firstly, I would use good/bad, not correct/buggy, but that is minor. My major issue is the idea that bad generators usually fail. Only really bad generators usually fail. Somewhat bad generators fail tests less often, and only slightly bad generators can pass many, many tests, only to show their weakness in some particular setting.
For example, if I take the output r1,r2,r3… of a good generator and swap r1 and r2 if r1>r2, r3 and r4 if r3>r4, etc. the result isn’t truly random, but will pass many tests.
If you suspect your generator to have this problem, it is extremely easy to test for it, but if you don’t, that may be hard.
A good array of tests will test subsequences, and find this easily (the average of the odd samples will typically be less than expected, and the average of the even samples will typically be larger)
It mentions the DIEHARD test near the beginning. Try ctrl-F.
I don't think it's really meaningful to point out that a bad RNG will pass many of the constituent tests of a particular test battery (e.g. diehard), because each constituent test is generally looking for one particular property.
"Most testers will be concerned with the second step of the grand strategy: testing code that transforms uniform random sequences into sequences with other distributions. Although very few people develop their own uniform generators, many people have reasons to develop custom nonuniform generators."
From a performance perspective there are vanishingly few applications where the difference between MT or PCG and AES-CTR is going to make an ounce of difference. Once the question of performance is settled, there simply don't remain any arguments in favor of using PRNGs.
csprng: 909 ns/Op
Xorhift128+: 2 ns/Op
Xorhift128+ is what all major JS engines use for Math.random().
I don't think it's a good idea if you use a CSPRNG if there isn't any reason for that. Especially if you need a lot of random numbers. E.g. a game might drop some additional frames here and there and your particle effects won't look any better and your AI won't behave any smarter either.
Not to use PRNGs ever is bad advice.
OK, go ships a lousy csprng. I've been asking the team to replace it but no one has gotten around to it. AES-CTR, for example, is competitive with Xorshift and Xoroshiro.
> Xorshift128+ is what all major JS engines use for Math.random().
Only because two years ago Yang Guo noticed that MWC1616 was garbage. Up until that point engines were shipping a broken generator because someone had been clever. This failure mode happens again and again. java.util.Random, for example.
> I don't think it's a good idea if you use a CSPRNG if there isn't any reason for that
Using insecure random sources opens you up to all sorts of attacks that CSPRNGs insulate you to.
> Especially if you need a lot of random numbers
Over the past year I profiled a huge number of binaries. I found exactly one where fetching random numbers was over 1% of CPU consumption.
> your particle effects won't look any better
Your particle effects are probably running in a shader. That's a whole other ball game.
> I found exactly one where fetching random numbers was over 1% of CPU consumption.
Again, Monte Carlo simulation is the obvious exception, and it is a huge, important field and big consumer of random numbers. Stochastic algorithms (see Sebastian Thrun's Probabilistic Robotics) might be another example.
However, one big problem is that many benchmarks basically benchmark the PRN generation, and so incentivise vendors to default to fast PRNG. And I agree with you, the default should be a CSPRNG.
Lastly, on a side note, I seem to recall that some generators from Vigna's Xoroshiro family suffer a very low quality least significant bit. Not sure whether Xorshift128+ is among them.
EDIT to add more:
BTW, it's surprisingly hard to get researchers in PRNG to give clear, unequivocal recommendations for users. They'll often resort to some version of "it depends" (or plug their own).
Lastly, let me plug my related stackoverflow answer:
https://stackoverflow.com/questions/4720822/best-pseudo-rand...
It depends. :) Even then very few realistic simulations are going to be RNG bound. Even fewer of those are going to care about the difference between Xoroshiro and AES-CTR (with AESNI).
A common failure mode I've seen is programmers picking Mersenne Twister and then assuming initialization is cheap.
> suffer a very low quality least significant bit
IIRC, the LSB behaves like a LFSR.
> it's surprisingly hard to get researchers in PRNG to give clear, unequivocal recommendations for users
There are about five PRNG researchers in the world and few (none?) of them are doing it full time. L'Ecuyer, the biggest name since Marsaglia died, seems to be dealing with PRNGs mostly as a means to doing operations research.
(Side note: Pierre L'Ecuyer is very likely the strongest over-50 cyclist in Quebec.)
However, I do agree that programming languages these day should probably make a CSPRNG the default, and let you switch to a fast PRNG when needed. (Now it's by and large the other way around – you get a fast PRNG and need to switch to a secure one.)
If you know what you're doing, the outcome is the same, but if you don't, in the first case you're unnecessarily slow, while in the second you're unnecessarily insecure.
8/10 is nice if you want a handwavy human explanation of some rudimentary expectations in crypto
- author spends a few pages thinking about randomness - we have formal definitions of a RNG/PRNG.
- author does basic statistical tests, these seem very unconcerned with actual randomness - i'm not sure what the point is
- author really shouldn't be writing about crypto randomness if they don't do crypto
+1 to higher comment saying reading TAOCP instead.
> The idea of what constitutes a good RNG depends on how the RNG is applied. That is why, for example, a generator may be considered high-quality for simulation while being considered unacceptable for cryptography. This chapter looks at tests of statistical quality and does not address tests for cryptographical security.
f(i) = SHA256(i + salt)& http://xoroshiro.di.unimi.it makes reference to how on x86 cpus with AES one could get a very fast prng similar to how you're implying
As a change of 1 bit in an input ideally flips half the bits of the output for a cryptographic hash, this scheme should work
If you’re asking if you can make a good PRNG out of cryptographic primitives, yes, that’s what happens in the bowels of OS CSPRNGs. But a bit more involved.
See my related stack overflow answer:
https://stackoverflow.com/questions/4720822/best-pseudo-rand...
Software random number generators are technically
pseudorandom number generators because the output
of a deterministic program cannot really be random.