7 ms·

Random Number Generator Recommendations for Applications

66 points by rdpintqogeogsaa 3y ago

some_furry 3y ago
In PHP, at least, random_bytes() is faster than their "high quality" example.
- jagged-chisel 3y ago
  How does the quality of random_bytes() compare?
  - djbusby 3y ago
    The manual says it uses high-quality sources https://www.php.net/manual/en/function.random-bytes.php 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)
  - some_furry 3y ago
    It uses the OS's cryptographic RNG.
rootw0rm 3y ago
nanorand for rust! edit: now after reading about rand_xoshiro i'm curious to try it out
djbusby 3y ago
If I'm using the random routines from libsodium is that good enough?
- tptacek 3y ago
  Yes.
wepple 3y ago
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
- deleted 3y ago
  [deleted]
- gregmac 3y ago
  What do you mean by just "RNG"? Hardware ("true")?
- cbsmith 3y ago
  > 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.
  - tptacek 3y ago
    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".
    - cbsmith 3y ago
      What do you interpret the output of `cat /proc/sys/kernel/random/entropy_avail` to mean?
fastneutron 3y ago
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 https://www.osti.gov/biblio/976209
- berkut 3y ago
  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...
0cf8612b2e1e 3y ago
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.
- charcircuit 3y ago
  This sounds similar https://github.com/ech0ii/forceitbox 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-csgojackpots-weak-rng/ https://jonasnick.github.io/blog/2015/07/08/exploiting-csgoj...
- Tangurena2 3y ago
  This is probably the article you are looking for: https://www.developer.com/guides/how-we-learned-to-cheat-at-online-poker-a-study-in-software-security/ 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/ https://blog.codinghorror.com/shuffling/
local_crmdgeon 3y ago
I wish the table of recommendations contained links. Searching some of those packages gives me sketchy deps I would not trust.
FabHK 3y ago
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/ https://prng.di.unimi.it/ [2] https://www.pcg-random.org/ https://www.pcg-random.org/ [3] https://pcg.di.unimi.it/pcg.php https://pcg.di.unimi.it/pcg.php And the reply https://www.pcg-random.org/posts/on-vignas-pcg-critique.html https://www.pcg-random.org/posts/on-vignas-pcg-critique.html [4] https://arxiv.org/abs/1910.06437 https://arxiv.org/abs/1910.06437 [5] https://docs.julialang.org/en/v1/stdlib/Random/ https://docs.julialang.org/en/v1/stdlib/Random/
- adgjlsfhk1 3y ago
  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 :)

some_furry 3y ago

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

jagged-chisel 3y ago
How does the quality of random_bytes() compare?
- djbusby 3y ago
  The manual says it uses high-quality sources https://www.php.net/manual/en/function.random-bytes.php 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)
- some_furry 3y ago
  It uses the OS's cryptographic RNG.

rootw0rm 3y ago

nanorand for rust! edit: now after reading about rand_xoshiro i'm curious to try it out

djbusby 3y ago

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

tptacek 3y ago
Yes.

wepple 3y ago

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

deleted 3y ago
[deleted]
gregmac 3y ago
What do you mean by just "RNG"? Hardware ("true")?
cbsmith 3y ago
> 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.
- tptacek 3y ago
  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".
  - cbsmith 3y ago
    What do you interpret the output of `cat /proc/sys/kernel/random/entropy_avail` to mean?

fastneutron 3y ago

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 https://www.osti.gov/biblio/976209

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

0cf8612b2e1e 3y ago

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.

charcircuit 3y ago
This sounds similar https://github.com/ech0ii/forceitbox 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-csgojackpots-weak-rng/ https://jonasnick.github.io/blog/2015/07/08/exploiting-csgoj...
Tangurena2 3y ago
This is probably the article you are looking for: https://www.developer.com/guides/how-we-learned-to-cheat-at-online-poker-a-study-in-software-security/ 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/ https://blog.codinghorror.com/shuffling/

local_crmdgeon 3y ago

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

FabHK 3y ago

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/ https://prng.di.unimi.it/ [2] https://www.pcg-random.org/ https://www.pcg-random.org/ [3] https://pcg.di.unimi.it/pcg.php https://pcg.di.unimi.it/pcg.php And the reply https://www.pcg-random.org/posts/on-vignas-pcg-critique.html https://www.pcg-random.org/posts/on-vignas-pcg-critique.html [4] https://arxiv.org/abs/1910.06437 https://arxiv.org/abs/1910.06437 [5] https://docs.julialang.org/en/v1/stdlib/Random/ https://docs.julialang.org/en/v1/stdlib/Random/

adgjlsfhk1 3y ago
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 :)