From: Bill Stewart <stewarts@ix.netcom.com>
Date: Sun, 5 Nov 1995 08:08:41 +0800
To: cypherpunks@toad.com
Subject: /dev/random - using up entropy?
Message-ID: <199511042352.PAA07554@ix4.ix.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain


The discussions of what to do when /dev/random has handed out all of its
available entropy have assumed that entropy gets used up; I'd like to 
propose that maybe it doesn't, at least in the computational-complexity
sense that says that you don't have the computational power around to
calculate the information inside /dev/random from the output,
giving a sort of "computational entropy" that reflects not only the 
uncertainty you have because of randomness but also the uncertainty
you have because of your computational limitations.

Most of the designs I've seen look like this:
        A Reservoir of entropy R = R1....Rn, where n is large, 1024 or 4096
        An input stream I = I1....Ik, which is mixed into R
        A mixing function F which is used to mix R <= F(R,I) 
                for some chunk of I, possibly empty.
        A hash function H, typically MD5.
        An output O = O1...Om = H(R), and E gets mixed after every output.
                (These are capital-o, not zero...)

The entropy E of the reservoir E before an output is
        -SUM(all X) p(X) log p(X)
where X is an event R1=x1, R2=x2 ... Rn=Xn
which is equal to n, assuming the Ri are iid equiprobable 0 or 1.

After an output, the entropy is
        - SUM p(X | H(R)=O) log p(X|H(R)=O)
which works out to n-m, since p(X) is zero if H(R)!=O, and 2**m/2**n if it does.
So that says you use up m bits of entropy if you get m bits of good output.

However, what I'd like to suggest is that you don't, from the perspective
of a user who doesn't have direct access to the reservoir R of random bits.
For that user, p(X|H(R)=O) is the same as p(X) or P(X|H(R)=O'), because
the user is neither able to invert H, nor to enumerate all possible R,
nor to calculate anything useful based on multiple outputs, since the
reservoir R is shuffled between outputs; even a simple circular shift
may be enough.   This doesn't apply to the case where n is 32 or 48
and the hash function produces n-bit outputs, or even m<<n bit outputs,
because that maybe be inverted or brute-forced, but it seems to apply
for the case where n is sufficiently large and the hash is good.
If the hash is simpler than MD5, it may apply anyway, since the hash
produces far fewer bits than its input, as long as the hash and the
mixing function don't give away any information about the reservoir
between successive outputs.

This would suggest that /dev/random ought to have a mode that says
"give me output of whatever quality you have available",
and that it ought to be OK to use it, as long as the reservoir has 
been seeded with sufficient high-entropy input to have decent randomness.
#---
#                                       Thanks;  Bill
# Bill Stewart, Freelance Information Architect, stewarts@ix.netcom.com
# Phone +1-510-247-0664 Pager/Voicemail 1-408-787-1281
#---