Need a PRNG? Use a CSPRNG
sortingsearching.com
sortingsearching.com
E.g. for the usual example of Monte Carlo integration, you pick a point randomly, usually by running your RNG for both coordinates. Then you evaluate your characteristic function with that point as an input. Very often, the function will have a runtime that is in the range of a few hundred FPU instructions or less. Comparable to the evaluation of your CSPRNG. So in the end, you usually get a 40 to 50% faster runtime by just using a slow PRNG instead of a CSPRNG. Not to mention the few extra percent you will gain with a fast PRNG.
And it doesn't stop there. CSPRNG libraries are often optimized to be side-channel free and cryptographically safe. Even if you were to use a CSPRNG, you are leaving performance on the table by using stuff with security properties you will never ever need, that can easily be optimized out for a 30% gain in the CSPRNG parts.
And yes, for simulations a few percent points are relevant. Thoses "few" percents are maybe days in runtime, thousands of currency units in power and hardware cost and tons of CO2 in pollution.
Your 4000x factor speed up for a linear-congruential generator is just a completely false number.
Yes I did pick ChaCha20 for its speed -- it's designed for speed!
"A few hundred FPU instructions" in your Monte Carlo is not comparable to generating a number with ChaCha20. If you need a few hundred FPU instructions per number, you will be running a lot slower than 2 GB/s. ChaCha only requires a few cycles per byte.
I agree that you can optimize out the side-channel free part for non-crypto-purposes. That's a good thing! I recommend doing that.
They agree with your numbers: their fast, high quality prng implementations are about 8gb/sec and chacha is about 2gb/sec:
But I agree with tczajka: good engineering practice ought to be to start with a CSPRNG. First make it work, then make it fast. With truly random data, you know your algorithm works, and can then check if there is a quality loss when switching away. The performance of CSPRNG is so optimized that it is seldom the bottleneck anyway.
Here's the comparison from the maintainers of Julia: https://prng.di.unimi.it/#shootout
Still, most crypto libraries are designed with extreme performance in mind, and very few PRNG libraries are. You can do a lot better than 0.3 cycles/byte and still beat the NIST test if you try for speed.
Looking at https://eprint.iacr.org/2018/392.pdf , it seems like:
- Intel CPUs can use AESNI to do AES at 0.64 cpb - AMD Zen cores have two AESNI cores and can achieve 0.31 cpb - Vectorized AES instructions (supposed to ship in Ice Lake five years ago, but maybe a casualty of Intel's AVX512 mishaps) were expected to bring it down to 0.16 cpb
In some sense this isn't a "fair" comparison in that it's fast because there's hardware acceleration, but that doesn't really matter, the hardware is there so it might as well be used.
https://www.thesalmons.org/john/random123/papers/random123sc...
> Your 4000x factor speed up for a linear-congruential generator is just a completely false number. > Yes I did pick ChaCha20 for its speed -- it's designed for speed!
1 Chacha20 block takes 20 rounds, each of which consists of 4 QR (quarter round) operations. A QR is 4 additions, 4 XORs and 4 ROTLs, so 12 instructions on 32bit values. Multiply that together and you arrive at 960 operations per block (actually a handful more for the counter, maybe the round loop and stuff like that, but not a lot), each block gives you 16 uint32 values. So 60 instructions per uint32 or 15 instructions per byte.
A multiply-add generator takes only 2 instructions (you could use fused-multiply-add if available, but i'll leave that out as I left out sub-microop-rotate before, just to not overcomplicate things) per uint32 or half an instruction per byte. Yes, that is not yet a hyperbolic factor of 4000.
But then you'll have to use your random values. Since your Chacha20 random number stream only comes in blocks, on many CPU architectures, you will have all your registers full with your resulting block. Meaning that for the subsequent calculation, you have to store those random numbers somewhere or throw them away, do your other calc, then load the randomness again, etc. So you will always pay a penalty for cache and memory accesses and you will always have unnecessary register pressure. Even a L1 cache access will cost you about 4 cycles of access latency, other cache levels are far worse. Which means that it probably won't be 4000 yet, but a lot more.
Now we'll arrive at "yes, but somebody said ChaCha20 is roughly 1 cycle per byte!". Which isn't wrong, but you have to read carefully: 1 _cycle_, not 1 _instruction_. That benchmark relies on calculating multiple ChaCha20 blocks in parallel, because a modern CPU has multiple execution units and thus can execute multiple independent instructions within one cycle. There is also SIMD, where one instruction can operate on multiple pieces of data. But to be fair, we also need to do this with our multiply-add-RNG. And where I can have 16 registers of 32bits calculating one ChaCha20 block, I can also have 16 of the same 32bit registers calculating 16 multiply-add random numbers in parallel.
Thus giving us 60 cycles per ChaCha20 uint32 vs. 0.125 cycles (2/16) per multiply-add uint32. That is a factor of 480, not taking possible memory or cache penalties into account, because that really depends on the computation between the randomness steps. Still not 4k, I admit, that was hyperbole.
First, ChaCha20 can easily be around 1-3 cpb, which translates into around 4-12 c/u32 (source: AVX2 perf of Go ChaCha20 package: https://pkg.go.dev/github.com/aead/chacha20#section-readme). So that’s already a lot better than your theoretical claim of 60 c/u32.
Second, a multiply-add PRNG is going to have abysmally poor statistical properties. Those are the kinds of statistical failures that show up real quick if you generate a billion numbers. If you care that little about random quality in your application, why not just increment a counter and be done with it?
A more realistic assessment is that it will cost you around 0.3 cpb for a decent quality generator that passes statistical tests. Yes, you want that, at the very least: you don’t want spurious correlations screwing up your billions of Monte Carlo iterations. There’s a plausible claim that you can get down to ~0.1 cpb with AVX (cf https://espadrine.github.io/blog/posts/shishua-the-fastest-p...). In any case, the best case here is that a CSPRNG is ~5-20x as slow as a decent-quality PRNG.
Sure, a crappy RNG is 10x faster than this, but the tradeoff is that sometimes your “randomized” algorithms produce nonsense, and the last thing that you want to debug is stochastic failures in your stochastic algorithms.
ChaCha20 implementations don’t usually need to have special handling for side-channel security because they don’t perform data-dependent lookups or branches. Indeed, as the article points out, a lot of these decent PRNGs kinda look like ChaCha-style ARX ciphers with a lot fewer rounds.
However, in general, I basically agree: for MOST tasks where you need a random number generator, a CSPRNG is probably the right choice and it's a reasonable "default" choice if you don't have good reasons why it shouldn't be. It's a continual annoyance to me that PRNG libraries usually don't include any solid CSPRNGs (looking at you, C++ header <random>) when it's often the right choice.
IMO, suggesting that CSPRNG should be the default choice is a bad engineering advice. This leads to software burning processor cycles for no reason at all. I agree with the author that the default PRNGs provided by many environments are of very poor quality, but that's hardly a reason to choose something you don't need.
It is absolutely the case that a crappy RNG can compromise a renderer by creating visible patterns where none should exist. You can get really visible artifacting with e.g. an LCG-driven raytracer. Granted, the artifacts should go away with a higher-quality RNG, but the fact remains that if you choose a CSPRNG in the first place then there will be essentially no chance of such artifacts in the first place (barring errors in the implementation).
But I think this is like everything else: don't prematurely optimize. If you start with a CSPRNG, you're more likely to know that your algorithm is correct, and that you're getting good, random results. If you later profile your code and see that the CSPRNG is a bottleneck, you can swap it out with something faster. And then you'll also have a baseline for comparison, so you'll know if using a weaker PRNG actually has a negative impact on whatever it is you're doing.
(And even if you don't do that profiling, you can swap out the CSPRNG just to see what happens, and get a good idea if the quality of the randomness produced by the PRNG is good enough, based on your experience with the CSPRNG.)
> The de-facto standard Rust library for random numbers, rand, uses ChaCha12, a reduced-round variant of ChaCha20, as its default PRNG.
You can’t get cryptographically secure random numbers without platform support, so it’s really bad to tell people to avoid the kernel CSPRNG.
Do you mean as a matter of Donenfeld's engineering decisions (that those algorithms are unavailable in WireGuard)?
Agreed on the need for using a predictable seed for testing/simulations, though. Technically you can seed /dev/urandom, but it's per-system, not per-process, so you can't guarantee some other process isn't "interrupting" your random stream.
CSPRNG is designed to be cryptographically secure, and thus I somewhat agree that it should be the default choice. But there are many cases where reproducibility is a good thing, and that's where you need seeded rngs.
EDIT: I was under the (wrong) impression that CSPRNGs were non-deterministic.
Entropy sources in for instance Linux constantly receive new data, but there are CSPRNGs that only receive truly random data at construction time, and you can intentionally expose that data in your testing code. Or to be precise, since this is security we are talking about: You can set your bootstrapping code to take a seed as input, and your tests can generate and log that seed, while the real code picks its own (secret) value and keeps it safely away from storage.
I don't know how Java works now but it worked this way about ten years ago.
It takes a lot of work to get people to use randomized testing properly. Seed reproduction is table stakes IMO and yet I've had to introduce it a couple of times because it was missing. Getting people to look at test failures instead of clicking 'run again' is a whole psycho-social tarpit.
In fact I suspect whoever invented Property Based Testing was trying to route around this tarpit - do random tests, then provide concrete repro steps, so people can't ignore them and hope.
The idea here is that given a truely random seed, the algorithm should subsequently generate random bits that aren't predicable from its last output. So given the first 128 bits of output you shouldn't be able to predict the next bit for example.
Given the same seed a PRNG, and a CSPRNG will always output the same bits.
Hopefully that explains it?
CSPRNG can also be used as the basis for a stream cipher. The output must be the same for the receiver of the message to be able to decrypt it. Being able to extract the seed would be problematic because an attacker could know some part of the message being sent, calculate the CSPRNG output from it and get the seed, thus being able to read all the messages.
CSPRNG are specifically designed to be a one-way function. Calculating the output from the seed should be easy, but calculating the seed from any output must be impossible.
Making the default secure would be a pretty significant mitigation against something that commonly makes "common security bugs" lists like https://developer.android.com/privacy-and-security/risks/wea...
If you consume many GBs/s/core of randomness, or you're writing a homebrew NES game, sure, you have a special case, code up a non-CSPRNG. But that isn't a reason for the default for everyone to remain a function that needs a warning label.
OpenSUSE:
483 0.305
484 0.293
485 0.283
486 0.275
487 0.3
488 0.302
489 0.304
490 0.274
491 0.274
492 0
493 0.285
494 0
495 0.271
496 0
497 0.289
498 0
499 0.294
500 0
501 0.306
502 0
503 0.31
504 0
505 0.275
506 0
507 0.285
508 0
509 0.289
510 0
511 0.282
512 0
513 0.301
514 0
515 0.266
516 0
517 0.289
518 0
519 0.291
520 0
521 0.309
522 0
523 0.325
524 0
525 0.358
526 0
527 1
528 0
529 0
530 0
531 0
532 0
533 0
534 0
I don't see this with mt19937, but I did see these funny nuggets with unseeded `rand()` on Windows:
255 0.3
256 0
257 0.289
258 0.306
...
511 0.262
512 0
513 0.275There doesn’t seem to be any good non-performance reasons to use a regular prng that I can think of.
https://en.m.wikipedia.org/wiki/Linear-feedback_shift_regist...
I use one on my NES projects that can compute a new 8bit PRNG value in something like 65 cycles
I appreciate that you had a note about performance, but you were pretty quick to dismiss that there's a large quality difference between rand() and any modern PRNG. Plenty of these are fine enough and paying for a CSPRNG with 4x or more the perf hit may be a mistake.
I do agree that if you don't know what you're going to use them for or don't know if you have a performance problem that you should just use a CSPRNG. The potential for someone to accidentally cause a security bug is not worth it. If they decide to do so intentionally, that's on them.
tl;dr: maybe "Need a PRNG? Start with one that's cryptographically secure"?
for randomized search I'm a fan of xoshiro256++ periodically reseeded by rdrand.
Obviously if performance isn't a concern, a CSPRNG should be the default. But it often is a concern.
Traditional 'fast' PRNGs have simple algebraic structure that is absolutely known to cause wrong results, they're not worth it compared to modern fast PRNGs.
(I wouldn't ever use MT today, it's not on the pareto-frontier of performance vs quality and has a bad cache footprint)
> tl;dr: maybe "Need a PRNG? Start with one that's cryptographically secure"?
I agree but: I think if people do that, they'll often find that their whole process is now 20% slower than when they used rand() and then go back to rand. So I think it's also important to make people aware of fast generators with better properties.
https://nullprogram.com/blog/2017/09/21/
https://pixelesque.net/blog/2020/08/prng-evaluation-and-benc...
Still, color me skeptical.
"In simple enough scenes"? OK perhaps, but we don't want to only run ray tracing for very simple scenes. Simple scenes are those cases where you probably don't need much calculation, so does it really matter that 5-10% of that simple calculation is RNG? It's the complicated computation-heavy scenes that matter!
Also, one would have to see the code to judge this. For instance, maybe that code was wasting random bits a lot?
I wouldn't want to use rand() because it's extremely likely that it will produce actually bad results.
I agree one should use a CSPRNG like chacha (or rdrand) if its runtime is insignificant but then the question is: whats the best choice when it's not insignificant? Using rand is a bad idea.
The fundamental challenge of CSPRNGs is that they tend to have high latency and each thread produces a lot of randomness at once, while typically you only need a little bit at a time. So either you throw away the extra bits, effectively wasting ALU, or you keep them around in storage somewhere, which is expensive as well.
I would love to see a CSPRNG that is designed to leverage subgroup/wave ops. (Hmm, now that I think about it, perhaps ChaCha can be spread reasonably across 4 lanes? That would give 4 dwords per thread and potentially cut latency quite a bit, much better tradeoff overall for most GPU applications)
For regular ol PRNGs (i.e. non-cryptographically secure), there are various tools [1] which let you feed in enormous amounts of samples and then automatically apply a variety of known techniques to try to find correlations. But, generally, you wouldn't expect a PRNG to pass these tests. Instead, you should focus on getting a distribution and behavior that is helpful to your use case.
Of the 1000000 possible 6-digit numbers:
151200 have six unique digits
453600 have five unique digits
327600 have four unique digits
64800 have three unique digits
2790 have two unique digits
10 have only one unique digit
Hence, if you find yourself believing that your 2FA codes look non-random, it’s probably an illusion. If you’re really uncertain, you could always record a large sample of codes and look for statistical anomalies.
I like the thrust of the article but if you’re going to be particular, you should also be correct. CSPRNGs are not suitable replacements in 100% of cases.
Engineering is about trade-offs.
In reality, genuinely writing (as opposed to just pretending it was written which is a hazard on any modern storage) any single byte (even just all 0 or all 255) to every position on the disk seems to be more than sufficient to thwart even the NSA.
However, as I pointed out, it's all pretty much moot. I've never seen anybody cough up evidence that a disk could be recovered after even a single write with merely zeroes. In fact, there was a competition and prize for a while that could be won if you could demonstrated reconstruction of a disk after even a single platter write. Nobody ever managed to claim it.
To your point, a non-CS PRNG seeded with a static value isn’t “random at all”.
This is why they are sometimes called DRBGs: deterministic random bit generators. You just described two such functions.
CSPRNGs are also sometimes called DRBGs. Classically, "Dual_EC_DRBG" but also NIST SP 800-90A "(AES_)CTR_DRBG," which is what the Windows 10 kernel random device uses.
But for this kind of work, a good prng is better. The reason is simple: when I find a failing test, I can print out the seed that generated that test. Then I can rerun just that one seed (so the error shows up immediately) and debug. Every time I rerun my program, a fixed seed means it will use the same input and fail in the same way. Perfect.
High quality, modern PRNGs shouldn’t have the kind of bugs that cause the problem listed at the start of this article. I think part of the problem is that C has so many ways to get random numbers that it’s hard to tell which are high quality, and on which platforms.
Rust’s rand crate is the poster child for me of what this looks like done well. Here’s a bunch of prngs and csrngs, implemented and listed in a simple table for you to pick which one you want to use. For each rng they show rough performance numbers and the prngs have a rough quality guide:
https://rust-random.github.io/book/guide-rngs.html
And if in doubt, thread_rng() is always a good choice.
https://rust-random.github.io/rand/rand_chacha/struct.ChaCha...
Firstly
Reproducibility
Using "true" randomness sacrifices that
Secondly
Performance
In simulations you often need billions of these
There are cases for true randomness, it is a good thing it is available those rare occasions5
That's a very silly objection: CSPRNGs can be seeded just like a PRNG. The "P" in both abbreviations is the key, it stands for "pseudo".
TRNG appliances can get very high throughput, too.
The platform is far more likely to have support for either of those in the system libraries, than a bespoke CSPRNG, which would need to be packaged with your app/game.
All I was trying to illustrate was that in general, pairing a PRNG with a block cipher or hash function is sufficient to create a CSPRNG, and any developers worried about their PRNGs can couple rand() with a readily available cipher/hash in the system libraries. After all the blog is explicit about not requiring a cryptographically secure RNG for most applications.
Without rand() it would be something like SHA3-CTR -- it's not standardized which is why I would prefer ChaCha20, but it has been proposed for standardization and yes it's probably a fine algorithm.
Yeah. I'm nervous about inventing my own RNG. It seems like one of those things thats much more difficult than it appears on the surface. Especially an RNG thats aiming to be crypto-secure.
You should be, but in this case you’re actually not inventing your own CSPRNG.
NIST SP 800-90A defines HASH_DRBG as hashing a seed (aka key) plus a counter and it is defined for basically any cryptographic hash function.
At which point, if you use AES, you've just implemented the AES-CTR csprng that TFA suggests.