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

21–30 of 105 posts

Re: Need a PRNG? Use a CSPRNG

#21

Post by josephg »

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

And if in doubt, thread_rng() is always a good choice.

Re: Need a PRNG? Use a CSPRNG

#22

Post by steponlego »

fanf2 wrote: post #10
steponlego wrote: post #7

Earlier quoted context omitted.

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.

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.

Re: Need a PRNG? Use a CSPRNG

#23

Post by pclmulqdq »

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…

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.

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.

Re: Need a PRNG? Use a CSPRNG

#24

Post by josephg »

espadrine wrote: post #18
josephg wrote: post #13

Earlier quoted context omitted.

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

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.

Re: Need a PRNG? Use a CSPRNG

#26

Post by worik »

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

Re: Need a PRNG? Use a CSPRNG

#27

Post by ngneer »

josephg wrote: post #21

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. The…

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.

Re: Need a PRNG? Use a CSPRNG

#28

Post by josephg »

exxos wrote: post #20

[flagged]

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.

Re: Need a PRNG? Use a CSPRNG

#29

Post by tptacek »

steponlego wrote: post #22
fanf2 wrote: post #10

Earlier quoted context omitted.

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.

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.

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.
Post reply on HN