rand() in C, rand() in PHP, Math.random() in JS.
Any use case where you want a poor random number generator is a niche use case and you can write your own. We should be secure by default.
This scenario corresponds to JavaScript engines of major Web browsers.
> CSPRNGs actually have slightly worse distributional properties than some much faster PRNGs, because the CSPRNG is more focused on being unpredictable.
What does this even mean? Non-uniform distribution for CSRNG is fatal. What is an RNG that has "better" distribution than CSRNG?
The actually relevant aspect is what percentage of a simulation's time is spent generating random numbers if it's using a CSPRNG. I have had this become a bottleneck in my work, and it's very rare to use CSPRNGs in scientific simulations for this reason.
> What does this even mean? Non-uniform distribution for CSRNG is fatal. What is an RNG that has "better" distribution than CSRNG?
There are distributional properties other than uniformity, and depending on how you use these numbers (e.g. Monte Carlo kernel form) these can be far more important than linear uniformity. The author briefly mentioned this in the article ("CSPRNGs emphasize unpredictability over all other measures of quality, some of which might be more important for your use case"). Look into the work of George Marsaglia, he wrote the test suites that generate the quality numbers most engineers use to evaluate both CSPRNG and normal PRNGs.
By the way, I think I've said this before, but I'll say it again. I really dislike the usage of the term 'CSPRNG' in these discussions. A CSPRNG is typically understood to be /dev/urandom---an algorithm that not only generates a long sequence of numbers, but also harvests entropy and tries to achieve forward and backward security. But it is also sometimes overloaded to mean a stream cipher, which is a conceptually simpler construct, and also able to be much faster. Stream ciphers can definitely compete in performance with things like Xorshift.
Not really. In general, the statistical tests are chosen such that when the law of large numbers comes into force, a perfectly random sequence would pass them with flying colors. If repeated runs of a perfect random number generator were failing these with a frequency that were improbable (i.e. far outside what the central limit theorem would predict), I think it would be safe to say the universe was playing a trick on you. Many of these are very closely related to predictability in practice as well. Uniformity is a statistical test, and I think it's probably the lowest bar you can set for "unpredictable".
The fundamental issue with measuring "randomness", especially for a PRNG, is that there is no set definition of information entropy suitable for calculation. Shannon entropy requires you to have a (possibly numerically sampled) PDF. The problem with that is that is you want to find the entropy of a sequence, you can't use the PDF of all the bytes you've gotten out the generator, since that PDF will have 1 for the exact sequence you obtained, and zero everywhere else. If you do it by multiple runs, there is no way you'd get enough data to construct an accurate PDF with a suitably large sample size. You have to use something based on highly subdivided sequence of values, but if you only look at each value in isolation you will only determine the uniformity with some small bin size, which ignores patterns due to proximity of values in the output.
So generally entropy is calculated using a more complex probability kernel, like the ones used in these statistical tests. But none of these can possibly be perfect. The "perfect" measure of entropy is Kolmogorov complexity[1], which captures the minimum length of a program you would need to be able to print the given output. On top of being undecidable in general, and also unobtainable in practice, you can show an upper bound of the Kolmogorov complexity on a CSPRNG that is actually quite low. Just take the algorithm the CSPRNG uses, plus any external entropy it got (from hardware interrupts, etc.). So in the end, various kinds of statistical tests are the only ones that make sense.
The actual goal of a CSPRNG is far more specific than just simulating a truly random sequence, which is why it differs from those used in simulations. It is unpredictability, defined by trying to make it so this short program which can generate all the output is impossibly hard to obtain from just the output in practice. In a vague sense, it is like (some of) the desired properties of a hash or cipher; we can't use a perfect random source (resp. one time pad), so let's get something that will take an impossible amount of computational power/measured output to break (resp. ciphertext using the same key), and mix it in with some as true random as we can get seed (resp. IV), and then mix some more in from time to time to make it even harder (resp. changing keys). That is the reason stream ciphers, while generally not as good as /dev/urandom-style CSPRNGs, are actually closely related enough that I think it's fair to call them CSPRNGs as well. They're just ones with a far worse algorithm/entropy source.
A statistical test _is_ a distinguisher! This seems self-evident to me. When the test repeatedly fails (with an extreme p-value or whatever criteria you want to apply here for 'failure'), you have successfully distinguished the sequence from random. Also you seem to misunderstand what I meant by equidistribution---uniformity is a different property, and of course crucial. I am puzzled, then, as to why you claim some generators are more 'uniform' than cryptographic ones.
Any pseudorandom bit generator whose next bit cannot be predicted in under 2^n "operations" also passes _all_ statistical tests that require less than this computational effort. This is a well-known result by Yao. In other words, unpredictability and indistinguishability are equivalent. In the case of, e.g., AES-CTR, n = 64 (birthday-bound distinguishers force it to be 64 instead of 128).
Your philosophizing about what true randomness really is does not strike me as very useful for practical purposes. Given unbounded computational power, obviously no such algorithm is actually indistinguishable. But who cares?
I'll repeat once again that I do think people should generally default to CSPRNGs, but I really don't understand why everyone involved in crypto insists that there are no valid use cases for non-CS PRNGs / that CSPRNGs are uniformly better for all use cases when it seems very obvious to me that they are not. I don't see any reason why a good PRNG and a good CSPRNG shouldn't exist in every standard library. Am I missing something?
As to why we insist that cryptographic primitives are uniformly better? Well, that is more subjective. I personally believe that they have gotten fast enough that the set of cases where they are unacceptably slow is vanishingly small, and the trend is clearly on the side of crypto getting faster. And I can sleep at night knowing that my results are not wrong due to some unknown, unexpected, property of my generator.
Another case where a long cycle length is useful would be the sort of scenario in my post, at much larger scale. If you have thousands of machines re-seeding at every service restart and then generating sequences of millions or billions of random numbers from a sequence, and you want a vanishingly small probability that those sequences will never overlap, could you use a CSPRNG?
Re: the generator properties, do you _really_ believe that? I mean, good non-CS PRNGs usually have fairly rigorous presentations and pass statistical tests. They aren't as sexy as crypto stuff, and maybe don't get the eyeballs, but they're relatively straightforward proven math whereas all of the CSPRNG results are based on conjecture. It seems at least as likely that some unexpected property of a CSPRNG will be discovered, a la RC4.
I do believe that. RC4 is a good example, actually; the unexpected properties that make RC4 be considered completely broken for cryptography are considered irrelevant for simulations (I won't swear by this, but I'll bet that RC4 passes all of TestU01's tests). The standards are just so much higher for cryptographic primitives. I'm sure unsexy generators can be suitable to this or that application. But due to the ad hoc nature of the statistical tests used, you can't be sure that your generator is not oddly correlated with a concrete application. I've written a comment a few days ago---on a thread very similar to this one---about a real-world case of this happening [1].
From a cryptanalysis standpoint I think that's consistent -- the probability of generating any particular single shuffle is astronomically low, so the difference between the actual probability and 0% is probably outside the realm of what's computationally feasible. But with something like MT19937 I can show that its at least possible for every outcome to have a non-zero probability. Perhaps this is just interesting academically, but maybe not if you're actually playing a card game for instance?
In particular, if there were some 0 <= y < 2^128 such that AES_k(x) != y for all 0 <= x < 2^128, then there must also be some z such that two different values x1 and x2 encrypt to the same value, which can't happen if AES is reversible.
You have already covered the distinction between guaranteed equidistribution and not, so I don't think there is much to add there. I do think the concern is mostly academic, since the difference between a subsequence that doesn't exist and one that will never be reached before the universe collapses is irrelevant to the user. I will note that Richard Brent, someone who is much better qualified than I to discuss this, has argued against the usefulness of equidistribution: http://maths-people.anu.edu.au/~brent/pub/pub240.html
edit: By in theory I mean that with enough computation resources you could break them even if you didn't find some new, clever weakness. Not that you could break them in theory because a weakness could always be found.
These characteristics don't just make Monte Carlo simulations converge quicker, they also do things like guarantee that your 52 deck shuffle will definitely produce the one shuffle that gives player two a royal flush on the flop in a round of texas hold 'em. Or, more generally, they guarantee that your Array.shuffle() method is unbiased for a reasonable sized array. In general you need true randomness and/or a long cycle linear-transformation PRNG to make those sorts of guarantees. It's also nice that they're fast. That said, I do also agree that the scenarios in which these things matter are rather rare, and most people should probably just use a CSPRNG by default.
Do you really think a CSPRNG is fast enough for your standard library's array shuffle though? Wouldn't you rather have something like xorshift1024* that's probably > an order of magnitude faster? Maybe a CSPRNG is fast enough... I don't have all the numbers. So this is an honest question.
CSRNGs make good general-purpose-use guarantees, because those who don't demand much of their RNG will enjoy "living in ignorance" of RNG trade-offs while getting the right set of guarantees so as to never accidentally generate a collision; while those who don't want the particular set of guarantees a CSRNG makes will be domain experts (i.e. people who have profiled their code and noticed that the RNG is the hotspot) who know what they need instead.
The same cannot be said if you make a non-CS PRNG the default. There, "living in ignorance" will result in disaster (as in the article); and just knowing that the provided PRNG isn't right for you doesn't imply you know what you do need.
I totally agree! Very few applications will notice if the random number generation takes 100 times more/less time. My point wasn't that CSPRNGs shouldn't be the default, it was that there definitely exist real situations where CSPRNGs are both not fast enough, and don't maximize the right kind of (domain-specific) quality.
The more vexing aspect is that many default random number generators are both slower and much, much worse than some really simple (we're talking 10 lines of C) PRNGs that out score them in every measure of quality. This is a choice that makes absolutely zero sense.
How much faster do you need your RNG to be in any non-niche situation?
Interestingly according to https://bocoup.com/weblog/random-numbers Firefox is just going to use its CSPRNG once the crypto api is ready. (Bug 322529 is still in NEW state, though.)
Depends on how you're using them. If you only care about collisions, and you're not worried about an attacker trying to manipulate your system, then using a PRNG whose output is well-distributed (read: not necessarily a language's random function) is fine. The problem is most language's default PRNGs are complete crap :(
edit: grammar
Seems like V8's Math.random was only fine for extremely trivial cases (Google doodle Pacman I guess). Meanwhile Webkit has been using a CSPRNG and nobody seems to be complaining.
V8 is a great piece of work but it was never intended for anything beyond speeding up web pages. Why are people using node.js on the server side at all, when there are more industrial strength runtimes with better performance available?
We fucked up by not vetting the algorithm, that's definitely the primary lesson here. Mea culpa. I'm sure you would have done things differently, but V8 is a modern system and I don't think assuming a modern PRNG was completely unreasonable while quickly getting to MVP at a new startup.
Bingo. Exactly.
I heavily criticized you in another post for 1) your initial choice of substandard algorithm and 2) your rationalizations (e.g. Google's "good reputation").
But that is ancient history. Here you're admitting that you fucked up, which IMO you didn't admit previously.
Also, kudos for your article which kicked off this entire discussion. In that article you showed that you carefully analyzed what was happening, how you went wrong, and how you could improve.
Even more important, you did this all publicly, both your article and your responses here on HN. Everyone learns from this. I commend you for your openness.