Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Need a PRNG? Use a CSPRNG

sortingsearching.com

Post reply on HN
Print view View original

11–20 of 105 posts

Re: Need a PRNG? Use a CSPRNG

#11

Post by tczajka »

isilofi wrote: post #6

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 ne…

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.

Re: Need a PRNG? Use a CSPRNG

#12

Post by tczajka »

boulos wrote: post #2

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…

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?

Re: Need a PRNG? Use a CSPRNG

#13

Post by josephg »

tczajka wrote: post #11
isilofi wrote: post #6

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 ne…

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 com…

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

Re: Need a PRNG? Use a CSPRNG

#14

Post by nullc »

tczajka wrote: post #12
boulos wrote: post #2

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…

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 th…

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.

Re: Need a PRNG? Use a CSPRNG

#15

Post by fanf2 »

barathr wrote: post #4

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.

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

Re: Need a PRNG? Use a CSPRNG

#16

Post by SuchAnonMuchWow »

mcraiha wrote: post #9
nicole_express wrote: post #3

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.

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

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.

Re: Need a PRNG? Use a CSPRNG

#17

Post by glitchc »

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.

Re: Need a PRNG? Use a CSPRNG

#18

Post by espadrine »

josephg wrote: post #13
tczajka wrote: post #11

Earlier quoted context omitted.

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 com…

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

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.

[0]: https://github.com/espadrine/shishua#comparison

Re: Need a PRNG? Use a CSPRNG

#19

Post by ribit »

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.

Post reply on HN