Hacker News Reader

Comment by FabHK | Hacker News Reader

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.)

View on HN

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-...

> 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.

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

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).

Fair, but rand() is kinda trashy, and the overwhelming part of that cost is fwrite anyway.

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.

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.

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.

Reply on news.ycombinator.com