It's been over a decade since I looked at this, but in real-time Monte Carlo path tracing the speed of your RNG is material. In simple enough scenes, probably something like 5-10% IIRC when using MT.
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"?
There are things with rand() like performance but much better properties.
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.
The other big nuisance of the MT is that its state is huge -- the most common version, MT19937, has ~2500 bytes of state and generates 32-bit numbers. A very good 64-bit PRNG only needs 16 bytes of state and a very good 32-bit PRNG only needs 8 bytes of state. That's >300x smaller. This is somewhat related to it being slow, of course, but also somewhat orthogonal.
I can just about believe that this kind of scenario might be a very rare exception where the performance difference is relevant and you might want to do something else.
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?
In the sorts of searches I often do, like fitting integer solutions to fast function approximations, searching for error correcting codes, and randomized SAT-like problems, or simulating usage of data structures for benchmarking them chacha is slow enough to meaningfully influence (even dominate) the runtime.
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.
I'm going to keep using quick insecure PRNGs for my NES games rather than write a 6502 implementation of a CSPRNG... I guess this isn't something that's safe to assume for all game development by any means, but in my case if someone really can predict the future actions based off of visual observation they deserve the slight advantage they get.
Even simpler than implementing a cryptographic PRNG yourself, just use /dev/urandom, which will provide an infinite, non-blocking stream of cryptographically-strong pseudorandom bytes. All platforms currently have known-good implementations of /dev/urandom -- Linux uses ChaCha and MacOS and BSDs use Bruce Schneier's Fortuna.
They weakened it recently in Linux again. For over a decade there was a badly bugged PRNG in the Linux kernel, it was discovered and replaced with a more costly one which worked great. Then, only a short time ago, they replaced that with one of... shady provenance. You're better off writing your own PRNG on that platform IMHO.
Jason Donenfeld (author of Wireguard) replaced Linux’s SHA-1 based PRNG (remember, SHA-1 is cryptographically broken) with BLAKE2. What is shady about it?
You can’t get cryptographically secure random numbers without platform support, so it’s really bad to tell people to avoid the kernel CSPRNG.
What are you talking about? Jason Donenfeld is the author of WireGuard, the extraordinarily popular VPN protocol that cannot use NIST cryptography (it does no negotiation, and is built on a version of Noise that uses ChaPoly and 25519). The change that was just described to you was a shift from NIST cryptography to non-NIST cryptography.
Yes: they use, for lack of a better term, DJB cryptography, and like many modern cryptosystems they eschew negotiation, so it's not straightforward to fit NIST algorithms in.
it's entirely straight-forward to substitute AES-256-GCM for ChaCha20/Poly1305 in Wireguard, and the result, while not "wireguard" is substantially faster than Wireguard.
/dev/urandom is really slow compared to a userland CSPRNG, though. And if you are doing simulations or fuzz testing, you need to be able to seed your PRNG to get reproducible results.
You can always pre-fetch random bytes in larger blocks. Read a few kB of random bytes at a time, store them in a buffer, and refresh the buffer when you run out.
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.
For many kinds of Monte Carlo algorithms, CSPRNGs are stupidly slow. The author compares two handpicked examples of a fast CSPRNG and a very slow PRNG, arriving at a factor of 4. In practice, e.g. comparing to very simple stuff like multiply-add RNGs, it is more like a factor of 4000. Only to then claim that "But that would only be true if generating random bits was the hot spot, the bottleneck of your program. It never is in practice."
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.
It's not true that I cherry-picked a slow PRNG for my 7 GB/s number. In fact I selected the second-fastest PRNG on that page (because it's popular)! The fastest one is 8 GB/s. PCG32 is 3 GB/s.
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.
I was curious. The rust rand library has implementations for a lot of rngs - prngs and csrngs. All with high quality implementations as far as I can tell.
They agree with your numbers: their fast, high quality prng implementations are about 8gb/sec and chacha is about 2gb/sec:
There are ways to make much faster PRNGs; I designed one that reaches 53 GB/s[0] (0.06 cycles per byte) with better quality than those listed in the article.
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.
Cool! I wonder if the rand crate would be interested in adding this. I love all their sampling functions - shuffle, choose, uniform, etc. But it looks like shishua is way faster than any of their rngs.
The state of the art in super-fast PRNGs is about 0.3 cycles per byte at the moment. I believe this is done with SIMD versions of the xoroshiro algorithms right now. 0.3 cycles per byte compared to "a few" cycles per byte is an order of magnitude difference in throughput.
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.
- 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.
For those interested in using AES with reduced rounds as a PRNG, it is covered in the paper "Parallel Random Numbers: As Easy as 1, 2, 3" by John Salmon et al.
Upon a closer look, do not trust the numbers on https://rust-random.github.io/book/guide-rngs.html in any way, they are clearly bogus and implausible. Their figure for their "StepRNG" which is just a counter is 51GB/s. Their XorShift RNG at 5GB/s, which is just a XOR and a shift is slower than Xorshiro at 7GB/s, which is a xor, shift and rotate, 1 op more. Both XorShift and Xorshiro should actually be of comparable performance to a counter of the same width because with modern CPUs, all those trivial bit operations like shift, rotate and XOR are sub-cycle microops. And all three of those should either be memory-bound and therefore of the same performance, or quite a bit faster than memory-bound if they just measure the in-register performance.
> 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.
You’re just spouting theoretical numbers here, not actual real-world numbers.
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.
PRNGs like the romu family are faster than multiply add LCGs and way higher quality (they don't fail statistical tests from testu01 and PractRand). This ia possible due to using more state and exploiting ILP. [0] In LCGs the add dependa on the multiply, so both need to be executed sequentually, romu prngs use a multiply and fit a.bunch of mixing operations into the other exexution ports while the multiply executes.
You can get close to 10x faster [1] than chacha8 with SIMD PRNG implementations, that are way higher quality than the usual LCG and don't fail any statistical test in the test suites (testu01 & PractRand). They are obviously not cryptographically secure, but it's very hard to run into problems with bias in simulations, when test suites designed to find such bias can't find it.
For Monte Carlo and if you need for speed, consider Quasi Monte Carlo. For the right kind of problems the speed up in convergence is huge (ie given same accuracy it will be faster.)
An alternative to the post is to take any PRNG's output and calculate the SHA3 hash of it, then use the hash as the random number. If SHA3 is not available, use AES. In either case, all statistical weaknesses and side-channel attacks will be eliminated.
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.
That might be convenient so you don’t have to go fishing for 3rd party libraries - which is especially a problem in C/C++. But I expect the result will be much slower than using an optimized csrng like chacha.
Well, ChaCha is actually a hash function. Specifically it was a candidate for SHA3 but was beaten by Keccak in the final spec. Additionally, aes-ctr-128 has the same performance as ChaCha (1.5 GB/s).
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.
As alright2565 already mentioned, sticking rand() in there doesn't add any benefit over a key + counter.
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.
Would be better to simply use a counter and a random seed in that case. Who knows when your prng will loop around, but your counter will always loop at 2^32.
At which point, if you use AES, you've just implemented the AES-CTR csprng that TFA suggests.
The reason not to use CSPRNG is performance and efficiency. There are many applications where you only need randomness, and don't care about the resiliency provided by the CSRPNG. I mean, I'm not going to run a cryptographically secure generator on a GPU just to scatter a few rays for my raytracer.
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.
Perhaps. But one could equally well argue that it should be the default simply because for the small number of applications where performance is really constrained by RNG performance one can still override with a less secure algorithm, while having the default the other way opens many applications to security flaws because of plain old oversights. Many programming language or STL features are somewhat less efficient than they could be by default out of similar concerns.
It’s not just security flaws you should worry about, because the arguments against CSPRNGs often involve situations with no security implications (e.g. rendering in games).
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).
The author does address the perf & efficiency concerns, though I have no opinion on the strength of their conclusions.
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.)
Real talk: If rust added a random numbers to the standard library, they would almost certainly have done a worse job the rand crate - which has multiple rngs with a standard api, and a whole lot of great sampling methods. (Eg choose from this set, shuffle a list, get a bool with some probability bias, etc.)
Rand is basically part of the standard library as far as I’m concerned. You just have to add it to cargo.toml to use it.
My biggest use case for random numbers is for fuzz testing. I fuzz test all over the place - any time I have some clear invariants and some complex code to test, I’ll generate random data in a loop and make sure the invariants always hold. This finds so many bugs.
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:
I recommend you research CSPRNGs before arriving at a conclusion. They, too, are seeded, which is helpful for deterministically replaying a sequence, say for fuzzing.
CSPRNGs are not true randomness. They are PRNGs (with a seed and all), but with cryptographic guarantees. That also means, as a corollary, that they are generally good RNGs.
TRNG appliances can get very high throughput, too.
There are lots of cases where a PRNG is more appropriate than a CSPRNG. Wiping disks is one of them, as the CSPRNG becomes the bottleneck with large arrays. Testing i/o or network throughput is another; you don’t want your algorithm tainting the results.
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.
If a predictable PRNG is sufficient for wiping disks, why do we care that the data is random at all? How about writing 0, 1, 2, ..., 255, 0, 1, 2, ... to consecutive bytes? Or -- generate 1 kb of good quality random data, and write the same 1 Kb repeatedly? It's not clear to me what we're trying to achieve in this scenario.
Because it is conceivable that you could extract patterns from the underlying data because you know what the highly correlated, short-cycle writing pattern was.
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.
Isn't it also similarly conceivable that if you write a predictable PRNG sequence such the outputs of Mersenne Twister you could also potentially extract patterns? Mersenne Twister is essentially as predictable as a short cycle.
Correlating a short cycle is much more difficult than correlating a long cycle even if you have complete information about the long cycle. If the bits on the disk have a pattern, it is much more likely to repeat against a short cycle.
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.
If this is sufficient, then this matches what I said in the article. I wrote that if you don't care about what numbers you get, don't bother with xoroshiro or Mersenne Twister, just use https://xkcd.com/221/.
> This is why they [non-CS PRNGs] are sometimes called DRBGs
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.
The author is a bit too categorical, there are certainly use-cases where both speed and code-size matters a great deal. Others have mentioned Monte Carlo algorithms, but there are others: not very long ago I was doing an effect in a shader that needed a PRNG, it would have been lunacy to use a CSPRNG. High quality statistical properties are not important at all, but speed and instruction size is VERY important. My hunch is that this is often true in game-dev: Minecraft probably should not use a CSPRNG to generate its random world.
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.
I recommend siphash24 [1] for its excellent statistical properties and good performance. It's a light weight, almost cryptographically secure, seeded hash, very popular in hashtable implementations.
I'm surprised I'm not seeing mention of the reduced round ChaCha8 version of ChaCha, that's what I'd recommend for Monte Carlo use. It's available in Rust at https://docs.rs/rand_chacha/0.3.1/rand_chacha/struct.ChaCha8... . I recommend seeding it from a high quality random source, but it could be fixed in your source code, generated with `openssl rand -base64 32` or similar.
This whole discussion seems to be summed up as “premature optimization is the root of all evil, and using anything but a csprng is a premature performance optimization”
There doesn’t seem to be any good non-performance reasons to use a regular prng that I can think of.
Xorshift has the best bang for the buck, easily. Literally three xors and shifts per generated number, no extra state, long period, reasonably high quality. But admittedly it would be trickier on a 8-bit platform…
There's one big scenario where PRNGs are good: reproducibility. I have a lot of tests that are deterministic given a seed, and if the test fails then I can grab the seed and replay the test.
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.
I'm confused; if you can predict the output, then isn't it by definition not secure? Or is the seed so hard to brute force that it's equivalent to breaking the underlying cryptography.
Guessing the seed is impossible using current knowledge of information theory and predictable breakthroughs in new computer hardware. That may or may not include quantum.
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.
People talking about seedable CSPRNGs for Monte Carlo work are proposing that you use CSPRNG algorithms, but in userland, as a library; instead of periodically rekeying them with unpredictable data collected from timing and hardware, you'd key it just once, with a known key, and thus generate a predictable sequence of "random" bits for your simulation.
If you have the key to a ciphertext, you can decrypt it, but that doesn't make the cipher insecure. It is the same principle for the seed of a CSPRNG. In fact, a common cipher construction (ChaCha20, for instance) relies on a random stream seeded by the key, generated by the sender to encrypt data, which the recipient re-generates from that same key to decrypt the data.
There is no such thing as a true random generator when we are talking about software - hence the P in PRNG. The seed value to any of these algorithms is meant to be the "true" random part - or as close to that as it can be.
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.
As hinkley said, it is basically impossible to get the seed from the output of the generator without breaking the algorithm itself.
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.
This is pretty reasonable, I think, but can it be applied to GPU code?
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)
I agree that it's a bad idea to use non-cryptographic PRNGs as defaults. I think most people are not aware of how easy it is to break them. For fun, I wrote an Android app to break LCGs and Mersenne Twisters:
https://github.com/asnelt/derandom
Are there accessible techniques to establish if a number sequence is from a good RNG or not?
I appreciate that people are probably bad judges of randomness but I keep noticing odd patterns with a supposedly random number generated as part of an MFA process.. I'm interested in seeing if there's a problem or if it's actually working effectively. What terms should I search for to find out more on this?
For CSPRNGs, we tend to use hardness proofs (i.e. prove that an attacker cannot predict the CSPRNG output in polynomial time). To understand these, you'll need to figure out what the algorithm in use is. This isn't particularly relevant to TOTPs since they are built on unforgeable message authentication codes (TOTP usually uses HMAC) so the proof would usually be less about predicting a bit (though, if you could, that would be a valid security break) and more about proving an attacker cannot forge a signature on a message without violating the hardness assumptions.
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.
Hah, if you’re referring to the fact that repetitive digits show up in 2FA codes, this is a great example of a randomness illusion.
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
Almost 40% of the time you will have a 2FA code that has at most four unique digits: it has two digits appear twice (e.g. 463426), or one digit appear thrice (e.g. 838819), etc. These look distinctly “non-random”, but appear frequently when using 2FA systems. In fact, having a number that “looks random” (has all unique digits) is comparatively uncommon at 15%; even in that set, there are many numbers with discernible patterns like “234719” and “136420”.
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 am pretty sympathetic to a CSPRNG being the default in standard libraries and so on. The relative performance has vastly changed since the first stdlib random()s; modern hardware- or SIMD-accelerated functions run at GBs/second per core, and CSPRNGs are flawless PRNGs--no fussing about whether PCG's subtle patterns matter--but the reverse is definitely not true.
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.
104 comments
[ 7.3 ms ] story [ 205 ms ] threadI 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.
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.
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:
https://rust-random.github.io/book/guide-rngs.html
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.
[0]: https://github.com/espadrine/shishua#comparison
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.
[0] https://www.romu-random.org
[0] https://github.com/espadrine/shishua
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.
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.)
Rand is basically part of the standard library as far as I’m concerned. You just have to add it to cargo.toml to use it.
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.
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.
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.
[1] https://en.wikipedia.org/wiki/SipHash
OpenSUSE:
That's wild.I don't see this with mt19937, but I did see these funny nuggets with unseeded `rand()` on Windows:
> The de-facto standard Rust library for random numbers, rand, uses ChaCha12, a reduced-round variant of ChaCha20, as its default PRNG.
There 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
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.
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.
[1] https://pracrand.sourceforge.net/PractRand.txt
Of the 1000000 possible 6-digit numbers:
Almost 40% of the time you will have a 2FA code that has at most four unique digits: it has two digits appear twice (e.g. 463426), or one digit appear thrice (e.g. 838819), etc. These look distinctly “non-random”, but appear frequently when using 2FA systems. In fact, having a number that “looks random” (has all unique digits) is comparatively uncommon at 15%; even in that set, there are many numbers with discernible patterns like “234719” and “136420”.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.
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.
https://rurban.github.io/dieharder/QUALITY.html