7 ms·

What applications require unpredictability where you wouldn't go full csprng?

uluyol 6y ago
Request back off / retries, any sort of simulation, various load balancing algorithms, randomized algorithms, fuzzing/testing, ...
- Thorrez 6y ago
  Why does back off / retry require unpredictability?
  - thiagocsf 6y ago
    To avoid a stampede of requests by synchronised clients.
    - Thorrez 6y ago
      That 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 ago
    It 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 ago
      I think you're agreeing with me that unpredictability isn't necessary (e.g. Mersenne Twister would work fine).
      - DougBTX 6y ago
        I see you’ve replied to quite a few of the comments in this thread, but I think the basis of the disagreement isn’t in the specifics, but because you’re using a stronger definition of “unpredictability” than they are.
        Thorrez 6y ago
        I believe I'm using the same definition of unpredictability as the website. If other people are using other definitions that is indeed going to cause a lot of confusion.
        Karliss 6y ago
        Today I learned that there are other aspects for CSPRNG beside the stronger definition of unpredictability. Wikipedia mentions inability to calculate previous values in case the hidden internal state gets revealed. So I assumed that top question was intentionally asking about weaker definition of predicatability not PRNG that have good enough unpredictability for CSPRNG but doesn't match other requirements.
nightcracker 6y ago
Some would say Monte Carlo methods, but I'd disagree. If the results are reliant on your RNG method I would not settle for less than crypto strength (and methods like ChaCha20 can generate random data at 4GB+ per core per second on a modern CPU). There is a time and place for non-CS rngs, and it is in randomized methods whos correctness/results does not rely on the RNG.
- BlackFly 6y ago
  You're going to validate your results anyways, aren't you? Non-cryptographic random number generators are not guaranteed to introduce bias, a given implementation of a monte carlo simulation might introduce bias via a bug or a poorly chosen modeling. If you need to validate for bias anyways, so you might as well verify by checking against a cryptographic random number generator as well as whatever bias tests you may have at your disposal and then switch over for the speed. A good non-cryptographic random number generator like xoshiro256 can generate at 4 times the speed of a chacha20 random number generator. Depending on how many models you need to compute and the desired precision of those models and how many random samples you need per model, this can easily be the difference between hours and days, or days and weeks.
- Athas 6y ago
  This surprises me. With Monte Carlo methods, wouldn't you rather want quasi-random numbers[0], because they allow the simulation to converge asymptotically faster? Those are certainly not anything like crypto-strength. [0]: https://en.wikipedia.org/wiki/Low-discrepancy_sequence https://en.wikipedia.org/wiki/Low-discrepancy_sequence
  - 0-_-0 6y ago
    This is my understanding as well. In a classic MC problem, global illumination with path tracing, low discrepancy-based sampling converges about twice as fast as random numbers. The Cycles renderer in Blender doesn't even give you the option to use random numbers, just a choice of low discrepancy sequnces [1]. [1] "Pattern" section here: http://builder.openhmd.net/blender-hmd-viewport-temp/render/cycles/settings/integrator.html#sampling http://builder.openhmd.net/blender-hmd-viewport-temp/render/...
vanderZwan 6y ago
Situations where there is no cryptographic issue in sight and random number generation is a bottleneck. Graphics and simulations in games, for example
- Thorrez 6y ago
  Does that actually require unpredictability? Or is it just a defense in depth type thing where we believe we don't need it, but some unknown vulnerability/attack might make unpredictability beneficial?
  - sgillen 6y ago
    The numbers used here are not for security they are just to make the scene look nice or to make the simulation more robust.
    - Thorrez 6y ago
      So I think we agree that unpredictability isn't necessary. The definition of unpredictability I'm using is the one on the website: where Mersenne Twister is easily predictable.
  - Karliss 6y ago
    Looking at your and other comments there might be confusion about definition of unpredictability. Unpredictable for user which is pretty low bar or unpredictable using best known mathematical techniques and available hardware. Wouldn't the second category be more less CSPRNG? As for first category and examples given. Requires is a weird question. Strongly requires as in it's impossible to make any game or visual effect without it - no. But in case of some design choices you might want some amount of unpredictability. You might want player not to fully predict enemies next move, or you might want a certain graphical effect which varies some parameter randomly within some distribution. Using a very poor pseudorandom generator there might became visible once it gets used in large amounts for placing objects spatially in the form of streaks, shapes or other patterns that wouldn't appear if true random or better quality psrng was used.
exmadscientist 6y ago
These algorithms are fantastic for microcontroller applications. You can even choose the multiplicative constant so that it fits in a Thumb-2 immediate and save yourself a constant pool reference, with no degradation in quality for the output (as measured by spectral tests).
- Thorrez 6y ago
  Why is unpredictability useful there?
  - exmadscientist 6y ago
    It's true that needing strict unpredictability, but not true cryptographic security, is rare in a microcontroller application. Though it can be nice to have. What makes PCG attractive for microcontrollers is really that it's of known good quality, its implementation is very small and very simple, and it ends up generating efficient code for 32-bit processors (i.e., ARM Cortex-Ms). That is not, and can not ever be, true for something like a 128-bit shift register. PCG is great for just tossing in when I'm working on a platform that has no built-in library rand() function, or where it's busted, or whether I don't want to bother figure out if/how badly it's busted. (With how easy PCG is to use, that last one covers every embedded platform ever....) PCG is not the best RNG out there: it's not the highest quality, it's not the fastest, it's not the least predictable, it's not the strongest theoretically. (It isn't the smallest, either, but it's quite small and the smaller RNGs I know of are either code-golfed, which doesn't count, or truly garbage.) But it is a nice equilibrium between all of those things. And did I mention it's simple? Simple is really, really nice to have :)
mratsim 6y ago
Anywhere you want reproducibility - Statistics, - Deep Learning, - Monte-Carlo simulation (finance, reinforcement learning, game AI, raytracing). - Fuzzing - Load balancing - Peer selection (if non adversarial, otherwise use a CSPRNG) Also non-determinism of CSPRNG (and floating points) would a huge issue for debugging machine learning models: - https://www.twosigma.com/insights/a-workaround-for-non-determinism-in-tensorflow https://www.twosigma.com/insights/a-workaround-for-non-deter... - https://github.com/tensorflow/tensorflow/issues/3103 https://github.com/tensorflow/tensorflow/issues/3103 - https://discuss.pytorch.org/t/deterministic-non-deterministic-results-with-pytorch/9087 https://discuss.pytorch.org/t/deterministic-non-deterministi... - https://github.com/tensorflow/tensorflow/issues/2732 https://github.com/tensorflow/tensorflow/issues/2732 - https://github.com/soumith/cudnn.torch/issues/270 https://github.com/soumith/cudnn.torch/issues/270 - https://github.com/pytorch/pytorch/issues/2831 https://github.com/pytorch/pytorch/issues/2831
- rainworld 6y ago
  The output of a CS_P_RNG is by definition reproducible. And there’s really only a small number of applications where, say, ChaCha8 would be too slow.
  - mratsim 6y ago
    According to https://rust-random.github.io/book/guide-rngs.html https://rust-random.github.io/book/guide-rngs.html Chacha8 has a throughput of 2GB/s and xoshiro256++ has a throughput of 8GB/s For Monte-Carlo, the RNG is definitely the bottleneck. For load balancing of short tasks the RNG is the bottleneck.
    - brandmeyer 6y ago
      On my thermally-limited laptop, aes-128-ctr runs at over 9 GB/s. If pure speed is the goal, then AES-NI is faster than the fastest PRNG. Seek to a deterministic point by advancing the counter. Choose random seed with a fresh key. What more could you want? ("portable speed!") You can eek out another 10% or so if you dial it back to the recommendations of the "too much crypto" paper: 9x AES rounds (versus 10). https://eprint.iacr.org/2019/1492 https://eprint.iacr.org/2019/1492
ChrisLomont 6y ago
Conversely, why pay the massive speed penalty for a csprng when you do not need to? I'd suspect the majority of random numbers generated in the world don't need crypto, they need speed. The world's supercomputers are not doing crpyto, they're doing simulations. Most people are not doing crypto most of the time - and when they're gaming in any manner, no need to pay csprng tax. The only place one should use a csprng is for adversarial situations. Use the right tool for the job, correct?
edflsafoiewq 6y ago
Being too easy to predict may break the blackbox nature of the PRNG (you might "predict" it by accident). For example you can increase the quality of a RNG sequence r(n) by adding a multiplicative hash, r'(n) = A r(n) for some good constant A. A consumer treating r' as a blackbox expects B r'(n) = AB r(n) to be a good random sequence, but if B is close to the inverse of A, the constant AB may no longer be "good".

Request back off / retries, any sort of simulation, various load balancing algorithms, randomized algorithms, fuzzing/testing, ...

Thorrez 6y ago
Why does back off / retry require unpredictability?
- thiagocsf 6y ago
  To avoid a stampede of requests by synchronised clients.
  - Thorrez 6y ago
    That 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 ago
  It 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 ago
    I think you're agreeing with me that unpredictability isn't necessary (e.g. Mersenne Twister would work fine).
    - DougBTX 6y ago
      I see you’ve replied to quite a few of the comments in this thread, but I think the basis of the disagreement isn’t in the specifics, but because you’re using a stronger definition of “unpredictability” than they are.
      - Thorrez 6y ago
        I believe I'm using the same definition of unpredictability as the website. If other people are using other definitions that is indeed going to cause a lot of confusion.
      - Karliss 6y ago
        Today I learned that there are other aspects for CSPRNG beside the stronger definition of unpredictability. Wikipedia mentions inability to calculate previous values in case the hidden internal state gets revealed. So I assumed that top question was intentionally asking about weaker definition of predicatability not PRNG that have good enough unpredictability for CSPRNG but doesn't match other requirements.

nightcracker 6y ago

Some would say Monte Carlo methods, but I'd disagree. If the results are reliant on your RNG method I would not settle for less than crypto strength (and methods like ChaCha20 can generate random data at 4GB+ per core per second on a modern CPU). There is a time and place for non-CS rngs, and it is in randomized methods whos correctness/results does not rely on the RNG.

BlackFly 6y ago
You're going to validate your results anyways, aren't you? Non-cryptographic random number generators are not guaranteed to introduce bias, a given implementation of a monte carlo simulation might introduce bias via a bug or a poorly chosen modeling. If you need to validate for bias anyways, so you might as well verify by checking against a cryptographic random number generator as well as whatever bias tests you may have at your disposal and then switch over for the speed. A good non-cryptographic random number generator like xoshiro256 can generate at 4 times the speed of a chacha20 random number generator. Depending on how many models you need to compute and the desired precision of those models and how many random samples you need per model, this can easily be the difference between hours and days, or days and weeks.
Athas 6y ago
This surprises me. With Monte Carlo methods, wouldn't you rather want quasi-random numbers[0], because they allow the simulation to converge asymptotically faster? Those are certainly not anything like crypto-strength. [0]: https://en.wikipedia.org/wiki/Low-discrepancy_sequence https://en.wikipedia.org/wiki/Low-discrepancy_sequence
- 0-_-0 6y ago
  This is my understanding as well. In a classic MC problem, global illumination with path tracing, low discrepancy-based sampling converges about twice as fast as random numbers. The Cycles renderer in Blender doesn't even give you the option to use random numbers, just a choice of low discrepancy sequnces [1]. [1] "Pattern" section here: http://builder.openhmd.net/blender-hmd-viewport-temp/render/cycles/settings/integrator.html#sampling http://builder.openhmd.net/blender-hmd-viewport-temp/render/...

vanderZwan 6y ago

Situations where there is no cryptographic issue in sight and random number generation is a bottleneck. Graphics and simulations in games, for example

Thorrez 6y ago
Does that actually require unpredictability? Or is it just a defense in depth type thing where we believe we don't need it, but some unknown vulnerability/attack might make unpredictability beneficial?
- sgillen 6y ago
  The numbers used here are not for security they are just to make the scene look nice or to make the simulation more robust.
  - Thorrez 6y ago
    So I think we agree that unpredictability isn't necessary. The definition of unpredictability I'm using is the one on the website: where Mersenne Twister is easily predictable.
- Karliss 6y ago
  Looking at your and other comments there might be confusion about definition of unpredictability. Unpredictable for user which is pretty low bar or unpredictable using best known mathematical techniques and available hardware. Wouldn't the second category be more less CSPRNG? As for first category and examples given. Requires is a weird question. Strongly requires as in it's impossible to make any game or visual effect without it - no. But in case of some design choices you might want some amount of unpredictability. You might want player not to fully predict enemies next move, or you might want a certain graphical effect which varies some parameter randomly within some distribution. Using a very poor pseudorandom generator there might became visible once it gets used in large amounts for placing objects spatially in the form of streaks, shapes or other patterns that wouldn't appear if true random or better quality psrng was used.

exmadscientist 6y ago

These algorithms are fantastic for microcontroller applications. You can even choose the multiplicative constant so that it fits in a Thumb-2 immediate and save yourself a constant pool reference, with no degradation in quality for the output (as measured by spectral tests).

Thorrez 6y ago
Why is unpredictability useful there?
- exmadscientist 6y ago
  It's true that needing strict unpredictability, but not true cryptographic security, is rare in a microcontroller application. Though it can be nice to have. What makes PCG attractive for microcontrollers is really that it's of known good quality, its implementation is very small and very simple, and it ends up generating efficient code for 32-bit processors (i.e., ARM Cortex-Ms). That is not, and can not ever be, true for something like a 128-bit shift register. PCG is great for just tossing in when I'm working on a platform that has no built-in library rand() function, or where it's busted, or whether I don't want to bother figure out if/how badly it's busted. (With how easy PCG is to use, that last one covers every embedded platform ever....) PCG is not the best RNG out there: it's not the highest quality, it's not the fastest, it's not the least predictable, it's not the strongest theoretically. (It isn't the smallest, either, but it's quite small and the smaller RNGs I know of are either code-golfed, which doesn't count, or truly garbage.) But it is a nice equilibrium between all of those things. And did I mention it's simple? Simple is really, really nice to have :)

mratsim 6y ago

Anywhere you want reproducibility - Statistics, - Deep Learning, - Monte-Carlo simulation (finance, reinforcement learning, game AI, raytracing). - Fuzzing - Load balancing - Peer selection (if non adversarial, otherwise use a CSPRNG) Also non-determinism of CSPRNG (and floating points) would a huge issue for debugging machine learning models: - https://www.twosigma.com/insights/a-workaround-for-non-determinism-in-tensorflow https://www.twosigma.com/insights/a-workaround-for-non-deter... - https://github.com/tensorflow/tensorflow/issues/3103 https://github.com/tensorflow/tensorflow/issues/3103 - https://discuss.pytorch.org/t/deterministic-non-deterministic-results-with-pytorch/9087 https://discuss.pytorch.org/t/deterministic-non-deterministi... - https://github.com/tensorflow/tensorflow/issues/2732 https://github.com/tensorflow/tensorflow/issues/2732 - https://github.com/soumith/cudnn.torch/issues/270 https://github.com/soumith/cudnn.torch/issues/270 - https://github.com/pytorch/pytorch/issues/2831 https://github.com/pytorch/pytorch/issues/2831

rainworld 6y ago
The output of a CS_P_RNG is by definition reproducible. And there’s really only a small number of applications where, say, ChaCha8 would be too slow.
- mratsim 6y ago
  According to https://rust-random.github.io/book/guide-rngs.html https://rust-random.github.io/book/guide-rngs.html Chacha8 has a throughput of 2GB/s and xoshiro256++ has a throughput of 8GB/s For Monte-Carlo, the RNG is definitely the bottleneck. For load balancing of short tasks the RNG is the bottleneck.
  - brandmeyer 6y ago
    On my thermally-limited laptop, aes-128-ctr runs at over 9 GB/s. If pure speed is the goal, then AES-NI is faster than the fastest PRNG. Seek to a deterministic point by advancing the counter. Choose random seed with a fresh key. What more could you want? ("portable speed!") You can eek out another 10% or so if you dial it back to the recommendations of the "too much crypto" paper: 9x AES rounds (versus 10). https://eprint.iacr.org/2019/1492 https://eprint.iacr.org/2019/1492

ChrisLomont 6y ago

Conversely, why pay the massive speed penalty for a csprng when you do not need to? I'd suspect the majority of random numbers generated in the world don't need crypto, they need speed. The world's supercomputers are not doing crpyto, they're doing simulations. Most people are not doing crypto most of the time - and when they're gaming in any manner, no need to pay csprng tax. The only place one should use a csprng is for adversarial situations. Use the right tool for the job, correct?

edflsafoiewq 6y ago

Being too easy to predict may break the blackbox nature of the PRNG (you might "predict" it by accident). For example you can increase the quality of a RNG sequence r(n) by adding a multiplicative hash, r'(n) = A r(n) for some good constant A. A consumer treating r' as a blackbox expects B r'(n) = AB r(n) to be a good random sequence, but if B is close to the inverse of A, the constant AB may no longer be "good".