12 ms·

I'd definitely argue that needing a CSRNG is more niche than needing a fast RNG.

by yoklov 11y ago

tedunangst 11y ago
Perpetuates fallacy that CSRNG is not fast.
- johncolanduoni 11y ago
  On many platforms it's several orders of magnitude slower than a fast, dead simple PRNG with very good distributional properties, like xorshift1024* [1]. [1]: http://xorshift.di.unimi.it http://xorshift.di.unimi.it
  - tedunangst 11y ago
    Let's return to the top. How many random bytes do you need per second? Rounded to the nearest billion, of course.
    - pcwalton 11y ago
      If your product is in a competitive environment and is being compared against others in benchmarks of random number generation, the answer is "as many as you can possibly generate". This scenario corresponds to JavaScript engines of major Web browsers.
      - tedunangst 11y ago
        In other words, bullshit breeds bullshit.
        pcwalton 11y ago
        I can't blame V8 engineers for not wanting to regress SunSpider. Sad or not—and, let me tell you, nobody who works on browsers likes this state of affairs when it comes to that benchmark—doing well on the popular benchmarks has to be an engineering goal in the environment browsers find themselves in.
        mmalone 11y ago
        FWIW xorshift1024* would almost certainly be faster than MWC1616 and it has no systematic failures on BigCrush. The only downside is that it uses more memory, but I think we can afford it. If not xorshift64* is also faster than MWC1616 and miles ahead of it in quality.
    - johncolanduoni 11y ago
      For large simulations, this can easily become a bottleneck, which is why those generally use a good non-CS PRNG. In addition, CSPRNGs actually have slightly worse distributional properties than some much faster PRNGs, because the CSPRNG is more focused on being unpredictable. CSPRNGs aren't the end-all be-all of PRNGs, they have their appropriate and inappropriate applications even if we ignore speed.
      - tedunangst 11y ago
        That's not a number. > CSPRNGs actually have slightly worse distributional properties than some much faster PRNGs, because the CSPRNG is more focused on being unpredictable. What does this even mean? Non-uniform distribution for CSRNG is fatal. What is an RNG that has "better" distribution than CSRNG?
        johncolanduoni 11y ago
        > That's not a number. The actually relevant aspect is what percentage of a simulation's time is spent generating random numbers if it's using a CSPRNG. I have had this become a bottleneck in my work, and it's very rare to use CSPRNGs in scientific simulations for this reason. > What does this even mean? Non-uniform distribution for CSRNG is fatal. What is an RNG that has "better" distribution than CSRNG? There are distributional properties other than uniformity, and depending on how you use these numbers (e.g. Monte Carlo kernel form) these can be far more important than linear uniformity. The author briefly mentioned this in the article ("CSPRNGs emphasize unpredictability over all other measures of quality, some of which might be more important for your use case"). Look into the work of George Marsaglia, he wrote the test suites that generate the quality numbers most engineers use to evaluate both CSPRNG and normal PRNGs.
        pbsd 11y ago
        I find it disingenuous to see properties such as equidistribution or low discrepancy being described as 'quality' of a generator. Yes, they make certain Monte Carlo algorithms converge quicker. No, they are not closer to a truly random sequence than a CSPRNG is. The goal of a CSPRNG is to be indistinguishable from true randomness, and a predictor is quite obviously a distinguisher. But so is a statistical test, or any 'nice' property that makes some algorithm behave better. By the way, I think I've said this before, but I'll say it again. I really dislike the usage of the term 'CSPRNG' in these discussions. A CSPRNG is typically understood to be /dev/urandom---an algorithm that not only generates a long sequence of numbers, but also harvests entropy and tries to achieve forward and backward security. But it is also sometimes overloaded to mean a stream cipher, which is a conceptually simpler construct, and also able to be much faster. Stream ciphers can definitely compete in performance with things like Xorshift.
- deleted 11y ago
  [deleted]
mistercow 11y ago
I would definitely argue against that given the perf that you can get out of CSPRNGs. AES/CTR could give you over 100 million random bytes per second back in 2009 (source: https://www.cryptopp.com/benchmarks.html https://www.cryptopp.com/benchmarks.html). How much faster do you need your RNG to be in any non-niche situation?
- Jach 11y ago
  The niche situations aren't going to use the built-in rand() anyway because they can write their own or use someone else's that's faster. Even if they end up using the same algorithm (e.g. a Mersenne Twister) they can still often go faster. Interestingly according to https://bocoup.com/weblog/random-numbers https://bocoup.com/weblog/random-numbers Firefox is just going to use its CSPRNG once the crypto api is ready. (Bug 322529 is still in NEW state, though.)
- iopq 11y ago
  I need it faster because I need to generate random values for montecarlo trials. So I am using xorshift now instead of the default.

I'd definitely argue that needing a CSRNG is more niche than needing a fast RNG.

by yoklov 11y ago

I'd definitely argue that needing a CSRNG is more niche than needing a fast RNG.

tedunangst 11y ago

Perpetuates fallacy that CSRNG is not fast.

johncolanduoni 11y ago
On many platforms it's several orders of magnitude slower than a fast, dead simple PRNG with very good distributional properties, like xorshift1024* [1]. [1]: http://xorshift.di.unimi.it http://xorshift.di.unimi.it
- tedunangst 11y ago
  Let's return to the top. How many random bytes do you need per second? Rounded to the nearest billion, of course.
  - pcwalton 11y ago
    If your product is in a competitive environment and is being compared against others in benchmarks of random number generation, the answer is "as many as you can possibly generate". This scenario corresponds to JavaScript engines of major Web browsers.
    - tedunangst 11y ago
      In other words, bullshit breeds bullshit.
      - pcwalton 11y ago
        I can't blame V8 engineers for not wanting to regress SunSpider. Sad or not—and, let me tell you, nobody who works on browsers likes this state of affairs when it comes to that benchmark—doing well on the popular benchmarks has to be an engineering goal in the environment browsers find themselves in.
        mmalone 11y ago
        FWIW xorshift1024* would almost certainly be faster than MWC1616 and it has no systematic failures on BigCrush. The only downside is that it uses more memory, but I think we can afford it. If not xorshift64* is also faster than MWC1616 and miles ahead of it in quality.
  - johncolanduoni 11y ago
    For large simulations, this can easily become a bottleneck, which is why those generally use a good non-CS PRNG. In addition, CSPRNGs actually have slightly worse distributional properties than some much faster PRNGs, because the CSPRNG is more focused on being unpredictable. CSPRNGs aren't the end-all be-all of PRNGs, they have their appropriate and inappropriate applications even if we ignore speed.
    - tedunangst 11y ago
      That's not a number. > CSPRNGs actually have slightly worse distributional properties than some much faster PRNGs, because the CSPRNG is more focused on being unpredictable. What does this even mean? Non-uniform distribution for CSRNG is fatal. What is an RNG that has "better" distribution than CSRNG?
      - johncolanduoni 11y ago
        > That's not a number. The actually relevant aspect is what percentage of a simulation's time is spent generating random numbers if it's using a CSPRNG. I have had this become a bottleneck in my work, and it's very rare to use CSPRNGs in scientific simulations for this reason. > What does this even mean? Non-uniform distribution for CSRNG is fatal. What is an RNG that has "better" distribution than CSRNG? There are distributional properties other than uniformity, and depending on how you use these numbers (e.g. Monte Carlo kernel form) these can be far more important than linear uniformity. The author briefly mentioned this in the article ("CSPRNGs emphasize unpredictability over all other measures of quality, some of which might be more important for your use case"). Look into the work of George Marsaglia, he wrote the test suites that generate the quality numbers most engineers use to evaluate both CSPRNG and normal PRNGs.
        pbsd 11y ago
        I find it disingenuous to see properties such as equidistribution or low discrepancy being described as 'quality' of a generator. Yes, they make certain Monte Carlo algorithms converge quicker. No, they are not closer to a truly random sequence than a CSPRNG is. The goal of a CSPRNG is to be indistinguishable from true randomness, and a predictor is quite obviously a distinguisher. But so is a statistical test, or any 'nice' property that makes some algorithm behave better. By the way, I think I've said this before, but I'll say it again. I really dislike the usage of the term 'CSPRNG' in these discussions. A CSPRNG is typically understood to be /dev/urandom---an algorithm that not only generates a long sequence of numbers, but also harvests entropy and tries to achieve forward and backward security. But it is also sometimes overloaded to mean a stream cipher, which is a conceptually simpler construct, and also able to be much faster. Stream ciphers can definitely compete in performance with things like Xorshift.
deleted 11y ago
[deleted]

mistercow 11y ago

I would definitely argue against that given the perf that you can get out of CSPRNGs. AES/CTR could give you over 100 million random bytes per second back in 2009 (source: https://www.cryptopp.com/benchmarks.html https://www.cryptopp.com/benchmarks.html). How much faster do you need your RNG to be in any non-niche situation?

Jach 11y ago
The niche situations aren't going to use the built-in rand() anyway because they can write their own or use someone else's that's faster. Even if they end up using the same algorithm (e.g. a Mersenne Twister) they can still often go faster. Interestingly according to https://bocoup.com/weblog/random-numbers https://bocoup.com/weblog/random-numbers Firefox is just going to use its CSPRNG once the crypto api is ready. (Bug 322529 is still in NEW state, though.)
iopq 11y ago
I need it faster because I need to generate random values for montecarlo trials. So I am using xorshift now instead of the default.