[703] in cryptography@c2.net mail archive
Re: Random numbers from the '60's...
daemon@ATHENA.MIT.EDU (Colin Plumb)
Tue May 6 10:37:28 1997
Date: Mon, 5 May 97 23:07:53 MDT
From: colin@nyx.net (Colin Plumb)
To: perry@piermont.com
Cc: cryptography@c2.net
> It feels right, but the times that I've asked smart crypto people
> (such as Hugo K., and Matt Blaze) for an answer to the question "can
> you distill entropy with a hash function", I've gotten answers that
> ranged from "Interesting question!" to "Well, it *should* be possible
> to answer that question one way or another... I'll try to prove some
> properties you'd need..."
Actually, it's not that hard to prove, at least until you get to the
tricky point of proving properties of hash functions.
What you need is collision freedom. If there are 2^160 possible inputs
(even if they're thousands of bits long), each of which produces a
distinct 160-bit output, then clearly no entropy has been lost.
You need the properties of a good (non-vryptographic) hash function,
namely a small number of collisions. For some limited kinds of
input distributions, you can prove this, but in general, choosing
from "god" hash functions will have to do.
Clearly, there are some data sources (such as papers written by Hans
Dobbertin) that will tax the ability of even cryptographic hash
functions to provide the collision-free property.
(Now, if you want an *interesting* question, ask, for generators like
PGP's and Linux's /dev/random that maintain an entropy estimate,
what is the sppropriate derating to apply as the pool approaches "full"?)
--
-Colin
