Re: [tlug] /dev/random is truly random?

["Stephen J. Turnbull" <stephen@??>]

Mauro D. Sauco writes:

 > On 2007/02/22@??:52, <Hung Vu Nguyen> wrote:

 >   > Linux's /dev/random is made from <kernel source>/drivers/char/random.c
 >   > The seed used there is system timer, and it adds more "noise" from
 >   > divice drives like keyboard "to have numbers which are not only
 >   > random, but hard to * predict by an attacker." ( quote from the
 >   > comment of the source code ) ( Yet, the seed is still timer! ).

I have now skimmed the full comment.  It's actually quite informative,
and tells exactly why the author believes that the random device is
hard to predict.  If it's not clear to you, then you probably simply
lack the specialized technical vocabulary to understand what is written.

 > It is interesting that random.c still generates a seed from predictable
 > sources only which make it fall in the category of "pseudo random". 

It's not "pseudo-random", because the seed changes continuously.

As for the initial seed, it's multisource, none of which are
predictable, although they are measureable, generally with fairly poor
accuracy.

Source 1: previous state -- the attacker must have access to your
          system at shutdown time, or it's not predictable.
Source 2: uname -- an attacker without access your system can guess
          this, but it changes with every kernel build.
Source 3: system timer -- changes every microsecond.

But this is still not the complete seed; we start adding more entropy
immediately, effectively changing the seed continuously.  Then we stir
with CRC-32 and a "twisted GFSR generator" (no, I don't know what that
is, but I suspect it is effective), and on top of that, hash the state
with SHA1 to generate the RNG output.  This is *not* atom bombs or
government work: a "six-sigma" estimate of the state is not good
enough.  *Exact-to-the-last-bit* is required to the best of anyone's
knowledge, and within a few seconds, the attacker is out of luck.

Yes, attacks are possible, most important the DoS attack I mentioned.

But get real; if you have to worry about an attack on this system
(other than entropy starvation), then you also need armed guards
outside the machine room, and the walls better be 2m thick missile
silo grade (and even so it's probably cheaper to penetrate the walls
than the RNG).

 > topic. If I remember there was a true random (sorry I don have time to
 > google) generator based on a kaotic randomnes source from electron

Yes, it would be nice if we could tap quantum randomness.  But quantum
randomness is only a theory; it is no more proven than the
"difficulty" (== cost of exhaustive search over the space of all
strings) of inverting SHA1.  You would *still* need to treat it as an
entropy pool and hash it to at least slow down an attack if the theory
turns out to be wrong.

The advantage to quantum randomness is not that it's "truly random".
It's that it's available in realtime, which system jitter is not.
People regularly report problems with /dev/random because they run
themselves out of entropy.

BTW, "chaotic randomness" is an oxymoron.

Mathematical chaos is *not* random.  Chaos is *precisely* the
continuous analogue of discrete pseudo-randomness; it's just that
the required precision is infinity, thus making accurate prediction
difficult as the horizon increases.  However, by spending the effort
to acquire more precise data, you can extend the horizon for which
accurate prediction can be made.