Entropy and PRNGs

[John Denker]

Ben Laurie wrote:

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

I still cannot see how that can happen to anyone unless
they're being willfully stupid.  It's like something out
of Mad Magazine: White Spy accepts a cigar from Black Spy,
lights it, and is surprised when it explodes.  That's
funny when it happens to somebody else, but as for me,
I'm not going to accept alleged "entropy" from any source
such that my adversary might know more about it than I do.
I'm just not.

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

I *almost* agree with that, but my real argument is somewhat
more nuanced:

a) Certainly there is a very wide class of PRNGs that
have no entropy whatsoever, including many that Mr. Laurie
seems willing to attribute entropy to.

b) It is also possible, as I have repeatedly explained,
for an ordinary PRNG to have a modest amount of entropy
residing in its internal state.  This entropy must
have abeen obtained from elsewhere, from something
other than a PRNG, not produced _de novo_ by any PRNG.

Categories (a) and (b) share the property of having
no nonzero lower bound on the entropy _density_ of
the output stream;  the entropy density is either
strictly zero (case a) or asymptotically zero (case b).

c) At the opposite extreme, there exist things that
produce 100% entropy density.  These must not be
called PRNGs.  I like the name HESG -- High Entropy
Symbol Generator.
   http://www.av8n.com/turbid/

d) Also as I have repeatedly explained, there exist
intermediate cases, where something that works like
a PRNG is coupled to something else that provides
real entropy.  I recommend calling this a SRSG,
i.e. Stretched Random Symbol Generator, since it
isn't just a PRNG and it isn't just a HESG either.
   http://www.av8n.com/turbid/paper/turbid.htm#sec-srandom

Linux /dev/urandom was an early and unsatisfactory
attempt at an SRSG.  Yarrow, coupled to a good HESG,
is vastly better, and that's what I implemented.


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