Entropy and PRNGs

[Ben Laurie]

John Denker wrote:
> 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.

The point I am trying to make is that predictability is in the eye of 
the beholder. I think it is unpredictable, my attacker does not.

By your argument, no PRNG ever has any entropy, since the inputs are 
clearly known (at least to the PRNG).

> *) 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.

I do say what it is conditioned on, further up the page.

> 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).

One-time pads are not PRNGs, so I don't really see the relevance of 
this. I do agree that not all cryptographers want the same thing, I was 
trying to make a general point which is, I believe, largely valid.

> 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.

Indeed - but it needn't be unknown to a potential attacker, which is 
precisely what I am getting at.

> *) 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.

This seems to me to be exactly the opposite of what you just said ... 
i.e. "your collision resistance depends on the number of different seeds
your PRNG can have ... which is plain old 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.

That's just silly. "True" clearly applies to "PRNG", not to "RNG".

Cheers,

Ben.

-- 
http://www.apache-ssl.org/ben.html       http://www.thebunker.net/

"There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit." - Robert Woodruff

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