Entropy and PRNGs

John Denker jsd at av8n.com
Mon Jan 10 00:21:49 EST 2005


Referring to http://www.apache-ssl.org/randomness.pdf
I wrote:

 >>I just took a look at the first couple of pages.
 >>IMHO it has much room for improvement.

David Wagner responded:

> I guess I have to take exception.  I disagree.  I think Ben Laurie's
> paper is quite good.  I thought your criticisms missed some of the points
> he was trying to make (these points are subtle, so this is completely
> understandable).  Presumably his paper could be criticized as not clear
> enough, since it seems it did not convey those points adequately, but
> I don't think his paper is inaccurate. 

Or perhaps it was my critique that was not clear enough.

I am not motivated to look for subtle shades of meaning in a
paper that claims the system clock is a source of entropy.

 >>First of all, you can't throw around the term "conditional
 >>entropy" without saying what it's conditioned on.
 >
 > 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

>> If it has no unpredictability, it has no entropy,
>>according to any reasonable definition of entropy, including the
>>somewhat loose definition on page 1.
> 
> 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.

> For instance, imagine if we use packet inter-arrival times (measured down
> to the nanosecond) as our randomness source. 

I am unable to imagine myself being so silly.

> This is the difference between unconditional and conditional entropy that
> Ben was trying to introduce.  In information-theoretic notation, H(X)
> vs H(X|Y).  Let X = packet inter-arrival time, and Y = everything seen by
> a local eavesdropper, and you will see that H(X|Y) can be much smaller
> than H(X).  Indeed, we can have H(X|Y) = 0 even if H(X) is very large.
> This is Ben's point, and it is a good one.

No.  There is only one entropy that matters in an adversarial
situation.  The so-called "unconditional entropy" H(X) is
merely a wild overestimate of the only thing that matters.

"There is no glory in outstripping donkeys."  (Martial)

There is no honor in introducing H(X) since it is irrelevant
in any adversarial situation.

> A counter is fine as long as there is only one machine in the universe
> that will ever assign UUIDs.  However, if you want to do distributed
> generation of UUIDs, then counters are insufficient because there is no
> way to prevent overlap of two machine's counter spaces.

I imagine a smart person such as DAW should be able to come
up with five schemes in five minutes whereby UUID generation
can be delegated to virtually any machine that wants it.
MAC(eth0) /concat/ local counter will do for scheme #1.

> Perhaps what Ben should have said is that:
> * Unconditional entropy is sufficient for UUIDs;
>   conditional entropy is not needed.
> * For centrally-assigned UUIDs, even unconditional entropy is unnecessary;
>   a centrally-managed counter is fine.
> * For distributed, unsynchronized assignment of UUIDs, unconditional
>   entropy appears to be necessary and sufficient.

Horsefeathers.  For generating  UUIDs,  _zero_ entropy is
sufficient, and no positive amount of entropy (unconditional
or otherwise) can be called necessary.

I am not interested in ways of obtaining wild overestimates
of zero.

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.


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



More information about the cryptography mailing list