Entropy and PRNGs

John Kelsey kelsey.j at ix.netcom.com
Mon Jan 10 13:07:32 EST 2005


>From: John Denker <jsd at av8n.com>
>Sent: Jan 10, 2005 12:21 AM
>To: David Wagner <daw-usenet at taverner.CS.Berkeley.EDU>
>Cc: cryptography at metzdowd.com
>Subject: Re: Entropy and PRNGs

>> Conditioned on everything known to the attacker, of course.

>Well, of course indeed!  That notion of entropy -- the entropy
>in the adversary's frame of reference -- is precisely the
>notion that is appropriate to any adversarial situation, as I
>have consistently and clearly stated in my writings;  see
>e.g. the end of the "definitions" section, i.e.
>   http://www.av8n.com/turbid/paper/turbid.htm#sec-defs

... 
>> Actually, I think Ben got it right.  Entropy depends on context.
>> The attacker might have extra context that allows him to narrow down
>> the possible values of the randomness samples.

>Heed your own "of course" statement.  It is hard to imagine a
>situation where my adversary has more "context" about my
>generator than I have myself.

Well, the broader problem isn't the context, it's the model.  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.

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.  Using cheaply-available sources of each kind in seeding a PRNG decreases the set of attackers that will be able to attack you,  while not preventing you from also using some source of entropy you believe to be good against all attackers.  

...
>If you want people to believe that unconditional entropy is a
>worthwhile concept, you'll have to come up with a nontrivial
>application for it.

Differentiate between measures of entropy.  Collision entropy (Renyi entropy of order two) is very useful in determining how many samples you can take before expecting a collision, and it's not conditioned on an attacker's information.  And collision probabilities do matter, in both obvious and subtle ways, for PRNG security.  

--John

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



More information about the cryptography mailing list