Re: strengthening /dev/urandom

From: Paul Rubin (//phr.cx_at_NOSPAM.invalid)
Date: 08/20/04 

Date: 19 Aug 2004 15:42:12 -0700

Tom St Denis <tomstdenis@iahu.ca> writes:
> As I understand the code /dev/random isn't an RNG. True RNG support is
> provided by other /dev/<name> virtual files. /dev/random is just a PRNG
> which *happens to* block when it *guesses* it lacks the entropy required.

Is that right? I thought /dev/random was a pseudo-device that
gathered measurements taken from various places around the kernel, as
well as (optionally) some from user inputs, and ran those measurements
through a PRNG. Maybe the PRNG is cryptographically clever, and
Fortuna as a PRNG is maybe even more clever. But the interesting part
is the non-PRNG part, i.e. the part that takes physical measurements
and tries to estimate the amount of entropy in them.

You guys are saying the entropy estimates are bad and we shouldn't
believe them. I'm ok with that notion. Then you say it's impossible
to come up with better estimates, so you refuse to do so. That's fine
too, if you replace the estimates with the most conservative possible
estimate, namely zero, and conclude that /dev/random should simply not
be trusted for security purposes. But it seems to me that you're
saying two conflicting things:

  1) there is no way to put a believable number on the amount of entropy
     inside /dev/random at any moment;
  2) despite that, it's still ok to use /dev/random in security apps.

That just doesn't make sense to me.

Question for JLC, who seems to say that entropy estimation is
inherently impossible no matter what hardware you use: imagine you
have an experimental setup containing one atom of some radioactive
isotope with a 23.5 second half-life. The experiment simply monitors
that atom for 23.5 seconds and outputs a 1 if the atom decays during
that interval, and a 0 otherwise. Do you claim that this device is
not a TRNG? Do you claim that you can't, with great confidence,
estimate the output entropy as being very close to 1 bit?

I'm asking this to check whether I have some severe misconception
about JLC's claims.

Relevant Pages

  • Re: strengthening /dev/urandom
    ... > well as some from user inputs, and ran those measurements ... > through a PRNG. ... > and tries to estimate the amount of entropy in them. ... any security is to have some events. ...
    (sci.crypt)
  • Re: new /dev/random
    ... For a proper PRNG, with the assumption that the algorithms are robust, ... is said to contain 40 bits of entropy if I could, ... If I want to attack a stream of 56 bits produced by a PRNG with a seed ... RNG resistance therefore relies on the same two classes of assumptions ...
    (sci.crypt)
  • Re: new /dev/random
    ... > is said to contain 40 bits of entropy if I could, ... > efficient attack would be to try the exhaustive search on the seed. ... > than the PRNG: evolution of computer science (the robustness of the ... > because, for a given length of random bits requested, the RNG will have ...
    (sci.crypt)
  • Re: Key entropy, stream entropy, block entropy, block population entropy AKA uniique stream length
    ... output (PRNG block) from the internal states. ... Now I encrypt with the key-stream. ... entropy and nothing will change that. ... Now, you say, "But those key-streams (permutations) are not the only ...
    (sci.crypt)
  • Re: strengthening /dev/urandom
    ... >>delivering true randomness should be somehow like the shelves ... >>has certain commodities in reserve. ... >>document that doesn't need any entropy. ... First discuss whether 'any' PRNG is needed. ...
    (sci.crypt)