4 ms·

So, what should we be using instead?

by wnoise 6y ago

jeffbee 6y ago
The paper is a bit light on its recommendation, but it seems to favor xoshiro256++. Others might suggest Randen. http://prng.di.unimi.it/ http://prng.di.unimi.it/ https://arxiv.org/pdf/1810.02227.pdf https://arxiv.org/pdf/1810.02227.pdf
- ajross 6y ago
  Yeah, the xorshiro family are the current cool kids. But really: use whatever your library provides. Despite the protests in the article, MT is just fine. It's not slow. It's state requirements are not that high. It's quality is not actually bad in any way that typical applications (yes, even crypto) care about. This is a mature area. It's last revolution was more than two decades ago when we walked away from LCRNGs, and frankly not much has really changed since. It's not worth your time. But yeah, if you have to pick something pick xorshiro.
  - owenmarshall 6y ago
    > It's quality is not actually bad in any way that typical applications (yes, even crypto) care about. > observing a sufficient number of iterations (624 in the case of MT19937, since this is the size of the state vector from which future iterations are produced) allows one to predict all future iterations. https://en.m.wikipedia.org/wiki/Mersenne_Twister https://en.m.wikipedia.org/wiki/Mersenne_Twister Care to square that circle?
    - lifthrasiir 6y ago
      The MT19937 state is a batch of 624 32-bit numbers which gets tampered and returned by the generator in the order. The tampering function is invertible, so each group of 624 successive numbers directly corresponds to the state.
    - ajross 6y ago
      State extraction is possible with all RNGs to varying extents. These are not stream ciphers. Good seeding remains important always, and that's part of the crypto protocol, not the RNG. This is not a problem for using MT responsibly in things like key generation, etc... Again: don't sweat this. If you are competent to write your own crypto code and have a good argument for xorshiro or whatever, then use that. If you just need a random number for whatever reason, use your library and don't bother with the advice in the linked article.
      - tzs 6y ago
        Good libraries have more than one random number generator. Yes, use your library if you are not competent to write your own or don't want to, but use the right library function. For example don't use random.randint() in Python if you need a random integer for crypto. Use random.SystemRandom().randint(). The former uses Mersenne Twister and is predictable. The latter uses os.urandom() for its underlying random bytes, which uses an OS-specific random source (/dev/urandom on Unix and Unix-like OSes) and should be sufficiently unpredictable for all cryptographic uses. There is also the secrets library in Python 3.6 and later. It's not better than random.SystemRandom, it's just a different interface to the OS secure random number generator. If you want your code to work unmodified on Python before 3.6 it is fine to use random.SystemRandom (or if you like its interface more).
        ajross 6y ago
        > For example don't use random.randint() in Python if you need a random integer for crypto. If you need a random number "for crypto", you should be using a crypto library's key generation function or whatever. What you describe is writing a crypto protocol, and that's way out of the realm of discussion here. (But yes: you don't naively use a PRNG of any type for that. The SystemRandom() utility hooks the OS entropy pool.)
        maqp 6y ago
        There are situations where the Pyhton random module can provide easy API for cryptographically unpredictable events. E.g. you can pick random words for passphrase from wordlist with random.SystemRandom().choice(word_list). SystemRandom is a CSPRNG. It's of course incredibly dangerous that you can accidentally use MT by forgetting to put in the SystemRandom() part. random.choice(word_list) works as well and doesn't fail tests. It would be really important to make all RNGs cryptographically secure unless explicitly stated that the RNG must be very fast at the cost of predictability, and the naming should reflect that, e.g. insecure_scientific_random.randint() for Monte Carlo simulations etc.
    - loeg 6y ago
      GP is just wrong (or misspoken); MT should not be used for cryptographic purposes.
zucker42 6y ago
The two most recommended options are variants of Xorshiro and PCG. There's a small comparison of the options in Rust's rand crate which I assume is neutral here: https://rust-random.github.io/book/guide-rngs.html https://rust-random.github.io/book/guide-rngs.html Note that the writer of this paper is a author of Xorshiro, so that might influence his recommendation.
- loeg 6y ago
  Similar comparison from the author of the PCG family: https://www.pcg-random.org/posts/other-good-options.html https://www.pcg-random.org/posts/other-good-options.html She's also written several times about flaws in various xorshift/xorshiro-family RNGs, e.g.: https://www.pcg-random.org/posts/xoshiro-repeat-flaws.html https://www.pcg-random.org/posts/xoshiro-repeat-flaws.html https://www.pcg-random.org/posts/implausible-output-from-xoshiro256.html https://www.pcg-random.org/posts/implausible-output-from-xos... https://www.pcg-random.org/posts/a-quick-look-at-xoshiro256.html https://www.pcg-random.org/posts/a-quick-look-at-xoshiro256.... https://www.pcg-random.org/posts/xoroshiro-fails-truncated.html https://www.pcg-random.org/posts/xoroshiro-fails-truncated.h...
loeg 6y ago
PCG. Small state requirements, very fast, very good distribution: https://www.pcg-random.org/index.html https://www.pcg-random.org/index.html
gilgoomesh 6y ago
The author of the paper is the author of Xoroshiro128+ https://en.wikipedia.org/wiki/Xoroshiro128%2B https://en.wikipedia.org/wiki/Xoroshiro128%2B

So, what should we be using instead?

by wnoise 6y ago

So, what should we be using instead?

The paper is a bit light on its recommendation, but it seems to favor xoshiro256++. Others might suggest Randen. http://prng.di.unimi.it/ http://prng.di.unimi.it/ https://arxiv.org/pdf/1810.02227.pdf https://arxiv.org/pdf/1810.02227.pdf

ajross 6y ago
Yeah, the xorshiro family are the current cool kids. But really: use whatever your library provides. Despite the protests in the article, MT is just fine. It's not slow. It's state requirements are not that high. It's quality is not actually bad in any way that typical applications (yes, even crypto) care about. This is a mature area. It's last revolution was more than two decades ago when we walked away from LCRNGs, and frankly not much has really changed since. It's not worth your time. But yeah, if you have to pick something pick xorshiro.
- owenmarshall 6y ago
  > It's quality is not actually bad in any way that typical applications (yes, even crypto) care about. > observing a sufficient number of iterations (624 in the case of MT19937, since this is the size of the state vector from which future iterations are produced) allows one to predict all future iterations. https://en.m.wikipedia.org/wiki/Mersenne_Twister https://en.m.wikipedia.org/wiki/Mersenne_Twister Care to square that circle?
  - lifthrasiir 6y ago
    The MT19937 state is a batch of 624 32-bit numbers which gets tampered and returned by the generator in the order. The tampering function is invertible, so each group of 624 successive numbers directly corresponds to the state.
  - ajross 6y ago
    State extraction is possible with all RNGs to varying extents. These are not stream ciphers. Good seeding remains important always, and that's part of the crypto protocol, not the RNG. This is not a problem for using MT responsibly in things like key generation, etc... Again: don't sweat this. If you are competent to write your own crypto code and have a good argument for xorshiro or whatever, then use that. If you just need a random number for whatever reason, use your library and don't bother with the advice in the linked article.
    - tzs 6y ago
      Good libraries have more than one random number generator. Yes, use your library if you are not competent to write your own or don't want to, but use the right library function. For example don't use random.randint() in Python if you need a random integer for crypto. Use random.SystemRandom().randint(). The former uses Mersenne Twister and is predictable. The latter uses os.urandom() for its underlying random bytes, which uses an OS-specific random source (/dev/urandom on Unix and Unix-like OSes) and should be sufficiently unpredictable for all cryptographic uses. There is also the secrets library in Python 3.6 and later. It's not better than random.SystemRandom, it's just a different interface to the OS secure random number generator. If you want your code to work unmodified on Python before 3.6 it is fine to use random.SystemRandom (or if you like its interface more).
      - ajross 6y ago
        > For example don't use random.randint() in Python if you need a random integer for crypto. If you need a random number "for crypto", you should be using a crypto library's key generation function or whatever. What you describe is writing a crypto protocol, and that's way out of the realm of discussion here. (But yes: you don't naively use a PRNG of any type for that. The SystemRandom() utility hooks the OS entropy pool.)
        maqp 6y ago
        There are situations where the Pyhton random module can provide easy API for cryptographically unpredictable events. E.g. you can pick random words for passphrase from wordlist with random.SystemRandom().choice(word_list). SystemRandom is a CSPRNG. It's of course incredibly dangerous that you can accidentally use MT by forgetting to put in the SystemRandom() part. random.choice(word_list) works as well and doesn't fail tests. It would be really important to make all RNGs cryptographically secure unless explicitly stated that the RNG must be very fast at the cost of predictability, and the naming should reflect that, e.g. insecure_scientific_random.randint() for Monte Carlo simulations etc.
  - loeg 6y ago
    GP is just wrong (or misspoken); MT should not be used for cryptographic purposes.

zucker42 6y ago

The two most recommended options are variants of Xorshiro and PCG. There's a small comparison of the options in Rust's rand crate which I assume is neutral here: https://rust-random.github.io/book/guide-rngs.html https://rust-random.github.io/book/guide-rngs.html Note that the writer of this paper is a author of Xorshiro, so that might influence his recommendation.

loeg 6y ago
Similar comparison from the author of the PCG family: https://www.pcg-random.org/posts/other-good-options.html https://www.pcg-random.org/posts/other-good-options.html She's also written several times about flaws in various xorshift/xorshiro-family RNGs, e.g.: https://www.pcg-random.org/posts/xoshiro-repeat-flaws.html https://www.pcg-random.org/posts/xoshiro-repeat-flaws.html https://www.pcg-random.org/posts/implausible-output-from-xoshiro256.html https://www.pcg-random.org/posts/implausible-output-from-xos... https://www.pcg-random.org/posts/a-quick-look-at-xoshiro256.html https://www.pcg-random.org/posts/a-quick-look-at-xoshiro256.... https://www.pcg-random.org/posts/xoroshiro-fails-truncated.html https://www.pcg-random.org/posts/xoroshiro-fails-truncated.h...

loeg 6y ago

PCG. Small state requirements, very fast, very good distribution: https://www.pcg-random.org/index.html https://www.pcg-random.org/index.html

gilgoomesh 6y ago

The author of the paper is the author of Xoroshiro128+ https://en.wikipedia.org/wiki/Xoroshiro128%2B https://en.wikipedia.org/wiki/Xoroshiro128%2B