[Cryptography] Entropy is forever ...

[John Denker]

On 04/21/2015 07:10 AM, Thierry Moreau wrote:

> Take a 256 bits PRNG seed and a 256+8=264 bits random message source 
> with with a uniform distribution for the 2^264 messages except that a
> specific message occurs 16 times more often. The minimum entropy 
> measure would thus be 260 (based on the message sample with the 
> highest probability).

The quantity calculated there is called the /surprisal/.
It is not properly called the entropy, or the min-entropy, 
or anything like that.

Here's how you know:  The surprisal is a very simple function
of the sample.  For any given distribution P, the surprisal
of the (i)th sample is 
      $(i) := log(1 / P(i))

The entropy is a functional of the distribution as a whole.
It is an ensemble average, i.e. the expectation value of
the surprisal:

      S[P] := ∑ P(i) log(1 / P(i))

Again:  For any given distribution, the entropy is a property
of the given distribution ... not a property of any particular
sample that may have been drawn from such a distribution.

To say the same thing the other way:  If it's a property of 
the sample, it cannot possibly be the entropy.

> it seems impossible to design an extractor that can reach full 
> entropy for the PRNG seed.

You have to decide what you're trying to do. 
 a) If you're building a PRNG, the objective was never to 
  achieve 100% entropy density anyway.  The output of a 
  PRNG is a lot closer to 0% than to 100% entropy density.
  That's how you know it's a PRNG.
 b) If you're trying to build some sort of whitener to
  hang on the output of a HRNG, that's something else
  entirely.  Then you care about the approach to 100%
  entropy density.

Both of these are interesting tasks, but they are not the
same thing.  Not even close.

We can agree that it appears(*) impossible to build a 
practical HRNG (or whitener) that emits exactly 100% 
entropy density ... although a good HRNG comes very
very very close.

(*) I can't prove it's impossible, but I've never seen
it done, and I can't imagine how it could be done.  It
doesn't really matter, because (with a lot of effort)
one can come close enough for any practical purpose.

> From the practitioner perspective, the artificial distribution is a 
> secondary consideration

The artificial example given above is a mild case of
something that is absolutely primary in the design of 
any practical HRNG ... in some sense the definition
of the task.  The core task of any HRNG is to start 
with a screwy distribution and transform it into a nice
distribution.  You need a thousand pieces of tricky
infrastructure to support that core, but still it's 
the core and the raison d'être.

> Before the Edward Snowden wake-up signal, it would have been silly to
> publicly suspect NIST to be influenced by the NSA for PRNG seed sizes
> exactly fit to the cryptographic processing downstream.
> Understandably, the role of the NSA is to preserve its future ability
> to "break some of the codes some of the times" and a few bits of
> entropy surreptitiously chopped off from the key space is a small
> gain for them.

That's not the right way to think about it.  Although
entropy has many important uses, it is *not* the answer
to all the world's questions.  In fact, in modern
cryptology, entropy is the answer to a verrry tiny
subset of questions.  The strength of a PRNG depends 
on (among other things) the computational difficulty 
of breaking it;  it is *not* measured in terms of entropy.
Any PRNG is easy to break in the NP sense.  That's what 
"pseudo" means.  That's what makes a PRNG different 
from a TRNG.  In contrast, the definition of entropy 
makes absolutely no mention of computational feasibility.

Secondly, the NSA backdoor in the Dual_EC_DRBG PRNG does
not merely remove "a few bits" from a large search space;
it makes the search trivial.

Thirdly, more than a few people knew about the backdoor,
years before the Snowden revelations.  Snowden made it
more widely known, confirmed it was intentional, and
showed that it was part of a much larger program.  Still,
the people who noticed it earlier are not "silly" people.