4 ms·

1. Agreed that CSPRNG are fast enough for most purposes, and should be the default PRNG basically everywhere. 2. The magic ingredients of a CSPRNG are not only

by FabHK 7y ago

1. Agreed that CSPRNG are fast enough for most purposes, and should be the default PRNG basically everywhere. 2. The magic ingredients of a CSPRNG are not only the "secret entropy" for seeding, but also the property that given a sequence of its outputs, it's sufficiently hard to predict the next output (this implies that it won't fail the usual statistical tests - every CSPRNG is a PRNG, but not vice versa: for example, with 624 outputs of the Mersenne Twister, you can predict all subsequent ones.) This next-bit test property was sort of implied (by saying "stream cipher"), but I wanted to spell it out, as it's good to have in one's mental model. 3. For some purposes (such as Monte Carlo simulations), a non-CSPRNG makes sense, as they're still faster. (But given the asymmetric payoffs of a mistake, default should be CSPRNG.)

tptacek 7y ago
What you're saying in (2) is essentially the same thing as saying "a typical CSPRNG is a stream cipher keyed by entropy", except that people seem to have a really hard time reasoning about what "predictability of the next bit" means, and not so hard of a time reasoning about what the keystream of a stream cipher does.
- FabHK 7y ago
  Might depend on your background. For a cryptographer, that property is an obvious consequence of being a stream cipher's keystream. For a Monte Carlo guy, it's not obvious, but close to miraculous. And what everyone needs to know is that it doesn't hold for many (non-CS) PRNG, as apparently poker site operators have found out to their chagrin.
petschge 7y ago
Actually you can make use of non-randomness in Monte Carlo simulations to get better results. There is various names for this, but the one I like best is "low discrepancy series". Have a look at [1] or [2] for a quick intro. These are sometimes also called quasi-random (or sub-random), but I find that a bit too close to pseudo-random. [1] https://en.wikipedia.org/wiki/Low-discrepancy_sequence https://en.wikipedia.org/wiki/Low-discrepancy_sequence [2] https://blog.demofox.org/2017/05/29/when-random-numbers-are-too-random-low-discrepancy-sequences/ https://blog.demofox.org/2017/05/29/when-random-numbers-are-...
tgsovlerkhgsel 7y ago
> a non-CSPRNG makes sense, as they're still faster Nowadays with highly optimized and often hardware-accelerated crypto, I honestly doubt it matters. Using "openssl rand", I can generate randomness 2x as fast as with a naive while (1) { r = rand(); fwrite(&r, 4, 1, stdout); } compiled with -O2. If I replace "openssl rand" with "openssl enc -aes-128-ctr < /dev/zero", I get randomness 4 times faster again, i.e. 8 times as fast as with the naive approach using rand(), hundreds of megabytes on a single core. And I don't have to worry about the properties of the PRNG.
- FabHK 7y ago
  Yes, good point. As O'Neill pointed out in a blog post last year on "Efficiently Generating a Number in a Range" [1], the impact of choosing a faster PRNG is smaller than the impact of choosing a good algorithm to generate an integer in a range. There'll be very few applications where choosing a faster PRNG has any significant impact. [1] http://www.pcg-random.org/posts/bounded-rands.html http://www.pcg-random.org/posts/bounded-rands.html
- wolf550e 7y ago
  Not "hundreds of megabytes on a single core", 5 GB per second on a single core on a i7-6700HQ. Use `openssl speed -evp aes-128-ctr`, look at right-most column of 16kb blocks (like TLS record layer).
- ahh 7y ago
  Fair, but rand() is kinda trashy, and the overwhelming part of that cost is fwrite anyway.
  - tgsovlerkhgsel 7y ago
    A large part of the cost being "not random number generation" is part of the point - speed of random number generation generally doesn't matter compared to the speed of what you do with the numbers, and optimizing other things, e.g. how to get the bits converted to random numbers usable by an application, are much more important than quickly generating the random bits.

by FabHK 7y ago

tptacek 7y ago

What you're saying in (2) is essentially the same thing as saying "a typical CSPRNG is a stream cipher keyed by entropy", except that people seem to have a really hard time reasoning about what "predictability of the next bit" means, and not so hard of a time reasoning about what the keystream of a stream cipher does.

FabHK 7y ago
Might depend on your background. For a cryptographer, that property is an obvious consequence of being a stream cipher's keystream. For a Monte Carlo guy, it's not obvious, but close to miraculous. And what everyone needs to know is that it doesn't hold for many (non-CS) PRNG, as apparently poker site operators have found out to their chagrin.

petschge 7y ago

Actually you can make use of non-randomness in Monte Carlo simulations to get better results. There is various names for this, but the one I like best is "low discrepancy series". Have a look at [1] or [2] for a quick intro. These are sometimes also called quasi-random (or sub-random), but I find that a bit too close to pseudo-random. [1] https://en.wikipedia.org/wiki/Low-discrepancy_sequence https://en.wikipedia.org/wiki/Low-discrepancy_sequence [2] https://blog.demofox.org/2017/05/29/when-random-numbers-are-too-random-low-discrepancy-sequences/ https://blog.demofox.org/2017/05/29/when-random-numbers-are-...

tgsovlerkhgsel 7y ago

> a non-CSPRNG makes sense, as they're still faster Nowadays with highly optimized and often hardware-accelerated crypto, I honestly doubt it matters. Using "openssl rand", I can generate randomness 2x as fast as with a naive while (1) { r = rand(); fwrite(&r, 4, 1, stdout); } compiled with -O2. If I replace "openssl rand" with "openssl enc -aes-128-ctr < /dev/zero", I get randomness 4 times faster again, i.e. 8 times as fast as with the naive approach using rand(), hundreds of megabytes on a single core. And I don't have to worry about the properties of the PRNG.

FabHK 7y ago
Yes, good point. As O'Neill pointed out in a blog post last year on "Efficiently Generating a Number in a Range" [1], the impact of choosing a faster PRNG is smaller than the impact of choosing a good algorithm to generate an integer in a range. There'll be very few applications where choosing a faster PRNG has any significant impact. [1] http://www.pcg-random.org/posts/bounded-rands.html http://www.pcg-random.org/posts/bounded-rands.html
wolf550e 7y ago
Not "hundreds of megabytes on a single core", 5 GB per second on a single core on a i7-6700HQ. Use `openssl speed -evp aes-128-ctr`, look at right-most column of 16kb blocks (like TLS record layer).
ahh 7y ago
Fair, but rand() is kinda trashy, and the overwhelming part of that cost is fwrite anyway.
- tgsovlerkhgsel 7y ago
  A large part of the cost being "not random number generation" is part of the point - speed of random number generation generally doesn't matter compared to the speed of what you do with the numbers, and optimizing other things, e.g. how to get the bits converted to random numbers usable by an application, are much more important than quickly generating the random bits.