This is the Nth time this website has been promoted on HN. As far as I know, a peer-reviewed academic paper has not yet been published; one was withdrawn for strange reasons. The algorithm, and claims made on this website, have garnered some significant criticism.
Getting an RNG right is important. I'd not trust this method until other people in the field have verified that the author's claims are true and critics have been satisfied. The accepted method for this is peer review.
Getting a secure RNG right is important. PCG isn't a secure RNG; neither is xorshiro, xorshift, or MT. You can't use them anywhere security relies on not predicting future outputs from past ones. If you have to ask, don't use them.
The most confusing thing about PCG's documentation is its "challenging" level of prediction difficulty. That's not a thing. The PCG authors should not have compared ChaCha or Arc4random with their generator.
Other than that, I'm a little confused why anyone would care how good PCG is. We have adequate insecure RNGs already, and secure RNGs are already so cheap that they make a reasonable default.
But, whatever. If people want to golf who can make the best insecure random number generator, seems fine.
I think all these people complaining about PCG not being secure or the existence of a new insecure PRNG have never worked in simulations or HPC. Absurdly fast PRNGs that are reasonably well behaved are super useful in things like monte-carlo simulations and black-box optimization algorithms.
The AVX-512 version of PCG runs at around 4 bytes / CPU cycle. That's pretty hard to beat.
There are secure AEAD constructions that are <1cpb today, and they do extra MAC work that a simple PRF in a CSPRNG doesn't need to do. I'm sure PCG is faster, but for the overwhelming majority of applications, it's not so much faster as to matter; meanwhile, a fast CSPRNG also gives you security, which you might find you need later on.
Can you clarify this? A RNG is generating n bytes of output per cycle. An AEAD is consuming n bytes of input per cycle. And an AEAD doesn’t need to have uniformly random-looking output to be secure.
An AEAD is consuming n bytes of input per cycle and producing at least n bytes of output, that is, the output ciphertext plus tag.
The definition of authenticated encryption is, essentially, indistinguishability of the ciphertext plus MAC security of the tag. You're right, the tag does not need to be indistinguishable from random, but in the majority of the cases it is anyway.
One significant difference between these non-cryptographic generators and cryptographic ciphers is that of latency---generators often optimize for latency, whereas ciphers optimize for throughput. By taking a cipher and a sufficiently large buffer, you can have low latency as well, at the cost of some memory.
For comparison, consider MORUS, AEGIS, and Tiaoxin, three unbroken contestants of the CAESAR competition. MORUS uses only AND, XOR, and bitwise rotation, and achieves somewhere between 0.5 and 0.66 cycles per byte on current x86 chips. AEGIS and Tiaoxin use the AES round, and where AES-NI is available, performs at between 0.15 to 0.25 cycles per byte. The claim somewhere above is that PCG can do 0.25 cycles per byte (or 4 words per cycle) when going all out with AVX-512; that's only hard to beat if you've not been paying attention.
Ah. So the “AEAD” part had little to do with it, in the sense that a non-authenticated cipher without associated data would work just as well. ChaCha20 makes and excellent and quite fast RNG, whereas using ChaCha20-Poly1305 as an RNG would be rather silly.
The AEAD bit is just as a baseline of performance - look how fast you can make this go if you had to do all the work to be an AEAD scheme. For 'merely' a CSPRNG, you can go faster. The argument is, for lots of typical applications that require randomness, you might as well go with a CSPRNG because it will be fast enough.
Which implementation are you talking about? The only assembly I can see in the reference implementation is used because clang fails to optimize a rotation. There seems to be no explicit SIMD at all.
Is a "challenging" level of prediction difficulty not a thing because it provably doesn't exist, or do you just want more evidence that the bar is reached?
Use case: a randomized algorithm, performance critical, but some users might expose it to the web. Using secure randomness is too slow to be feasible, but using a trivially weak RNG might make people vulnerable to DOS attacks.
A potentially weak RNG that at least seems to be difficult to predict acts as a buffer. If it takes brute force effort to break the RNG, that correspondingly cuts down the strength of an attack, and the extent to which your adversaries do not have access to a vulnerability, you are safe from that attack from them. Since this is securing availability rather than privacy, should you end up finding yourself unexpectedly vulnerable, you can always switch it out for something else.
"Challenging" is inherently unfalsifiable, and gives you very little information about what security you're getting. You can come up with a better-than-bruteforce attack, only to be met with "see? I was right all along, it was still challenging!". There's a reason cryptographic algorithms come with concrete security claims; it becomes a mess of definitions and rationalizing of attacks otherwise.
Imprecise, perhaps, but certainly not unfalsifiable; a MCG is not challenging, xorioshiro is not challenging, a stream of 9s is not challenging. Not knowing precisely where to draw the line is not to say there is no difference between 2^60 and 10.
It is not like you have to be right first time and forever more; in the absolute worst case and the NSA already has a perfect attack, that still leaves you better off than otherwise, and frankly if the NSA wanted to DOS you they would manage regardless.
"Not breakable in fewer than O(2^(n/2)) operations" is an imprecise security claim; "challenging" means nothing. "Challenging" may not even mean "computationally hard"---breaking a truncated LCG is arguably quite challenging if you are unfamiliar with lattice reduction.
Do you lock your front door? Is your lock unpickable, or robust to attacks from national superpowers? What formal security guarantees does it give you?
Surely you must accept that there is some scope, somewhere, for better-than-nothing security, some amount of protection that is not robust against arbitrarily skilled adversaries, but nonetheless makes it harder to break your things. So either you need to show that it is not useful in this case specifically, or you need to show that this particular formulation in untenable. Arguing about words does not get us closer to an answer; I have shown a specific threat and a specific mitigation, either it helps or it does not.
I will continue to mark the security of PCG as "unwilling to quantify", which is strictly below "better than nothing". Debating the virtues of the latter is therefore pointless.
Nowhere does O'Neil discourage expert analysis of PCG generators. She does lack the ability to do direct research to the standards of the industry, but discusses related work and attacks in the paper, and has encouraged further research. I don't see how you can see the evidence presented in the paper and claim there is zero practical difference between it and the examples I listed, even just talking about today's adversaries.
Why are you bringing up secure RNGs? PCG isn't in this category.
Getting a non-secure RNG right is important. There are plenty of simulation applications which rely on RNGs like these to make high-quality statistically random selection results.
And yet the page calls the other RNGs out as being insecure:
> Many RNGs can be predicted with after observing small amount of their output. If you use random numbers as a way to ensure fairness or unpredictability, that's a problem.
> [Talking about PCG] * It's much less predictable and thus more secure than most generators
If you're comparing all PRNGs, there's no reason to exclude the CSPRNGs. They're fine to use for all sorts of purposes. They mostly just tend to be slow.
As usual, it is worth testing and seeing the results empirically. For an excellent project testing these and comparing results, see https://github.com/lemire/testingRNG.
This is not enough. The results need to be understood and interpreted as well. For example, it is questionable whether linear dependencies in some bits matter for any of the typical applications of non-CSPRNGs.
Getting an RNG right is important. I'd not trust this method until other people in the field have verified that the author's claims are true and critics have been satisfied. The accepted method for this is peer review.