Random Number Generator Recommendations for Applications | Hacker News Reader

Random Number Generator Recommendations for Applications

peteroupc.github.io

Useful.

One thing to keep in mind: there’s been a bit of a feud in the PRNG space between the Vigna camp [1] with xoroshiro and newcomer O’Neill [2] with PCG.

This website seems stay on the traditional side and shy away from recommending PCG. I’m not really qualified to judge on that dispute [3], but I think both options are better, smaller, faster than the good old Mersenne Twister, so it’s time that we moved on from that [4] and pick one of the latest generation PRNGs.

FWIW, Julia now uses xoshiro256++ by default [5], and they investigated their choice quite thoroughly, I believe.

[1] https://prng.di.unimi.it/

[2] https://www.pcg-random.org/

[3] https://pcg.di.unimi.it/pcg.php

And the reply https://www.pcg-random.org/posts/on-vignas-pcg-critique.html

[4] https://arxiv.org/abs/1910.06437

[5] https://docs.julialang.org/en/v1/stdlib/Random/

we're also considering moving to a 192 bit combination of xoshiro128++ with pcg64 (early stages, PR doesn't exist yet). this would have the advantage that you could do really cheap rng splitting by modifying the pcg state while avoiding the 128 bit multiplies that make bigger pcg slow. also it would mean both sides of the fued would be mad at us :)

I am trying and failing to find an article where a poker website published their source code, including how they shuffled cards and seeded their randomness. The seed was the current timestamp. Someone realized an efficient way to reduce the search space, assuming vaguely accurate clocks, and predict every card distributed at the table after viewing only a small number of cards.

This sounds similar https://github.com/ech0ii/forceitbox

Also for an example of exploiting a gambling site that used javascript's Math.random https://jonasnick.github.io/blog/2015/07/08/exploiting-csgoj...

This is probably the article you are looking for: https://www.developer.com/guides/how-we-learned-to-cheat-at-...

The timestamp was down to a fraction of a second, so instead of having 52! possible decks (about 2^226) there were only 2^32 possible decks that could be generated by the algorithm.

Also: https://blog.codinghorror.com/shuffling/

This article fails to explain why someone should explicitly reach for an RNG over PRNG.

It also suggests os.urandom as a Python RNG which (as the name suggests) uses /dev/urandom or the getrandom() syscall, both of which are PRNGs

What do you mean by just "RNG"? Hardware ("true")?

> This article fails to explain why someone should explicitly reach for an RNG over PRNG.

There aren't a lot of cases where you need to explicitly reach for a non-PRNG over a PRNG, and if you do need it, you most likely know it. What does often make a lot of sense is using a PRNG that is seeded from a non-PRNG.

> It also suggests os.urandom as a Python RNG which (as the name suggests) uses /dev/urandom or the getrandom() syscall, both of which are PRNGs

So, that's not ENTIRELY accurate. At least on Linux, while /dev/urandom uses a PRNG, but it is fed from the entropy pool. So unless you consume the entropy pool of a system, it has all the randomness of /dev/random. The difference is that /dev/random blocks when you run out of entropy, while /dev/urandom will just keep feeding output generated purely from the PRNG until more entropy becomes available.

There are some notable exceptions, but in most cases pulling from /dev/urandom is the right choice.

I don't think this "PRNG" vs. "RNG" distinction is doing us much good. There's no meaningful difference in the mechanics of how urandom and random serve unpredictable bits. There is also no such thing as "running out of entropy".

What do you interpret the output of `cat /proc/sys/kernel/random/entropy_avail` to mean?

Nothing.

> There is also no such thing as "running out of entropy".

Hear hear. There is, indeed, no such thing as running out of entropy in a modern PRNG's state.

> I don't think this "PRNG" vs. "RNG" distinction is doing us much good.

But it's still nice to seed and periodically reseed a PRNG w/ entropy from an RNG. So there is a distinction between PRNG and RNG to be made, and we should make it. What we really want is to always have an RNG-seeded PRNG, and to always use the PRNG not the RNG.

> Hear hear. There is, indeed, no such thing as running out of entropy in a modern PRNG's state.

Yes, of course. PRNG's are about producing random data from a seed. But /dev/random & /dev/urandom isn't just a PRNG.

> What we really want is to always have an RNG-seeded PRNG, and to always use the PRNG not the RNG.

Which is effectively what is going on with /dev/random & /dev/urandom

At the point where you're simply equating /dev/random and /dev/urandom, you're no longer really disagreeing with anybody here. The only difference between the two is that /dev/random keeps a metric on how many bits its vended, and blocks waiting for rekeying when that metric gets too high. That's more or less a nonsensical thing to do.

I'm definitely not saying what /dev/random does makes sense. ;-)

I think I understand what you were getting at by "there is no such thing as running out of entropy". Would you say there is such thing as "not having adequate entropy"?

Not really. A CSPRNG is either initialized properly or it isn't. Once it is, entropy has ceased to be a concern. The original LRNG design misapprehends the purpose of continuous "entropy collection", which is about post-compromise security (it's essentially a rekeying operation), and not about any kind of cryptographic exhaustion.

But /dev/urandom will provide you with random numbers even if initialization has not completed, whereas /dev/random will not.

It's best to think of this as an OS/distro detail; if you can reasonably expect /dev/urandom to give you insecure bits, your distro has a vulnerability.

That said: today you'd just use some variant of getrandom.

> It's best to think of this as an OS/distro detail; if you can reasonably expect /dev/urandom to give you insecure bits, your distro has a vulnerability.

Isn't that more a function of hardware than software? The hardware random number generators on modern CPUs pretty much eliminate the need to worry about entropy...

No, this has nothing at all to do with hardware; the state of play is the same on machines that don't have instructions like RDRAND.

I think I still don't understand. Can you explain why it is not a hypothetical problem on a deterministic virtual machine?

/dev/random does not block when 'out of entropy'. 'Running out of entropy' isn't something that can happen, and /dev/random will only block if the RNG hasn't been initialized (short enough after boot to not matter).

See Jason Donenfeld's authoritative talk on the Linux RNG for details: https://youtu.be/-_yzaSp2xtY

I'll have to look at the talk, but I've had first hand experience with that behaviour from /dev/random. Perhaps it has changed over time.

I just checked the source code, and it appears that the entropy pool is alive and well and that /dev/random still waits for enough entropy to collect in the pool before providing more data for consumption.

https://github.com/torvalds/linux/blob/48b1320a674e1ff5de2fa...

The "wait_for_random_bytes" function is still there: https://github.com/torvalds/linux/blob/48b1320a674e1ff5de2fa...

Sure, I maybe should’ve noted that. But my key point is that the article tells you that you should use an RNG (without reason) rather than a PRNG, but then ends up listing something that is an (RNG-initialized) PRNG in the RNG section.

TL;DR he article has glaring inconsistencies and shouldn’t be regarded reliable

It was indeed a little... bizarre.

All this, and the nuclear business is still using variants of LCGs from 60 years ago [1] for Monte Carlo simulations.

In this case, their speed, repeatability and “good enough” statistical properties haven’t motivated much to change.

1. https://www.osti.gov/biblio/976209

Which is interesting, because for MC simulations for rendering (path tracing for example) fast and high quality random numbers are very important...

Although there are alternatives like using low discrepancy sequences (Halton, Sobol) which don't explicitly need the random number values generated from a PRNG itself which are used as well...

If I'm using the random routines from libsodium is that good enough?

Yes.

I wish the table of recommendations contained links. Searching some of those packages gives me sketchy deps I would not trust.

In PHP, at least, random_bytes() is faster than their "high quality" example.

How does the quality of random_bytes() compare?

The manual says it uses high-quality sources

https://www.php.net/manual/en/function.random-bytes.php

Edit: the PHP docs seem to meet the requirements from the article but, the article has a different recommendation (odd?, Maybe I missed something)

It uses the OS's cryptographic RNG.

nanorand for rust!

edit: now after reading about rand_xoshiro i'm curious to try it out

Reply on news.ycombinator.com