[Python-ideas] Should our default random number generator be secure?

[Nathaniel Smith]

On Mon, Sep 14, 2015 at 8:53 PM, Steven D'Aprano <steve at pearwood.info> wrote:
> On Mon, Sep 14, 2015 at 10:19:09PM +0100, Robert Kern wrote:
>
>> The requirement for a good PRNG for simulation work is that it be *well*
>> distributed in reasonable dimensions, not that it be *exactly*
>> equidistributed for some k. And well-distributedness is exactly what is
>> tested in TestU01. It is essentially a collection of simulations designed
>> to expose known statistical flaws in PRNGs. So to your earlier question as
>> to which is more damning, failing TestU01 or not being perfectly 623-dim
>> equidistributed, failing TestU01 is.
>
> I'm confused here. Isn't "well-distributed" a less-strict test than
> "exactly equidistributed"? MT is (almost) exactly k-equidistributed up
> to k = 623, correct? So how does it fail the "well-distributed" test?

No, "well-distributed" means "distributed like true random stream",
which is a strong and somewhat fuzzy requirement. "k-equidistributed"
is one particular way of operationalizing this requirement, but it's
not a very good one. The idea of k-equidistribution is historically
important because it spurred the development of generators that
avoided the really terrible flaws of early designs like Unix rand, but
it's not terribly relevant to modern RNG design.

Here's how it works.

Formally speaking, a randomized algorithm or Monte Carlo simulation or
similar can be understood as a function mapping an infinite bitstring
to some output value, F : R -> O.

If we sample infinite bitstrings R uniformly at random (using a
theoretical "true" random number generator), and then apply F to each
bitstring, then this produces some probability distribution over
output values O.

Now given some *pseudo* random number generator, we consider our
generator to be successful if that repeatedly running F(sample from
this RNG) gives us the same distribution over output values as if we
had repeatedly run F(true random sample).

So for example, you could have a function F that counts up how many
times it sees a zero or a one in the first 20,000 entries in the
bitstring, and you expect those numbers to come up at ~10,000 each
with some distribution around that. If your RNG is such that you
reproduce that distribution, then you pass this function. Note that
this is a little counterintuitive: if your RNG is such that over the
first 20,000 entries it always produces *exactly* 10,000 zeros and
10,000 ones, then it fails this test. The Mersenne Twister will pass
this test.

Or you could have a function F that takes the first 19937 bits from
the random stream, uses it to construct a model of the internal state
of a Mersenne Twister, predicts the next 1000 bits, and returns True
if they match and False if they don't match. On a real random stream
this function returns True with probability 2^-1000; on a MT random
stream it returns True with probability 1. So the MT fails this test.
OTOH this is obviously a pretty artificial example.

The only case the scientists actually care about is the one where F is
"this simulation right here that I'm trying to run before the
conference deadline". But since scientists don't really want to design
a new RNG for every simulation, we instead try to design our RNGs such
that for all "likely" or "reasonable" functions F, they'll probably
work ok. In practice this means that we write down a bunch of explicit
test functions F inside a test battery like TestU01, run the functions
on the RNG stream, and if their output is indistinguishable in
distribution from what it would be for a true random stream then we
say they pass. And we hope that this will probably generalize to the
simulation we actually care about.

Cryptographers are worried about the exact same issue -- they want
RNGs that have the property that for all functions F, the behavior is
indistinguishable from true randomness. But unlike the scientists,
they're not content to say "eh, I checked a few functions and it
seemed to work on those, probably the ones I actually care about are
okay too". The cryptographers consider it a failure if an adversary
with arbitrary computing power, full knowledge of the RNG algorithm,
plus other magic powers like the ability to influence the RNG seeding,
can invent *any* function F that acts differently (produces a
different distribution over outputs) when fed the input from the RNG
as compared to a true random stream. The only rule for them is that
the function has to be one that you can actually implement on a
computer that masses, like, less than Jupiter, and only has 1000 years
to run. And as far as we can tell, modern crypto RNGs succeed at this
very well.

Obviously the thing the scientists worry about is a *strict* subset of
what the cryptographers are worried about. This is why it is silly to
worry that a crypto RNG will cause problems for a scientific
simulation. The cryptographers take the scientists' real goal -- the
correctness of arbitrary programs like e.g. a monte carlo simulation
-- *much* more seriously than the scientists themselves do. (This is
because scientists need RNGs to do their real work, whereas for
cryptographers RNGs are their real work.)

Compared to this, k-dimensional equidistribution is a red herring: it
requires that you have a RNG that repeats itself after a while, and
within each repeat it produces a uniform distribution over bitstrings
of some particular length. By contrast, a true random bitstring does
not repeat itself, and it gives a uniform distribution over bitstrings
of *arbitrary* length. In this regard, crypto RNGs are like true
random bitstrings, not like k-equidistributed RNGs. This is a good
thing. k-equidistribution doesn't really hurt (theoretically it
introduces flaws, but for realistic designs they don't really matter),
but if randomness is what you want then crypto RNGs are better.

I-should-really-get-a-blog-shouldn't-I'ly-yrs,
-n

-- 
Nathaniel J. Smith -- http://vorpus.org