Re: strengthening /dev/urandom

From: Tom St Denis (tomstdenis_at_iahu.ca)
Date: 08/20/04 

Date: Thu, 19 Aug 2004 22:52:52 GMT

Paul Rubin wrote:

> 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.

The output of /dev/random is actually the output of SHA-1. That makes it a
PRNG. A von neumon rejectors on a true RNG bit source would be an example
of "processing" that doesn't make it a PRNG since the rejector is balanced.

> 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.

I never said there is zero entropy in the pool. I said making conclusions
about the entropy in the pool is meaningless. There is no 100% answer to
this problem. If you don't have an initial seed then the only way to get
any security is to have some events. Wherether you estimate their entropy
count or not you're still stuck at "until enough data comes in".

So really it's a moo point [as TBS would have me say it...].

At best you could re-write the script to say "no seed file found, move your
mouse and type keys 'randomly' for the next three minutes please."

What you're looking for is an absolute and you should know better.

I mean you AES encrypt your 20MB message with a truly random 256 bit key.
How much "security" do you have? Is it 256 bits? Are you sure? How do
you know that? Same thing here. You feed Fortuna with 1000s of inputs.
How much entropy is in there? Even if you "estimate" it are you sure? How
do you know that?

In both systems we rely on the entropy in our input sources. Just in our
case we don't rely on entropy estimation to prevent "leaking state" or
whatever it's there for.

Tom

Relevant Pages

  • Re: strengthening /dev/urandom
    ... well as some from user inputs, and ran those measurements ... through a PRNG. ... You guys are saying the entropy estimates are bad and we shouldn't ... that atom for 23.5 seconds and outputs a 1 if the atom decays during ...
    (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: Fortuna
    ... I certainly agree that information-theoretic security is a stated goal ... >state collisions (therby reducing pool entropy). ... start with any entropy, then information-theoretically secure randomness ... extraction is impossible -- at least in principle. ...
    (Linux-Kernel)
  • Re: is this double CBC?
    ... You designed something that is not supposed to add to security, instead it is designed to consume entropy, and so significantly weakens security. ... and then you go on this completely seperate tangent about how i am destroying the security of AES and CBC and everything else under the sun because i am 'consuming entropy' which i know for a fact i am not. ...
    (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)