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

81–90 of 105 posts

Re: Need a PRNG? Use a CSPRNG

#81

Post by twotwotwo »

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

Re: Need a PRNG? Use a CSPRNG

#82

Post by nneonneo »

isilofi wrote: post #35
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…

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

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.

Re: Need a PRNG? Use a CSPRNG

#83

Post by nneonneo »

emodendroket wrote: post #76
ribit wrote: post #19

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

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…

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

Re: Need a PRNG? Use a CSPRNG

#84

Post by nneonneo »

nmstoker wrote: post #71

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?

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.

Re: Need a PRNG? Use a CSPRNG

#85

Post by emodendroket »

nneonneo wrote: post #83
emodendroket wrote: post #76

Earlier quoted context omitted.

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…

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

Good point. All the more reason to make people opt out.

Re: Need a PRNG? Use a CSPRNG

#86

Post by SonOfLilit »

e63f67dd-065b wrote: post #58
Klaus23 wrote: post #53

Earlier quoted context omitted.

The same is true for CSPRNG. Same seed -> same output.

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.

CSPRNG means "if the seed were secure, it would be secure", i.e. "the mixing is so good we don't even know how to undo it"

Re: Need a PRNG? Use a CSPRNG

#87

Post by JoachimS »

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.

You could use Siphash as a CSPRNG, and I have an implementation in 6502 asm: https://github.com/secworks/siphash_6502

Re: Need a PRNG? Use a CSPRNG

#88

Post by camel-cdr »

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…

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.

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

Re: Need a PRNG? Use a CSPRNG

#89

Post by camel-cdr »

nneonneo wrote: post #82
isilofi wrote: post #35

Earlier quoted context omitted.

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

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

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.

[0] https://www.romu-random.org

Re: Need a PRNG? Use a CSPRNG

#90

Post by tczajka »

sneak wrote: post #72
tczajka wrote: post #48

Earlier quoted context omitted.

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.

What you just described is, in theory, just a really bad non-CS PRNG. In that sense we are in agreement that a CSPRNG is not necessary. 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.

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