Re: What is entropy?

Steve Reid (sreid@alpha.sea-to-sky.net)
Tue, 14 Jul 1998 14:15:46 -0700 (PDT)

• Next message: Carl Ellison: "pools of entropy"
• Previous message: David Wagner: "Re: Random Data from Geiger Counter"
• Maybe in reply to: William H. Geiger III: "Random Data from Geiger Counter"
• Next in thread: Cicero: "Re: What is entropy?"

On Tue, 14 Jul 1998, bram wrote:
> The attack I'm worried about is one where the attacker has already
> completely cracked everything in the system (knows internal state,
> controls inputs, knows when outputs happen) and is now attempting to
> induce statistical bias in it's output.
[snip]
> If an application is getting fed strings which only contain small
> amounts of entropy, it's necessary to set up two PRNGs, the first one
> of which simply acts as a collection area for entropy, it's output
> being fed into the 'main' PRNG which is used for output.

Maybe I don't understand your idea, but it sounds like you're suggesting
this:
1- Encrypt incoming random bits with a PRNG
2- re-seed the main PRNG using the result of step 1

or this:
1- re-seed the main PRNG using incoming random bits
2- encrypt the PRNG output using some other PRNG

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.

This obviously does not save you from someone who determines the PRNG
state by gaining read access to your RAM, because they could read your
reserve entropy too. Also, you need a reliable source of randomness to
generate your reserve entropy in the first place. It should at least
reduce damage when your PRNG is cryptanalized and entropy sources are
poisoned _after_ the system is up and running.

Is this what you had in mind, or am I totally off-base?

• Next message: Carl Ellison: "pools of entropy"
• Previous message: David Wagner: "Re: Random Data from Geiger Counter"
• Maybe in reply to: William H. Geiger III: "Random Data from Geiger Counter"
• Next in thread: Cicero: "Re: What is entropy?"