9 ms·

Speaking of which,... does anybody here know a portable, easy to use, and high quality, deterministic random number generator? It is a requirement that you mu

Speaking of which,... does anybody here know a portable, easy to use, and high quality, deterministic random number generator? It is a requirement that you must get the exactly the same sequence of pseudo-random numbers on any architecture (depending on a user-settable seed). I use a hand-crafted (two-line) linear congruential generator, but always feel a bit uneasy about that.

throw0101a 7y ago
Any stream cipher? If you use the same symmetric key and nonce, the output bit stream should be the same every time. This is how OpenBSD's arc4random(3) started out: using the output of RC4 and stirring the entropy pool regularly to ensure forward security. (They've since switched to ChaCha20.) * https://man.openbsd.org/arc4random.3 https://man.openbsd.org/arc4random.3 Remove the stirring and you've got deterministic output. Security comes from the entropy of the initial conditions.
- enriquto 7y ago
  Yes, something like that would be great! But does it come packaged nicely? So that I can compile it out of the box on windows, linux, macos, android?
  - jedisct1 7y ago
    The `randombytes_deterministic()` function from libsodium or libhydrogen does exactly what the name suggests.
  - SAI_Peregrinus 7y ago
    Monocypher is a decent fit here. Just run its ChaCha20 with (a hash of) your seed as the key. Larger libraries (libsodium, NaCl, etc) are decent too, but bigger.
    - tptacek 7y ago
      Alternative opinion: Don't use Monocypher. Much less safe than libsodium.
  - slrz 7y ago
    Libbsd includes it. https://libbsd.freedesktop.org/ https://libbsd.freedesktop.org/
wahern 7y ago
What's high quality depends on your requirements and usage. But, for example, you can use a Feistel construction to generate a random, non-repeating sequence that is as unpredictable as the mixing function. I've used this technique instead of a Fisher–Yates shuffle, trading higher CPU for lower space, for generating 16-bit DNS QIDs.
- enriquto 7y ago
  Yes, I know many nice algorithms with "high quality" properties. My question is about actual implementations: is there a canonical github repo that everybody is using for this need, or I have to write or adapt the code myself?
ChrisLomont 7y ago
PCG generators are very good, very fast, and decently random, don't suffer (AFAIK) from bad seeds like Mersenne Twister, mix well, have small state, and have selectable periods of about any size. They are vastly better than LCGs. I use a 64 bit one and a 128 bit one for all sorts of work. These are not crypto, so don't use them for that. For non-crypto I have seen no better PRNG than these (and I've followed and written on this space for a long time). Code available on github. http://www.pcg-random.org/ http://www.pcg-random.org/
- enriquto 7y ago
  That's exactly what I was looking for! Is it your code?
  - ChrisLomont 7y ago
    Not my code, but I have versions I've written for various platforms/languages that I use.
- tptacek 7y ago
  When you say "not crypto, don't use them for that", you mean "don't use them for any situation in which the security of the randomness matters", right?
  - ChrisLomont 7y ago
    Yep - which is a lot, if not the vast majority, of random numbers generated. Also, I'm answering a question by someone that looks like they want precisely this type of PRNG. There is no need to make a mess with CPRNGs.
ermir 7y ago
You can use a sequence of AES encryptions with a pre-shared seed, the quality of the random numbers will be among the highest you can get. You can find AES implementations all over the place, for basically any platform. You would do something like rng1 = AES(seed); rng2 = AES(rng1); rng3 = AES(rng2);
- ermir 7y ago
  To add to my answer, you can also do something like this: randomNumber = AES(secretKey, counter), where counter is just a sequence number that you can share in the open. Anyone without the key would not be able to generate the random number with just the counter only.
dfox 7y ago
That depends on what you use the PRNG for. For cryptographic applications what you want is as previously noted just some arbitrary secure stream function (with block cipher in OFB or CTR mode being particularly convenient way to obtain such cipher). Bear in mind that for cryptographic applications it is often important whether the state can be determined by observing the output and whether the state can be rewound back (which then necessitates choosing stream cipher that satisfies these requirements or using more complex construction. Most notably block ciphers in CTR/OFB mode does not satisfy this and ChaCha/Salsa also does not as it is essentially block cipher in CTR mode). Interesting modern construction would involve Keccak-style sponge functions, which are kind of universal cryptographic primitive that is usable as hash, MAC and PRNG/stream cipher all at once depending on mode of operation. For monte-carlo simulations you want something that is reasonably fast and has large state space. Mersenne Twister is common choice, although XorShift is significantly faster and usually has state space that is large enought. For randomized distributed simulations (read: lock-step realtime multiplayer games) you don't care about the output quality of the output that much and LCG tends to be sufficient, althought also in this case XorShift would be probably better as it has comparable performance and significantly better output quality. All the mentioned algorithms are by definition deterministic and discounting implementation errors platform independent.
- tptacek 7y ago
  Plenty of CSRNGs are built from AES-CTR and ChaCha20. There's probably no good reason to prefer XorShift over a cryptographic random bit generator that you can seed directly.
  - pcwalton 7y ago
    For Monte Carlo simulations, CSRNGs are too slow. Xorshift is incredibly fast. You wouldn't want to use a CSRNG for path tracing rendering, for example; you're calling the RNG many times per ray and shooting dozens or hundreds of rays per pixel. We've dealt with this in Rust—people love to write Monte Carlo simulations as language benchmarks, and Rust used to get dinged for preferring CSRNGs.
luizfelberti 7y ago
I don't know what you want this for exactly, so definitely don't use my suggestion for crypto purposes. However... If what you want is just to add some uniform, seemingly random behavior to something (e.g. a game, generate some noise, whatever), I've used the Wolfenstein3D's FizzleFade effect algorithm [0] in the past. It's boringly easy and works like a charm. [0] http://fabiensanglard.net/fizzlefade/index.php http://fabiensanglard.net/fizzlefade/index.php
deleted 7y ago
[deleted]

throw0101a 7y ago

Any stream cipher? If you use the same symmetric key and nonce, the output bit stream should be the same every time. This is how OpenBSD's arc4random(3) started out: using the output of RC4 and stirring the entropy pool regularly to ensure forward security. (They've since switched to ChaCha20.) * https://man.openbsd.org/arc4random.3 https://man.openbsd.org/arc4random.3 Remove the stirring and you've got deterministic output. Security comes from the entropy of the initial conditions.

enriquto 7y ago
Yes, something like that would be great! But does it come packaged nicely? So that I can compile it out of the box on windows, linux, macos, android?
- jedisct1 7y ago
  The `randombytes_deterministic()` function from libsodium or libhydrogen does exactly what the name suggests.
- SAI_Peregrinus 7y ago
  Monocypher is a decent fit here. Just run its ChaCha20 with (a hash of) your seed as the key. Larger libraries (libsodium, NaCl, etc) are decent too, but bigger.
  - tptacek 7y ago
    Alternative opinion: Don't use Monocypher. Much less safe than libsodium.
- slrz 7y ago
  Libbsd includes it. https://libbsd.freedesktop.org/ https://libbsd.freedesktop.org/

wahern 7y ago

What's high quality depends on your requirements and usage. But, for example, you can use a Feistel construction to generate a random, non-repeating sequence that is as unpredictable as the mixing function. I've used this technique instead of a Fisher–Yates shuffle, trading higher CPU for lower space, for generating 16-bit DNS QIDs.

enriquto 7y ago
Yes, I know many nice algorithms with "high quality" properties. My question is about actual implementations: is there a canonical github repo that everybody is using for this need, or I have to write or adapt the code myself?

ChrisLomont 7y ago

PCG generators are very good, very fast, and decently random, don't suffer (AFAIK) from bad seeds like Mersenne Twister, mix well, have small state, and have selectable periods of about any size. They are vastly better than LCGs. I use a 64 bit one and a 128 bit one for all sorts of work. These are not crypto, so don't use them for that. For non-crypto I have seen no better PRNG than these (and I've followed and written on this space for a long time). Code available on github. http://www.pcg-random.org/ http://www.pcg-random.org/

enriquto 7y ago
That's exactly what I was looking for! Is it your code?
- ChrisLomont 7y ago
  Not my code, but I have versions I've written for various platforms/languages that I use.
tptacek 7y ago
When you say "not crypto, don't use them for that", you mean "don't use them for any situation in which the security of the randomness matters", right?
- ChrisLomont 7y ago
  Yep - which is a lot, if not the vast majority, of random numbers generated. Also, I'm answering a question by someone that looks like they want precisely this type of PRNG. There is no need to make a mess with CPRNGs.

ermir 7y ago

You can use a sequence of AES encryptions with a pre-shared seed, the quality of the random numbers will be among the highest you can get. You can find AES implementations all over the place, for basically any platform. You would do something like rng1 = AES(seed); rng2 = AES(rng1); rng3 = AES(rng2);

ermir 7y ago
To add to my answer, you can also do something like this: randomNumber = AES(secretKey, counter), where counter is just a sequence number that you can share in the open. Anyone without the key would not be able to generate the random number with just the counter only.

dfox 7y ago

That depends on what you use the PRNG for. For cryptographic applications what you want is as previously noted just some arbitrary secure stream function (with block cipher in OFB or CTR mode being particularly convenient way to obtain such cipher). Bear in mind that for cryptographic applications it is often important whether the state can be determined by observing the output and whether the state can be rewound back (which then necessitates choosing stream cipher that satisfies these requirements or using more complex construction. Most notably block ciphers in CTR/OFB mode does not satisfy this and ChaCha/Salsa also does not as it is essentially block cipher in CTR mode). Interesting modern construction would involve Keccak-style sponge functions, which are kind of universal cryptographic primitive that is usable as hash, MAC and PRNG/stream cipher all at once depending on mode of operation. For monte-carlo simulations you want something that is reasonably fast and has large state space. Mersenne Twister is common choice, although XorShift is significantly faster and usually has state space that is large enought. For randomized distributed simulations (read: lock-step realtime multiplayer games) you don't care about the output quality of the output that much and LCG tends to be sufficient, althought also in this case XorShift would be probably better as it has comparable performance and significantly better output quality. All the mentioned algorithms are by definition deterministic and discounting implementation errors platform independent.

tptacek 7y ago
Plenty of CSRNGs are built from AES-CTR and ChaCha20. There's probably no good reason to prefer XorShift over a cryptographic random bit generator that you can seed directly.
- pcwalton 7y ago
  For Monte Carlo simulations, CSRNGs are too slow. Xorshift is incredibly fast. You wouldn't want to use a CSRNG for path tracing rendering, for example; you're calling the RNG many times per ray and shooting dozens or hundreds of rays per pixel. We've dealt with this in Rust—people love to write Monte Carlo simulations as language benchmarks, and Rust used to get dinged for preferring CSRNGs.

luizfelberti 7y ago

I don't know what you want this for exactly, so definitely don't use my suggestion for crypto purposes. However... If what you want is just to add some uniform, seemingly random behavior to something (e.g. a game, generate some noise, whatever), I've used the Wolfenstein3D's FizzleFade effect algorithm [0] in the past. It's boringly easy and works like a charm. [0] http://fabiensanglard.net/fizzlefade/index.php http://fabiensanglard.net/fizzlefade/index.php

deleted 7y ago

[deleted]