Re: What is entropy?

bram (bram@gawth.com)
Sun, 12 Jul 1998 20:25:33 -0700 (PDT)

• Next message: David K. Merriman: "Item in archive(s)?"
• Previous message: Trei Family: "$10,000 DES Challenge starting!"
• Next in thread: Cicero: "Re: What is entropy?"

On Sun, 12 Jul 1998, Carl Ellison wrote:

> On Sun, 12 Jul 1998, Michael F. Reusch wrote:
> > I was wondering when "mixing bad entropy with good entropy results in good
> > entropy". If an attacker can feed you things to mix in doesn't this depend
> > on the mixing function?
>
> XOR doesn't mix very thoroughly, however, so people often use
> cryptographically strong hash functions, like SHA-1, for this mixing.
> XOR doesn't carry form one bit to the next but a good hash function
> will affect each output bit with each input bit (with probability about
> 1/2).

One way of maintaining a pool of entropy is as follows:

Pick a one-way hash function to use. The pool size in the same number of
bits as the hash output.

To incorporate a bitstring into the pool, first hash the bitstring, then
xor the resust with the contents of the pool, then hash the result to get
the new contents of the pool.

The above has the following properties:

The entropy of the pool after a new bitstring is added will either be the
old entropy of the pool plus the entropy of the bitstring or the length of
the pool, whichever is smaller.

An attacker can't track the internal state of the pool after missing even
a single input.

An attacker can't force the pool into a predictable state by feeding it
bogus bitstrings.

A good way of getting random numbers out of the pool is to compute the
hash of it's negation and use that as the random output, then hash it's
non-negated value to get the new value for the pool.

It's missing a separate collection pool, but I think the above is
otherwise a fairly secure technique.

-Bram

• Next message: David K. Merriman: "Item in archive(s)?"
• Previous message: Trei Family: "$10,000 DES Challenge starting!"
• Next in thread: Cicero: "Re: What is entropy?"