Entropy and PRNGs

[John Denker]

Ben Laurie wrote:
> Given recent discussion, this is perhaps a good moment to point at a 
> paper I wrote a while back on PRNGs for Dr. Dobbs, where, I'll bet, most 
> of you didn't read it.
> 
> http://www.apache-ssl.org/randomness.pdf

I just took a look at the first couple of pages.

IMHO it has much room for improvement.

*) For instance, on page 2 it says

>> I can have a great source of entropy, but if an attacker knows
>> all about that source, then it gives me no unpredictability at
>> all.

That's absurd.  If it has no unpredictability, it has no entropy,
according to any reasonable definition of entropy, including the
somewhat loose definition on page 1.

*) Later on page 2 it says:

>> Cryptographers want conditional entropy, but for UUIDs, and
>> other applications, what is needed is unconditional entropy.

First of all, you can't throw around the term "conditional
entropy" without saying what it's conditioned on.  For a PRNG,
unpredicatbility conditioned on knowing previous outputs is one
thing; unpredictability conditioned on knowing the entire
internal state is something else entirely.

More importantly, there are lots of cryptographers, and they
don't all want the same thing.  In particular, the entropy
of a good one-time pad is unconditional, in the sense that
you can condition it on anything you like and the entropy is
unchanged (with the trivial exception of 100% correlation to
the counterpart pad locked up in the safe at headquarters).

Also importanty, for UUIDs no entropy is required at all.
A globally-accessible counter has no entropy whatsoever, and
suffices to solve the UUID problem   OTOH if you demand an
offline, autonomous method for generating UUIDs, your
collision resistance depends on the number of different seeds
your PRNG can have ... which is plain old entropy, the same
sort needed when making one-time pads.

*) At the bottom of page 2 it says:

>> Well, for many purposes, the system time has plenty of
>> unconditional entropy, because it is usually di erent when
>> used to generate different UUIDs.

No, the system time has no entropy whatsoever, not by any
reasonable definition of entropy.

*) On page 4, I find the name "trueprng" to be an oxymoron.
The P in PRNG stands for Pseudo, which for thousands of
years has meant "false", i.e. the opposite of true.


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