[Cryptography] Entropy is forever ...

[John Denker]

  "When it was announced that the Library contained
   all books, the first reaction was unbounded joy."
			/The Library of Babel/
			Jorge Luis Borges (1941)



On 04/20/2015 11:28 PM, dj at deadhat.com wrote:

> The adversary may see the output of a seeded PRNG as effectively full
> entropy

Please don't abuse the terminology of "entropy" in this
way.  
 ++ There is such a thing as a computationally-strong
  pseudo-RNG (CSPRNG).
 ++ There is also such a thing as a true-RNG (TRNG).  A 
  good hardware-RNG (HRNG) closely approximates a TRNG.

A CSPRNG and a TRNG are both interesting, but they are 
not the same thing.  Really not.

Suggestion:  If you mean randomness, please say "randomness".
Entropy is a very special kind of randomness;  it is not an
all-purpose synonym for randomness.

> From the system design point of view, you want to judge it by the
> min-entropy of the source process,

Sorry, no.  The entropy density of a PRNG is a lot closer
to zero percent than it is to 100 percent ... and is not
the basis for judgment.  That's how you know it's a 
pseudo-RNG not a true-RNG.

A PRNG is judged on (among other things) whether breaking
it is /computationally feasible/.  This stands in contrast
to the definition of entropy, which has got nothing to do 
with computational feasibility.  In particular, breaking 
*any* PRNG will always be easy in the NP sense;  you just 
have to figure out the internal state.  In contrast, a 
TRNG has no seed and no long-term state ... and the amount
of entropy cannot be reduced with NP work or any other 
amount of work.

It may be that for this-or-that practical purpose, you
don't care whether something is impossible in principle
or merely "hard enough" ... but still, you've got nothing
to gain by trampling on the distinction.  If you don't
really mean entropy, please don't call it entropy.  Call
it "randomness" or whatever.

> Wigdersen got it right when he said entropy is a function of the observer.
> It is. But entropy is also a function of the generation process.

There is no "also".  Entropy is a function -- technically
a /functional/ -- of the distribution.  If you know the
distribution (aka ensemble aka macrostate), you don't care
who or what the observer is.

Sometimes when I am observing things ... e.g. when playing
poker ... I change my mind about what distribution to use.
This changes the entropy, even though the observed string
and the generation process remain the same.  The observer
remains nominally the same.  I suppose you could say the
state of the observer changed, but in any case, the only
thing that matters is the /distribution/.  Entropy is
*defined* to be a property of the distribution.  It is
an ensemble average, specifically the expectation value
of the surprisal.

> If the feedback variable (and all real sources have a feedback variable)
> follows a gaussian distribution, you can always show that there will be a
> window in time when the entropy asymptotically approaches zero, even
> though the majority of the time it's 99.99999%

I have no idea what that's talking about, but it's not
talking about entropy.

First of all, not all real sources have a relevant
feedback variable.  It is entirely possible to build
a HRNG that produces 99.99999% entropy density without
using any long-term memory.  One batch is completely
independent of previous batches.  In digital-filter
terms, it's FIR, not IIR.  No feedback.

  It's fairly common practice to stick in some
  feedback anyway, even though it falls into the
  category of belt+suspenders.  If done halfway
  competently, such feedback does not weaken the
  HRNG, not even a little bit.  Random XOR random
  is still random.

Secondly, entropy is properly defined in terms of 
an ensemble average.  Averaging over the ensemble
washes out most of the time dependence.  There is
such a thing as "entropy fluctuations" but they're
not good for anything;  the cost of identifying a
fluctuation exceeds any value you could hope to
get from it.  There is an extensive literature on
the topic of Maxwell demons.
  Maybe this-or-that screwed-up implementation has
  a "window in time" where things go wrong, but that
  does not "always" happen.
If we now assume a decent HRNG implementation, the
output entropy density never goes to zero, not even
close, not asymptotically or otherwise.  If at some
point the output string looks non-random to you, 
that's not a reflection of the actual entropy, as 
you can verify by looking at other members of the 
ensemble.

Suggestion:  Even though you can "usually" replace
the ensemble average by a time average, if you are
in a situation where you think fluctuations might
be important, you can save yourself a *lot* of
trouble by not doing that.  Rely on the ensemble
average.