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 [EMAIL PROTECTED]
