Re: FreeBSD rnd bug

[Alexander Nasonov <alnsn%yandex.ru@localhost>]

J. Lewis Muir wrote:
> On 2/20/15 7:55 AM, Taylor R Campbell wrote:
> > Yes, for cprng_strong.  However, statistical tests on the output of
> > a cryptographic PRNG will not detect failure to seed it.  They will
> > detect only catastrophic bugs in the PRNG itself.  (They will also
> > sometimes spuriously fire, as is the nature of statistical tests on
> > uniform random data.)
> 
> See Dilbert's tour of accounting:
> 
>   http://dilbert.com/strip/2001-10-25

I talked about long runs with Taylor at EuroBSDCon in Sofia but
I'd like to share it with more people, especially in a context
of testing. The below is a (rather long) quote from Analytic
Combinatorics book by Flajolet and Sedgewick:

http://algo.inria.fr/flajolet/Publications/AnaCombi/book.pdf, page 52-53:

Revesz in [508] tells the following amusing story attributed to T. Varga:
"A class of high school children is divided into two sections. In
one of the sections, each child is given a coin which he throws
two hundred times, recording the resulting head and tail sequence
on a piece of paper. In the other section, the children do not
receive coins, but are told instead that they should try to write
down a random head and tail sequence of length two hundred.
Collecting these slips of paper, [a statistician] then tries to
subdivide them into their original groups. Most of the time, he
succeeds quite well."

The statistician's secret is to determine the probability distribution
of the maximum length of runs of consecutive letters in a random
binary word of length n (here n = 200). The probability that this
parameter equals k is

(big scary formula here)

and is fully determined by (54). The probabilities are then easily
computed using any symbolic package: for n = 200, the values found are

(sorry, can't copy/paste a table from pdf to txt)

Thus, in a randomly produced sequence of length 200, there are
usually runs of length 6 or more: the probability of the event
turns out to be close to 97% (and there is s till a probability of
about 8% to have a run of length 11 or more). On the other hand
most children (and adults) are usually afraid of writing down runs
longer than 4 or 5 as this is felt as strongly non-random.  The
statistician simply selects the slips that contain runs of length
6 or more as the true random ones. Voila.

Alex