8 ms·

Need a PRNG? Use a CSPRNG

74 points by tczajka 3y ago

boulos 3y ago
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"?
- nullc 3y ago
  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.
- fanf2 3y ago
  There are several PRNGs that are faster and more random than Mersenne Twister.
  - nurandal 3y ago
    Some example benchmarks which compare MT against other newer algorithms in a couple of blog posts here: https://nullprogram.com/blog/2017/09/21/ https://nullprogram.com/blog/2017/09/21/ https://pixelesque.net/blog/2020/08/prng-evaluation-and-benchmarks-for-monte-carlo-simulations/ https://pixelesque.net/blog/2020/08/prng-evaluation-and-benc...
  - loeg 3y ago
    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.
- tczajka 3y ago
  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?
  - nullc 3y ago
    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.
nicole_express 3y ago
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.
- mcraiha 3y ago
  I hope you have already watched "Dragon Warrior by NEScardinality" that shows exactly what slight advantage is https://www.youtube.com/watch?v=Bgh30BiWG58&t=428s https://www.youtube.com/watch?v=Bgh30BiWG58&t=428s
  - SuchAnonMuchWow 3y ago
    This exploit the fact that the game use a PRNG instead of a true RNG, and can work regardless of whether the PRNG is a CSPRNG or not.
- emodendroket 3y ago
  We can probably assume that writing assembly for a machine the better part of 40 years old was not what the author had in mind when writing.
- JoachimS 3y ago
  You could use Siphash as a CSPRNG, and I have an implementation in 6502 asm: https://github.com/secworks/siphash_6502 https://github.com/secworks/siphash_6502
barathr 3y ago
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.
- steponlego 3y ago
  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.
  - fanf2 3y ago
    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.
    - steponlego 3y ago
      I simply don't trust NSA people and those who take their money. Why would you? We've seen nothing but shady moves from them in this space.
      - tptacek 3y ago
        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.
        3y ago
isilofi 3y ago
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.
- tczajka 3y ago
  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.
  - josephg 3y ago
    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: https://rust-random.github.io/book/guide-rngs.html https://rust-random.github.io/book/guide-rngs.html
glitchc 3y ago
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.
- josephg 3y ago
  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.
  - glitchc 3y ago
    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.
    - Thorham 3y ago
      ChaChah is a stream cipher and was never a SHA3 candidate.
    - tczajka 3y ago
      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.
exxos 3y ago
[flagged]
- josephg 3y ago
  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.
- tptacek 3y ago
  Please don't try to start language fights on HN.
ribit 3y ago
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.
- emodendroket 3y ago
  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.
  - nneonneo 3y ago
    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).
    - emodendroket 3y ago
      Good point. All the more reason to make people opt out.
- kelnos 3y ago
josephg 3y ago
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: https://rust-random.github.io/book/guide-rngs.html https://rust-random.github.io/book/guide-rngs.html And if in doubt, thread_rng() is always a good choice.
- ngneer 3y ago
  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.
  - josephg 3y ago
    Oh, TIL! And indeed chacha in Rust’s rand crate can be seeded. Cool! https://rust-random.github.io/rand/rand_chacha/struct.ChaCha20Rng.html#impl-SeedableRng-for-ChaCha20Rng https://rust-random.github.io/rand/rand_chacha/struct.ChaCha...
deleted 3y ago
[deleted]
worik 3y ago
This is wrong for two reasons 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
- OskarS 3y ago
  > Reproducibility 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".
- pclmulqdq 3y ago
  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.
sneak 3y ago
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. Engineering is about trade-offs.
- tczajka 3y ago
  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.
  - bsder 3y ago
    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.
    - tczajka 3y ago
      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.
      - bsder 3y ago
        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.
OskarS 3y ago
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.
tromp 3y ago
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. [1] https://en.wikipedia.org/wiki/SipHash https://en.wikipedia.org/wiki/SipHash
pyjarrett 3y ago
> You can try running this code yourself and see if you get the same answers. This experiment is repeatable. 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 That's wild. 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.275
Vecr 3y ago
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.ChaCha8Rng.html 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.
- kelnos 3y ago
  The article does at least mention the ChaCha12 impl in that same rust crate: > The de-facto standard Rust library for random numbers, rand, uses ChaCha12, a reduced-round variant of ChaCha20, as its default PRNG.
spott 3y ago
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.
e63f67dd-065b 3y ago
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.
- Klaus23 3y ago
  The same is true for CSPRNG. Same seed -> same output.
  - e63f67dd-065b 3y ago
    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.
    - hinkley 3y ago
      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.
zeta0134 3y ago
But if you need a PRNG in a big hurry, an LFSR is probably fine. https://en.m.wikipedia.org/wiki/Linear-feedback_shift_register 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
- Sharlin 3y ago
  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…
atq2119 3y ago
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)
slow_typist 3y ago
http://csundergrad.science.uoit.ca/courses/sim-and-modeling-notes/lectures/random-processes/dilbert.pdf http://csundergrad.science.uoit.ca/courses/sim-and-modeling-...
toppy 3y ago
Welcome on HN, your reputation precedes you :)
asnelt 3y ago
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 https://github.com/asnelt/derandom
nmstoker 3y ago
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?
- deleted 3y ago
  [deleted]
- sweetjuly 3y ago
  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. [1] https://pracrand.sourceforge.net/PractRand.txt https://pracrand.sourceforge.net/PractRand.txt
  - nmstoker 3y ago
    Thanks a lot - this is helpful!
- nneonneo 3y ago
  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.
twotwotwo 3y ago
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. 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/weak-prng 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.
rurban 3y ago
I do have much more numbers, sorted by quality and speed. https://rurban.github.io/dieharder/QUALITY.html https://rurban.github.io/dieharder/QUALITY.html
- loeg 3y ago
  What hardware are you measuring performance on?

74 points by tczajka 3y ago

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"?

nullc 3y ago
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.
fanf2 3y ago
There are several PRNGs that are faster and more random than Mersenne Twister.
- nurandal 3y ago
  Some example benchmarks which compare MT against other newer algorithms in a couple of blog posts here: https://nullprogram.com/blog/2017/09/21/ https://nullprogram.com/blog/2017/09/21/ https://pixelesque.net/blog/2020/08/prng-evaluation-and-benchmarks-for-monte-carlo-simulations/ https://pixelesque.net/blog/2020/08/prng-evaluation-and-benc...
- loeg 3y ago
  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.
tczajka 3y ago
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?
- nullc 3y ago
  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.

nicole_express 3y ago

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.

mcraiha 3y ago
I hope you have already watched "Dragon Warrior by NEScardinality" that shows exactly what slight advantage is https://www.youtube.com/watch?v=Bgh30BiWG58&t=428s https://www.youtube.com/watch?v=Bgh30BiWG58&t=428s
- SuchAnonMuchWow 3y ago
  This exploit the fact that the game use a PRNG instead of a true RNG, and can work regardless of whether the PRNG is a CSPRNG or not.
emodendroket 3y ago
We can probably assume that writing assembly for a machine the better part of 40 years old was not what the author had in mind when writing.
JoachimS 3y ago
You could use Siphash as a CSPRNG, and I have an implementation in 6502 asm: https://github.com/secworks/siphash_6502 https://github.com/secworks/siphash_6502

barathr 3y ago

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.

steponlego 3y ago
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.
- fanf2 3y ago
  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.
  - steponlego 3y ago
    I simply don't trust NSA people and those who take their money. Why would you? We've seen nothing but shady moves from them in this space.
    - tptacek 3y ago
      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.
      - 3y ago

isilofi 3y ago

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.

tczajka 3y ago
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.
- josephg 3y ago
  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: https://rust-random.github.io/book/guide-rngs.html https://rust-random.github.io/book/guide-rngs.html

glitchc 3y ago

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.

josephg 3y ago
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.
- glitchc 3y ago
  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.
  - Thorham 3y ago
    ChaChah is a stream cipher and was never a SHA3 candidate.
  - tczajka 3y ago
    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.

exxos 3y ago

[flagged]

josephg 3y ago
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.
tptacek 3y ago
Please don't try to start language fights on HN.

ribit 3y ago

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.

emodendroket 3y ago
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.
- nneonneo 3y ago
  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).
  - emodendroket 3y ago
    Good point. All the more reason to make people opt out.
kelnos 3y ago

josephg 3y ago

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: https://rust-random.github.io/book/guide-rngs.html https://rust-random.github.io/book/guide-rngs.html And if in doubt, thread_rng() is always a good choice.

ngneer 3y ago
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.
- josephg 3y ago
  Oh, TIL! And indeed chacha in Rust’s rand crate can be seeded. Cool! https://rust-random.github.io/rand/rand_chacha/struct.ChaCha20Rng.html#impl-SeedableRng-for-ChaCha20Rng https://rust-random.github.io/rand/rand_chacha/struct.ChaCha...

deleted 3y ago

[deleted]

worik 3y ago

This is wrong for two reasons 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

OskarS 3y ago
> Reproducibility 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".
pclmulqdq 3y ago
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.

sneak 3y ago

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. Engineering is about trade-offs.

tczajka 3y ago
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.
- bsder 3y ago
  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.
  - tczajka 3y ago
    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.
    - bsder 3y ago
      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.

OskarS 3y ago

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.

tromp 3y ago

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. [1] https://en.wikipedia.org/wiki/SipHash https://en.wikipedia.org/wiki/SipHash

pyjarrett 3y ago

> You can try running this code yourself and see if you get the same answers. This experiment is repeatable. 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 That's wild. 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.275

Vecr 3y ago

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.ChaCha8Rng.html 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.

kelnos 3y ago
The article does at least mention the ChaCha12 impl in that same rust crate: > The de-facto standard Rust library for random numbers, rand, uses ChaCha12, a reduced-round variant of ChaCha20, as its default PRNG.

spott 3y ago

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.

e63f67dd-065b 3y ago

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.

Klaus23 3y ago
The same is true for CSPRNG. Same seed -> same output.
- e63f67dd-065b 3y ago
  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.
  - hinkley 3y ago
    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.

zeta0134 3y ago

But if you need a PRNG in a big hurry, an LFSR is probably fine. https://en.m.wikipedia.org/wiki/Linear-feedback_shift_register 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

Sharlin 3y ago
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…

atq2119 3y ago

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)

slow_typist 3y ago

http://csundergrad.science.uoit.ca/courses/sim-and-modeling-notes/lectures/random-processes/dilbert.pdf http://csundergrad.science.uoit.ca/courses/sim-and-modeling-...

toppy 3y ago

Welcome on HN, your reputation precedes you :)

asnelt 3y ago

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 https://github.com/asnelt/derandom

nmstoker 3y ago

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?

deleted 3y ago
[deleted]
sweetjuly 3y ago
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. [1] https://pracrand.sourceforge.net/PractRand.txt https://pracrand.sourceforge.net/PractRand.txt
- nmstoker 3y ago
  Thanks a lot - this is helpful!
nneonneo 3y ago
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.

twotwotwo 3y ago

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. 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/weak-prng 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.

rurban 3y ago

I do have much more numbers, sorted by quality and speed. https://rurban.github.io/dieharder/QUALITY.html https://rurban.github.io/dieharder/QUALITY.html

loeg 3y ago
What hardware are you measuring performance on?