testing quality of a /dev/random
em at who.net
Fri Mar 10 09:35:03 CET 2000
My personal opinion about random number generators can be summarized as
1. A good "random" sequence is one that is unguessable by an adversary. Good
statistical properties are a necessary, but not sufficient, condition for
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
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.
----- 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).
> 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:
> > > (very deterministic) digits of PI would pass your tests with flying
> > > Determining an lower bound for the entropy of a data source based only
> > > 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
More information about the Gnupg-devel