Entropy and PRNGs

[John Denker]

John Kelsey wrote:
> 
> If your attacker (who lives sometime in the future, and may
> have a large budget besides) comes up with a better model to
> describe the process you're using as a source of noise, you
> could be out of luck.   The thing that matters is H(X| all
> information available to the attacker), which is based on P(X
> | all information available to the attacker), which includes a
> model that may be better than yours.

I disagree.  For the sources of entropy that I consider
real entropy, such as thermal noise, for a modest payoff I'd
be willing to bet my life -- and also the lives of millions
of innocent people -- on the proposition that no adversary,
no matter how far in the future and no matter how resourceful,
will ever find in my data less entropy than I say there is.

(For instance, under suitable conditions I might say that
there's 159.98 bits of entropy in a 160-bit word.)

Of course I'd want to make approriate checks for implementation
errors, but in principle the entropy is there and the adversary
can't make it go away.  Some guy named Shannon had something to
say about this.

> But I think it's of practical value to consider the different
> attackers whose information might not include some information
> you use for seeding a PRNG.  Some sources of entropy, such as
> packet arrival times, are not worth much for attackers on your
> local network who are attacking you in real time, but are
> quite valuable against attackers who attack you later.  Other
> sources of entropy, such as the hash of the contents of your
> Windows registry, or a full directory tree from your hard
> drive, are worthwhile against real-time attackers without
> access to your machine, but worthless against  attackers with
> your machine in their hands.  

Can you please exhibit a nonzero lower bound on the entropy
content of the windows registry?  If not, please don't call
it entropy.

In particular, I ask you to consider the case of mass-produced
network appliances as mentioned at
   http://www.av8n.com/turbid/paper/turbid.htm#sec-prng-attack
and consider whether, registry or no registry, the boxes will
be waaay too much alike.

In ordinary situations, the windows registry is constructed
by strictly deterministic processes.  No entropy.  If your
adversaries are so lame that they cannot figure out how the
registry is constructed, you're living in some kind of paradise.

> Differentiate between measures of entropy.  Collision entropy ...

Let's stay on-topic.

There is only one measure of entropy appropriate to a random
symbol generator.  If I am unable in principle to predict
the output of my HESG, then under mild assumptions that's
what I call entropy.

   By mild assumptions I mean things like assuming my
   machine has not been taken over by the attacker.  This
   assumption is of course common to *all* discussions
   of security algorithms and principles.  I mention it
   only to fend off nit-picks.  There's not much point in
   discussing algorithm "A" if you're going to turn around
   and tell me your box might be implementing some other
   algorithm.


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com