News for hackers. Stuff that matters.
Re:Billions of Random Numbers in a Blink of an Eye by tptacek on Tuesday July 02, 2019 @05:27PM (#20339562)
Just for what it's worth: it's not that cryptography needs difficult-to-generate "true" random numbers, but rather that it needs a particular kind of pseudorandomness. The best mental model to have of crypto-randomness is that it's seeded from events unpredictable enough to be effectively secret; a typical CSPRNG is, in fact, essentially a stream cipher that uses "entropy" (again, those unpredictable events) as its key.

Once you've got it seeded, you can get random numbers from your system's platform CSPRNG plenty fast, and CSPRNGs make, for most applications, a reasonable default RNG.

Re:Billions of Random Numbers in a Blink of an Eye by FabHK on Tuesday July 02, 2019 @05:57PM (#20339740)
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.)

Re:Billions of Random Numbers in a Blink of an Eye by petschge on Tuesday July 02, 2019 @07:55PM (#20340445)
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 [2] https://blog.demofox.org/2017/05/29/when-random-numbers-are-...

Re:Billions of Random Numbers in a Blink of an Eye by tgsovlerkhgsel on Wednesday July 03, 2019 @03:10AM (#20342258)
> 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.

Re:Billions of Random Numbers in a Blink of an Eye by wolf550e on Wednesday July 03, 2019 @01:42PM (#20346614)
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).
Re:Billions of Random Numbers in a Blink of an Eye by FabHK on Wednesday July 03, 2019 @10:04AM (#20344343)
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

Re:Billions of Random Numbers in a Blink of an Eye by ahh on Wednesday July 03, 2019 @09:19PM (#20350687)
Fair, but rand() is kinda trashy, and the overwhelming part of that cost is fwrite anyway.
Re:Billions of Random Numbers in a Blink of an Eye by tgsovlerkhgsel on Sunday July 07, 2019 @03:58PM (#20377416)
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.
Re:Billions of Random Numbers in a Blink of an Eye by tptacek on Tuesday July 02, 2019 @06:05PM (#20339809)
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.
Re:Billions of Random Numbers in a Blink of an Eye by FabHK on Tuesday July 02, 2019 @06:30PM (#20339979)
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.