pools of entropy

Carl Ellison (cme@acm.org)
Tue, 14 Jul 1998 17:24:47 -0400

• Next message: Ben Laurie: "Re: One real life secure random generator"
• Previous message: Steve Reid: "Re: What is entropy?"
• In reply to: bram: "Re: What is entropy?"

-----BEGIN PGP SIGNED MESSAGE-----

At 02:15 PM 7/14/98 -0700, Steve Reid wrote:
>AFAICS, both of these boil down to keeping some N secret key bits around
>(in this case, stored in a PRNG) to ensure that there are at least N
>bits of entropy in the final output.
>
>I think the simplest way to accomplish this is to hash incoming random
>bits using a MAC (a keyed hash) and use that to seed the PRNG. If
>someone can cryptanalize the PRNG and determine the state, they would
>have to reverse it to the seed and then break the MAC in order to get
>your N bits of "reserve entropy" and know all future PRNG output.

For continuous running RNG's, you have to assume that the supply and demand
will not be in sync. The bits may come in at a steady, slow rate, while
they're demanded in bursts, for example.

This calls for buffering. It's standard I/O programming. Sometimes you
need large buffers, sometimes only small ones. It depends on the rates and
probability distributions of arrivals and departures and the wait you're
willing to impose on the requester of bits.

So -- I can imagine needing a buffer of thousands of bits of good randomness
to be milked for a really bursty demand.

Milking the buffer can be messy.

You can hash down incoming bits to known good bits and then just buffer and
deliver them -- or you can buffer the raw incoming bits and then hash over
the whole buffer whenever you milk. I generally prefer the latter. It has
the advantage that if an attacker gets a snapshot of the buffer at some
point, his information soon becomes outdated while under the former scheme
he ends up knowing with certainty what some of the RNG outputs will be.

So, between buffering output and input, I opt for buffering input.

 - Carl

-----BEGIN PGP SIGNATURE-----
Version: PGP for Personal Privacy 5.5.3

iQCVAwUBNavMnhN3Wx8QwqUtAQFlrgP/TqW90Z/pdUlCZ1sdVn93DlVlYA+mYk2V
YVGZY7HN/HqxdCOkcVxiMFRdt5cKISsQrUq2yK59fSc+z1T/n3EUXISo1/A3jKHF
lHvzVhWPAPJWaf0VDWLqNS4LR2SdxoXDcmZVewL1tlbrqDoAabDiKXis9z4CR9wH
Eg9jAQ5r+V0=
=6P6O
-----END PGP SIGNATURE-----

+------------------------------------------------------------------+
|Carl M. Ellison cme@acm.org http://www.clark.net/pub/cme |
| PGP: 08FF BA05 599B 49D2 23C6 6FFD 36BA D342 |
+-Officer, officer, arrest that man. He's whistling a dirty song.--+

• Next message: Ben Laurie: "Re: One real life secure random generator"
• Previous message: Steve Reid: "Re: What is entropy?"
• In reply to: bram: "Re: What is entropy?"