Re: strengthening /dev/urandom

From: David Wagner (daw_at_taverner.cs.berkeley.edu)
Date: 08/20/04 

Date: Thu, 19 Aug 2004 23:33:15 +0000 (UTC)

Paul Rubin wrote:
>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.

I suspect you're not addressing me, but in case it helps avoid confusion:
personally, I wouldn't take that position.

I don't have any evidence that the entropy estimates are bad. In fact,
I expect most of the time the entropy estimates are just fine (I
don't claim to have any evidence for this, it is just my suspicion).
The entropy Linux /dev/random estimators attempt to be conservative,
and it seems like they leave a lot of room for slop here.

But I'm also saying that I haven't seen much evidence that the entropy
estimators are great, either. And I have to suspect -- again, without
evidence -- that, in some plausible scenarios, they're not going to
do the right thing, and you could be unhappy with the results. Again,
the caveat: I'm only claiming you'll be unhappy if you care about true
information-theoretic entropy with security against state compromise
attacks. For most apps, I believe computational security is fine, and
in that case these concerns totally go away. In randomness generation,
crypto can absolve a whole lot of mistakes in entropy estimations, as
long as you're satisfied with computational security.

For those who care about information-theoretic true entropy nonetheless,
well-- If you want high assurance, you want something more than "most
of the time you should be fine", and you want some evidence of security
backed by careful analysis. I'm not sure Linux's /dev/random gives you
that level of assurance.

I trust /dev/random for the purposes I use it. My posts are mostly a
reaction to people who say they demand this set of very strong things from
a RNG (like information-theoretic security), and who believe that Linux's
/dev/random is giving them those very strong things. I'm not so sure.

I also don't believe the claims that entropy estimation is inherently
impossible. If you know something about the physical source and do the
right careful analysis, in some cases I think you can come up with some
defensible estimates. It's not clear whether this has been done for
the sources to Linux's /dev/random. I'd bet a nickel or two it hasn't,
at least not for most of them, but I could well be wrong.