testing quality of a /dev/random

[Enzo Michelangeli]

Sam,

My personal opinion about random number generators can be summarized as
follows:

1. A good "random" sequence is one that is unguessable by an adversary. Good
statistical properties are a necessary, but not sufficient, condition for
that.

2. A cryptographically sound pseudo-random number generator (PRNG) is good
enough, as long as its internal state is also unguessable. This requires
one-way algorithms preventing the attacker from back-stepping it, and a
large (say, > 128-bit) amount of internal state to prevent brute-force
attacks.

3. As PRNG's are deterministic machines, they must be initialized by
"seeding" them with true random data (entropy) collected from the physical
world. Once this is done, say with N bits of entropy, the PRNG may be safely
assumed to churn out sequences whose brute-force guessing requires a number
of attempt in the region of 2**N. A few years ago Netscape, in the SSL
implementation for Navigator 2, used a value too small for N, and they got
busted by Ian Goldberg and David Wagner. The most difficult part here is
determining how large N is for some typical entropy sources (mouse
movements, disk jitter, UNIX process
table content etc.).

If you are interested in these matters, you may want to have a look at the
documentation of Yarrow ( http://www.counterpane.com/yarrow.html )
containing in-depth analysis of design guidelines for good (P)RNG's and a
description of the most common attacks against them.

Cheers --

Enzo


----- Original Message -----
From: "Sam Roberts" <sam at cogent.ca>
To: <gnupg-devel at gnupg.org>
Sent: Friday, March 10, 2000 0:52
Subject: Re: testing quality of a /dev/random


>
> Ok, so this test doesn't work, and I'm back with the questions
> I started with.
>
> The gnupg web site claims that Linux's /dev/random is suitable
> for a high quality source of entropy. My driver uses the same
> code, just using QNX-specific ways of detecting an irq
> event and calling the function to mix in some irq entropy. Linux
> calls this function when it detects (in linux-specific ways) that
> the irq has occurred.
>
> My questions, then and again, are:
>
> - why do people think that Linux's dev/random is of high quality?
> - how was it tested?
> - how, if it is possible at all, do I demonstrate that my port generates
>   random data of the same quality?
>
> It appears to me that only consideration of the source code and
> the means of detecting random events can be used to convince
> yourself the output is random.
>
> I also don't see why the linux driver is as complex as it is.
>
> I think I could just grap the TSC on
> every irq, take the lowest order bit, and add to the entropy pool
> bit by bit. I'd then link urandom to random. This might be slower
> in gathering entropy, but every bit in the entropy pool would
> correspond to whether the irq handler sample the TSC on an odd
> or even instruction cycle, which has got to be random. The Linux
> code does the same, but it adds all bits of the time difference to
> the entropy pool, even though many of those bits will not be random,
> and then attempts to compensate for this using an algorithm that
> is undocumented (every other alogorithm in the driver
> comes with a reference to it's source, and some discussion,
> the estimate of randomness function is just there, with a comment
> saying that it's estimating the amount of randomness added to
> the pool).
>
> And from a less technical point-of-view:
>
> - is it possible to have this included in a contrib directory?
> - is there some other distribution technique you'd like (I could
>   stick it on QNXs site, but unless you add a note to the web
>   page or the INSTALL note, users of gpg won't know it exists).
>
> Thanks,
> Sam
>
> --
> Sam Roberts, sam at cogent dot ca, www.cogent.ca
>
> ----- Original Message -----
> From: Werner Koch <wk at gnupg.org>
> To: <gnupg-devel at gnupg.org>
> Sent: Thursday, March 09, 2000 5:36 AM
> Subject: Re: testing quality of a /dev/random
>
>
> > On Thu, 9 Mar 2000, Enzo Michelangeli wrote:
> >
> > > Such kind of tests, at best, prove how bad a (P)RNG is, not how good:
the
> > > (very deterministic) digits of PI would pass your tests with flying
colours.
> > > Determining an lower bound for the entropy of a data source based only
on
> > > the data stream is a non-computable problem.
> >
> > And remember that the output from /dev/random transfers the SHA-1
> > mixinf function.  There is no way to measure the entropy outside the
> > kernel.
> >
> >    Werner
> >
> >
>