3 ms·

> A Mersenne twister ... is fine for deck shuffling It isn't. Please don't do that! Mersenne Twister is fully reversible given its 624 consecutive outputs (see

by ilya_m 2y ago

> A Mersenne twister ... is fine for deck shuffling It isn't. Please don't do that! Mersenne Twister is fully reversible given its 624 consecutive outputs (see, for instance, this pretty good write-up: https://blog.ollien.com/posts/reverse-mersenne-twister https://blog.ollien.com/posts/reverse-mersenne-twister). In other words, someone who can observe 624 outputs can reconstruct its entire output sequence forward and backward.

bluecalm 2y ago
This is very interesting, thank you! When I was implementing random shuffling I used xoroshiro128+ instead of Mersenne twister and felt pretty good about it but only because it was used for randomness needed for Monte Carlo simulations, not for gambling games where there are potential adversaries looking to break it. Are you aware of how that one (xoroshiro128+) or other pseudo random generators fare against adversaries?
- whyever 2y ago
  Don't use a non-CSPRNG if you worry about adversaries. CSPRNGs are only ca. 10 times larger and roughly as fast if you can use SIMD. According to [1], you only need 4 outputs to predict xoshiro. Predicting PCG is a bit more difficult, but still on the level of "exercise for cryptography students" [2]. [1]: https://www.pcg-random.org/posts/a-quick-look-at-xoshiro256.html https://www.pcg-random.org/posts/a-quick-look-at-xoshiro256.... [2]: https://hal.science/hal-02700791/document https://hal.science/hal-02700791/document
pclmulqdq 2y ago
You're right that you wouldn't want to use any non-cryptographic PRNG for gambling games of any significant stake. Many low-stakes games will use them, relying on having many different players connected to one result source to protect themselves. However, "624 consecutive outputs" is not the way to think about it, because those outputs are truncated to narrow integers. A single shuffled deck leaks about 230 bits of information, and backing out the state of a Mersenne twister needs several thousand bits of information.

by ilya_m 2y ago

bluecalm 2y ago

This is very interesting, thank you! When I was implementing random shuffling I used xoroshiro128+ instead of Mersenne twister and felt pretty good about it but only because it was used for randomness needed for Monte Carlo simulations, not for gambling games where there are potential adversaries looking to break it. Are you aware of how that one (xoroshiro128+) or other pseudo random generators fare against adversaries?

whyever 2y ago
Don't use a non-CSPRNG if you worry about adversaries. CSPRNGs are only ca. 10 times larger and roughly as fast if you can use SIMD. According to [1], you only need 4 outputs to predict xoshiro. Predicting PCG is a bit more difficult, but still on the level of "exercise for cryptography students" [2]. [1]: https://www.pcg-random.org/posts/a-quick-look-at-xoshiro256.html https://www.pcg-random.org/posts/a-quick-look-at-xoshiro256.... [2]: https://hal.science/hal-02700791/document https://hal.science/hal-02700791/document

pclmulqdq 2y ago

You're right that you wouldn't want to use any non-cryptographic PRNG for gambling games of any significant stake. Many low-stakes games will use them, relying on having many different players connected to one result source to protect themselves. However, "624 consecutive outputs" is not the way to think about it, because those outputs are truncated to narrow integers. A single shuffled deck leaks about 230 bits of information, and backing out the state of a Mersenne twister needs several thousand bits of information.