[OT] Combinatronics WAS Re: /dev/random and linux security issues (kinda long)

[David Ecklein]

My 2 cents worth...

In my wasted youth I experimented with random number generator algorithms of
various kinds.  One amusing but useful tool that can act as a fairly good
eliminator of many such schemes is to convert the output into a graphical
plot.  It often doesn't matter too much how this is done, just that the x/y
position of a pixel is related somehow to the digital output of the scheme.
You will be surprised to see that many purportedly random series of
characters or numbers that look good will show regular and obvious patterns
when so displayed.  Sometimes these patterns take some scaling in time and
space to become obvious.

Any scheme wholly algorithmic by definition will not be truly "random", only
"pseudorandom", and all of them, I believe, will eventually repeat or enter
a repeating cycle.  This is not undesirable in most cases, since if the
algorithm is started under the same conditions, it will then produce the
same sequence.  An invaluable property when the output is used for testing
other algorithms, or used for cryptographic purposes, for instance.  One
generally seeks a sufficiently long cycle without terminating in a
relatively tight epicycle and enough local statistical independence along
the way to do whatever job is intended.

For a "truly random" source, it might be best to use a good white noise
source, such as a properly chosen and biased point contact silicon diode or
the like.  For something in between and completely accessible to a software
approach, the computer clock could be factored into a prospective algorithm.

But I don't think a "truly random" (in principle unrepeatable) approach
solves as many useful problems as the "pseudorandom" approaches overall.

Somewhere in one of Donald Knuth's classic books on algorithms was an
excellent and extended discussion of random number generation programming
and the associated pitfalls.  I remember him illustrating that sometimes
simplest is best!

Dave E.


----- Original Message ----- 
From: "Benjamin Scott" <dragonhawk at iname.com>
To: "Greater NH Linux User Group" <gnhlug-discuss at mail.gnhlug.org>
Sent: Sunday, May 15, 2005 8:42 PM
Subject: Re: /dev/random and linux security issues (kinda long)


> On May 15 at 6:45pm, aluminumsulfate at earthlink.net wrote:
> >>   It may seem that way at first thought, but it is not the case.  It
> >>   is entirely possible to randomly generate the same value repeatedly
> >>   in sequence.  Statistically, it is, in fact, equally likely that you
> >>   will generate 79 '6's as 79 characters with no repeats.
> >
> > I don't believe so. The probability of getting 79 '6's is 1/95^79. The
> > probability of getting ANY string of 79 of the same digit would be
1/95^78.
>
>    Hmmmm... from what I remember of my college combinatorics course (which
I
> flunked), you're both right.
>
>    If the series is statistically random, then the probability of getting
*any*
> set of N characters it the same.  If you have a statistically random
penny,
> for example, and you flip it 20 times, you have just as much a chance of
> getting 20 heads as you do 10 heads, because each individual flip is
strictly
> 50/50, and each flip has no bearing on any other flip.  The fact that you
get
> 10 heads in a row does not mean the next one should be tails to "start
making
> up for the previous 10 heads".
>
>    There's a great Dilbert comic on this... here's a copy:
>
>
http://www.pen.k12.va.us/Div/Winchester/jhhs/math/humor/comics/computer/random.html
>
>    So, from that point of view, Mike's right.
>
>    Now, in the real world, I understand that there is some argument about
> whether a truly statistically random series can exist.  Certainly, from a
> practical standpoint, if one flips a penny 100 times and gets heads each
time,
> it's more likely that the penny (or the flip) is somehow biased in favor
of
> heads.  I'd certainly put my money (hah) on heads rather then tails.  The
same
> applies to the kernel's RNG.  If you see patterns, it could just be a
random
> coincidence, but one should look for flaws in the RNG.
>
>    So, from that point of view, aluminumsulfate at ... (Dave?) is right.
>
>    Of course, as aluminumsulfate at ... discovered, when it comes to matters
of
> crypto, one's own tools tend to be the first source of trouble.  This is
why
> peer review of crypto software is absolutely critical.
>
> -- 
> Ben <dragonhawk at iname.com>