10 ms·
A Family of Better Random Number Generators
- EE84M3i 6y agoThey describe rc4 as secure, which it hasn't been considered for years, so I'm not sure how seriously to take this site
- andreareina 6y agoSpeaking of rc4, what are the reproducibility issues? Quick search on mobile didn't turn anything up. Is it just the "alleged" designation, i.e. no confirmation that it implements Rivest's original cipher?
- JoachimS 6y agoIRRC The real RC4 was licensed to Novell and used in Notes. People was later able to use the leaked, alleged rc4 algorithm to decrypt messages encrypted by Notes. That basically confirmed that the algorithms are the same.
- JackeJR 6y ago"secure" in the website refers to predictability. Do you have a source on how to predict rc4?
- hannob 6y agoThe RC4 stream has biases. This means you have something like "bit X is slightly more likely to be 1 than 0". This isn't "predictability" in a sense that you know what it'll be, but it's bad enough for certain applications. How much it matters probably depends how exactly you design your RNG, but it seems like playing with fire and is easily avoidable by using a cipher without that property.
- febstar 6y agoI believe numpy.random uses PCG by default. https://numpy.org/doc/stable/reference/random/index.html https://numpy.org/doc/stable/reference/random/index.html
- andreareina 6y agoWhat applications require unpredictability where you wouldn't go full csprng?
- uluyol 6y agoRequest back off / retries, any sort of simulation, various load balancing algorithms, randomized algorithms, fuzzing/testing, ...
- Thorrez 6y agoWhy does back off / retry require unpredictability?
- thiagocsf 6y agoTo avoid a stampede of requests by synchronised clients.
- Thorrez 6y agoThat doesn't require unpredictability. For example, Mersenne Twister seeded from /dev/urandom would work fine for that, even though it's predictable because Mersenne Twister is predictable.
- mytailorisrich 6y agoIt does not require true unpredictability, the key aim being to have each host retry at a different time. There is no need to cryptographic strength, which is costly, and pseudo-randomness is enough and much cheaper.
- Thorrez 6y agoI think you're agreeing with me that unpredictability isn't necessary (e.g. Mersenne Twister would work fine).
- deleted 6y ago[deleted]
- Tipewryter 6y agoFor "Arc4Random" it says "Reproducible Results: Not Always". Can an algorithm really produce a non-reproducible result?
- stonogo 6y agoThere are implementations of Arc4Random which introduce entropy during generation. So, it's not a design feature of the algorithm as much as it is an implementation detail.
- jwilk 6y agohttps://www.pcg-random.org/other-rngs.html#arc4random https://www.pcg-random.org/other-rngs.html#arc4random explains what they meant: > The BSD implementations (which are the only widely used ones) have several additional issues > • No facility for a user-provided seed, preventing programs from getting reproducible results > • Periodically “stirs” the generator using kernel-provided entropy; this code must be removed if reproducible results desired (and is removed from the C++ adaptation I created for testing purposes)
- Thorrez 6y agoThanks for the info. I wonder why the openssl implementation wasn't used: https://stackoverflow.com/q/9329631/830749 https://stackoverflow.com/q/9329631/830749
- AlotOfReading 6y agoDepends on what you're counting for determinism. Arc4Random uses the system entropy pool, so it's non-deterministic from a user perspective. In a more direct sense, yes. If you're allowed to keep secrets (like internal state), it's possible to produce random numbers algorithmically for certain (weak) definitions of random, even with a deterministic machine. A simple example of this would be sequential bits of a normal number. As you strengthen your definition of randomness you pretty quickly get into non-computable territory though.
- lucioperca 6y agoSounds pretty undecidable to me to proof that a pseudo number generator has a challenging prediction difficulty.
- jacobolus 6y agoHere’s a Javascript implementation, https://observablehq.com/@jrus/permuted-congruential-generator https://observablehq.com/@jrus/permuted-congruential-generat... It’s a bit of a pain because Javascript can’t do native 64-bit integer arithmetic. But it should still be fast enough for most purposes.
- celrod 6y agoXoshiro over PCG arguments: http://pcg.di.unimi.it/pcg.php http://pcg.di.unimi.it/pcg.php Response by the author: https://www.pcg-random.org/posts/on-vignas-pcg-critique.html https://www.pcg-random.org/posts/on-vignas-pcg-critique.html Personally, I use a SIMD Xoshiro256+ when I want a solid and fast RNG (although I mostly use Julia's default -- a MersenneTwister).
- BlackFly 6y agoThanks for digging this up. I was curious about exactly this.
- GolDDranks 6y agoWhy does Julia use Mersenne Twister as default? I gather that it's quite bad by modern standards?
- shele 6y agoIt _has_ a cool name, tough...
- logos01 6y agoAnd the pcg page has pretty colors
- versteegen 6y ago"quite bad" is quite an overstatement; its quality isn't a problem for many real use cases. It's quite slow compared to the likes of PCG though.
- logos01 6y agoJulia uses dSFMT, which is as fast as xoshiro on vigna own benchmark page. I would not call that slow.
- GolDDranks 6y agoRight, a bad phrasing from my part; I didn't actually mean the distribution, but more like... the bang for the buck. Why would you use slow generator as a default, if you don't even get good distribution?
- s9w 6y agoThe Drama between the author of PCG (u/ProfONeill) and the author of xoshiro (u/sebastianovigna) is one of the more entertanining parts of the C++ community. Too bad that despite that fierce competition, the <random> standard header itself is universally hated.
- littlestymaar 6y agoentertaining isn't really the word I'd use…
- OskarS 6y ago<random> and <chrono> have really been in a death match of "C++ standard libraries that are super-annoyingly C++", but they've both been absolutely destroyed by <range>, i think.
- s9w 6y agoAs in range being better or even worse? I haven't tried it out yet.
- OskarS 6y agoFrom what little I've used it, <range> is a C++ nightmare. Compile times explode and every time you get a tiny type error (which is impossible avoid, because the library is very persnickety about types) you get a bazillion pages of template errors. Concepts and modules (supposedly) fix these issues, and I'm not going to use ranges again until those two are very mature features of C++. Even if you ignore this stuff, it's incredibly "C++ified" in just the worst way, with incredibly obtuse templates and type concepts all over the place.
- steerablesafe 6y agoI agree regarding <random>, but <chrono> is a work of art.
- s9w 6y ago
- whateveracct 6y agoAnd there are Haskell bindings: https://hackage.haskell.org/package/pcg-random https://hackage.haskell.org/package/pcg-random Nice!
- nestorD 6y agoOn random numbers, I found the ideas behind "Parallel Random Numbers: As Easy as 1, 2, 3" [0] (which is implemented in JAX) interesting. Their generator is a mapping between keys and random numbers which get rid of the sequential dependency in the generator making it very easy to run in parallel at a GPU scale. [0]: http://www.thesalmons.org/john/random123/papers/random123sc11.pdf http://www.thesalmons.org/john/random123/papers/random123sc1...
- mratsim 6y agoI've been diving into parallel reproducible PRNG [1] in the end I choose to have a PRNG based on xoshiro and seeding process that could take loop iteration variables [2] for reproducibility: - [1] https://github.com/mratsim/weave/issues/147 https://github.com/mratsim/weave/issues/147 - [2] https://github.com/mratsim/trace-of-radiance/blob/99f7d85/trace_of_radiance/support/rng.nim#L21-L53 https://github.com/mratsim/trace-of-radiance/blob/99f7d85/tr... - Usage for parallel raytracing: https://github.com/mratsim/trace-of-radiance/blob/99f7d85/trace_of_radiance/render.nim#L55-L60 https://github.com/mratsim/trace-of-radiance/blob/99f7d85/tr... Beyond the JAX paper, the Pedigree-based RNG from Leiserson was interesting as well: - http://supertech.csail.mit.edu/papers/dprng.pdf http://supertech.csail.mit.edu/papers/dprng.pdf - https://pdfs.semanticscholar.org/a32c/3b7b8d5d3ebd594bea2d9c0935c1ac7f8e24.pdf https://pdfs.semanticscholar.org/a32c/3b7b8d5d3ebd594bea2d9c... And Haskell's splittable RNG: - http://www.hg.schaathun.net/research/Papers/hgs2015jfp.pdf http://www.hg.schaathun.net/research/Papers/hgs2015jfp.pdf - http://publications.lib.chalmers.se/records/fulltext/183348/local_183348.pdf http://publications.lib.chalmers.se/records/fulltext/183348/... - http://gee.cs.oswego.edu/dl/papers/oopsla14.pdf http://gee.cs.oswego.edu/dl/papers/oopsla14.pdf
- logos01 6y ago100% agree. You can also use chacha or aes the same way. I like it. I wonder however if some streams may not be too extreme with those. https://chasethedevil.github.io/post/more-on-random-number-generators/ https://chasethedevil.github.io/post/more-on-random-number-g...
- rdw 6y agoI used PCG years ago for procedural content generation where random number generation was a bottleneck. It is very fast, so I was happy with it. Additionally the implementation I used[1] is comprehensible enough that I could modify it in various small ways. One property I anecdotally observed about it is that it is a little sensitive to the values you choose for its seed. Too many zero bits or making two generators with nearly-identical seeds would create visible correlation in the outputs. It worked much better if all values were hashed before using them for seeding. [1] https://github.com/tlauterbach/unity-pcg-csharp https://github.com/tlauterbach/unity-pcg-csharp
- m4r35n357 6y agoTinyCC example in README is wrong, should have trailing '-': as in "cat pcg_basic.c pcg32-demo.c | tcc -run -"
- mshachkov 6y agoOne might be interested in https://github.com/wangyi-fudan/wyhash https://github.com/wangyi-fudan/wyhash
- rurban 6y agoRecently added to my dieharder: https://github.com/rurban/dieharder/blob/master/dieharder/wyrand_g210_a.out https://github.com/rurban/dieharder/blob/master/dieharder/wy... but I still need to add more tests to get a better quality comparison against the xoshiro's
- fsiefken 6y agoIs there a fork of Fortune that uses the PCG, Xoshiro or wyhash algorithm? I am not fluent in C or Rust and time constrained, otherwise I would have taken a shot at it https://raw.githubusercontent.com/shlomif/fortune-mod/master/fortune-mod/fortune/fortune.c https://raw.githubusercontent.com/shlomif/fortune-mod/master... https://raw.githubusercontent.com/wapm-packages/fortune/master/src/main.rs https://raw.githubusercontent.com/wapm-packages/fortune/mast... Or better, with an entropy source like rdrand or rdseed?
- moonchild 6y agoRdrand is not generally considered trustable, and the algorithm it uses is not known. The main use for rdrand is to mix it with other entropy sources to produce a seed for another rng.
- rainworld 6y agoStatistical Quality PCG Family Excellent ChaCha20 Good What a joke.
- jwilk 6y agoThe only complaint about ChaCha's statistical properties I could find on <https://www.pcg-random.org/other-rngs.html#id7 https://www.pcg-random.org/other-rngs.html#id7> is: > Fewer rounds result in poor statistical performance; ChaCha2 fails statistical tests badly, and ChaCha4 passes TestU01 but sophisticated mathematical analysis has shown it to exhibit some bias. ChaCha8 (and higher) are believed to be good. Nevertheless, ChaCha needs to go to more work to achieve satisfactory statistical quality than many other generators.
- rainworld 6y agoExhaustive list of valid complaints about ChaCha (and CSPRNGs in general): * too slow (for a scant few applications) * too much state & code (for a scant few applications) * can’t find a nice implementation (there are some, though) Everything else written there is FUD. And this whole "statistical tests" thing is a red herring anyway. There’s a field that concerns itself with "statistical quality"—it’s called cryptography. They have plenty sophisticated mathematical analysis.
- dragontamer 6y agoYou might be surprised. Cryptographic RNGs achieve their strength through large round-counts. ChaCha runs 20x quarter rounds of its algorithm, which means you're basically doing: randomNumber = hash(hash(hash(hash...hash(seed))))))))))) After 80-iterations of your hash function, you'd HOPE it was random looking!! In effect, cryptographic RNGs are built for safety, and have huge safety margins. --------- The "natural" approach to making a non-secure (but faster) RNG is to reduce the hash rounds to a single cycle. IE: instead of running 80-quarter rounds of ChaCha, why not just run 1x quarter-round of ChaCha? Well, it turns out that 1-round of ChaCha20 is utter crap. Completely crap, worse than a LCGRNG. ------ AES is similarly designed for 8+ rounds. In my experiments, it took 4 or 5 rounds before AES would achieve a decent distribution of bits!! It took a fair bit of effort for me to turn AES into a random number generator. I analyzed AES's bit-flow, and designed a "counter function" that worked well with AES's single-round weakness. Even then, I never accomplished a 1-round of AES RNG, I had to use 2-rounds of AES to make a decent bit distribution. In particular: 1-round of AES is only designed to shuffle bits across a 32-bit DWORD. You need the 2nd round (or more) to shuffle the bits to the whole 128-bit group. (That is: the "MixColumns" and "ShiftRows" step of AES, which only really take effect on the 2nd round or later). ----- If anyone could figure out a special "seed" function that can work with AES's single-round weakness, they probably can make a much faster RNG than what I accomplished. Or maybe, people can just be "happy" with 32-bits of well-shuffled bits? A 32-bit RNG (with 128-bit seed) is probably still useful to somebody.
- kevincox 6y agoI've used Pcg32 via https://docs.rs/rand_pcg https://docs.rs/rand_pcg and been quite happy. That being said I don't rely on excellent quality and haven't tested it. One of the main reasons I use it is that the implementation works perfectly in WebAssembly. I use it to deal tiles in my version of online Azul: https://tiles.kevincox.ca https://tiles.kevincox.ca I also used it to simulate the Red7 game for strategy testing: https://gitlab.com/kevincox/red7-sim https://gitlab.com/kevincox/red7-sim
- plopilop 6y agoThe website does not seem to have been updated but the prediction security of PCG has been fully broken recently (and does not rely on the "Challenging" part of the spectrum): https://hal.inria.fr/hal-02700791/ https://hal.inria.fr/hal-02700791/ Hence any cryptographic use of PCG is definitely prohibited
- nimish 6y agoVigna's RNGs are faster and as good statistically so it's not clear why you'd use PCG. They are a neat theoretical construction however I believe they have some serious flaws when attempting to split and construct multiple streams. Honestly though RDRAND is cheap enough that I'd take true randomness over determinism.
- dragontamer 6y agoThe pcg-random methodology is very good. The basis is the following pattern: #1: Have a "counter" of some kind. The simple counter trivially creates a maximum length cycle. "seed++" is one such counter. #2: Have a "hash" that converts the counter into a random number, using a 1-to-1 bijection. There are a great many 1-to-1 bijections. So your RNG is basically: oldSeed = seed; seed = counterFunction(seed); return hash(oldSeed); ------------ I used this methodology to make a pretty fast generator myself. The coding was done in a weekend, but it took some weeks to test: https://github.com/dragontamer/AESRand https://github.com/dragontamer/AESRand For AESRand: "counterFunction" is a SIMD 2x64-bit Add over the XMM register. I chose an odd number arbitrarily (which are just the first 16 prime numbers: 0x01030507...), which will trivially cycle after 2^64 numbers. "hash" is aesenc(aesenc(seed, constant), constant), where constant is an arbitrary (chosen to be the same odd number that was used in the "counterFunction" step). The 2nd parameter to aesend is just an XOR. I also run a 2nd parallel aesdec(aesenc(seed, constant), constant) to generate a 2nd set of 128-bit random numbers, for 256-bits to be made across the hash. Yes, a 128-bit seed "hashes" into a 256-bit random number. Since this passes statistical tests, its probably fine, and this is a good source of instruction-level-parallelism. All in all, I achieved 30GB/sec random numbers. Or 256-bits of random numbers every 3.7 cycles that passes BigCrush, TestU01, and PractRand. -------- AES is a 1-to-1 bijection: that's a necessary condition for AES to be decoded. Though I use AES, this function is NOT cryptographically sound. I'm just using AES because its the fastest high-quality bijection in the entire modern CPU instruction set. x86, ARM, and POWER9 all implement single-cycle AES instructions. It is possible to write a portable AESRand across the different CPUs (ARM, x86, and POWER9). I got far enough to prove that its possible, but then my real work started to ramp up and I had to drop this hobby project. Its very tricky to do so: ARM, x86, and POWER9 implement AESENC slightly differently: shuffling the fundamental steps in different ways. Or in the case of POWER9, it executes in big-endian mode instead of little-endian (like ARM / x86). Redesigning the algorithm to be portable across the shuffled "SubBytes" and "MixColumns" steps between the CPUs is tricky but possible.
- deleted 6y ago[deleted]
- tshoaib 6y agoWould the outputs of these algorithms be considered pseudo-random?