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

["Nguyen Vu Hung" <vuhung16plus@??>]

On 2/23/07, Stephen J. Turnbull <stephen@??> wrote:
> Nguyen Vu Hung writes:
>
>  > The term hard is confusing and doesn't have any metrics.
>
>  > * How "hard" it is to predict the randomness of /dev/random ?
>
> Essentially impossible for non-realtime applications.
This is an important point. My question is "how "hard"  is is". I did
mean I want quantative explanations like: The complexity of the
algorithm is, the time it takes to do X is Y seconds etc.... I think
the term "hard" or "high quality" should be avoid ( see the comment at
the header of ./drivers/char/random.c ) > Theodore Ts'o

>  > * Is there any way to choose a seed other than the system timer ?
>
> Read the code.  Probably not, and it probably doesn't matter, because
> the seed is something like nanoseconds % 1000, I would bet.
Deterministic seed is timer, all other "noise" is non-deterministic.
The author ensure the security by system startup time. He assumes that
the attacker can't know the system startup time if he don't have root
( in the case, we are already doomed ). For a non-realtime system like
Linux, by adding non-deterministic noise to the seed, we make the seed
harder  to predict.

# What if the attacker gets root, he reboots the system and try to do
something more sophiciated with the RNG?

The background of random.c is this paper.

http://www.ietf.org/rfc/rfc4086.txt
Randomness Requirements for Security

>  > * Any example run ( or papers ) out there on how to predict the
>  > randomnese of /dev/random ( or the randomese of ( computer
>  > generated ) random number ?
>
> /dev/random may or may not be random (cf. the Improbability Drive from
> The Hitchhiker's Guide to the Galaxy).  However, it is essentially
> unpredictable (it's a true one-time pad), with the important exception
> of the DoS attack I described.

I still don't agree with you that it is unpredictable, though I don't
have enough clues :D.

> For pseudo-random numbers, start with Donald Knuth, _The Art of
> Computer Programming_, vol. 1 (Fundamental Algorithms).  That was
> written about 30 years ago, but it will keep you busy for a while. ;-)
> I can do the math for Knuth, it's elementary (but not easy).
It is 170 pages on Chaper 3, Volumes 2, Seninumerical Algorithms. I
read the books 2 or 3 years ago when I was in university. Thank you. I
read it again and found that I lack some very fundametal background.

Btw, this is quoted from the book:

-------------------------------------------
Any one who considers arithmetical
methods of producing random digits
is, of course, in a state of sin.
â JOHN VON NEUMANN A951)
--------------------------------------------

The algorithms Knuth introdues in his book are all deterministic. The
sequence of random number generated by such algorithms depend on the
seed. That's why we have to add (non-deterministic ) noisy to the
seed.

> A shorter, but very hard, path to enlightenment would be to start at
> the Rc4 article on Wikipedia.  ARC4 is a very well-known, high-quality
> stream cipher, although it seems that it is not currently considered
> sufficiently secure for wireless networks (thus the deprecation of
> WEP).  I can't hack the math in most of the papers cited here.

I will read them.

--
Best Regards,
Nguyen Hung Vu
vuhung16plus{remove}@??
VIQR Standard: http://vi.i18n.kde.org/viqr
http://www.flickr.com/photos/vuhung/tags/fav/