[Cryptography] Proper Entropy Source

John Denker jsd at av8n.com
Thu Jan 23 05:42:21 EST 2020


A couple of balloonists managed to get completely lost.
They called down to a guy on the ground. 
  --Balloonist:   Hey!  Excuse me!
		  Can you tell us where we are?

  --Pedestrian:   You're in a balloon.

The answer was true but completely useless.  I mention this
because on 1/22/20 9:30 PM, Mansour Moufid wrote in part:

> Given two finite schemes A and B, the entropy of the product AB is
> H(AB) = H(A) + H(B|A).
> 
> If A and B are independent then H(B|A) = H(B) and H(AB) = H(A) + H(B).
> 
> It is always true that H(B|A) <= H(B).
> 
> In the worst case, B is deterministic, then H(B|A) = 0 and H(AB) = H(A).
> 
> The proof of this property is in the first chapter of "Mathematical
> Foundations of Information Theory" by Khinchin.

Why yes, we *are* in a balloon, TYVM.

> In other words, software can never increase entropy,

Again, true but uninformative.
Some guy named von Neumann pointed that out in the 1940s.

> at best it contributes nothing.

Not true.  Not a consequence of the foregoing equations.
Software can increase randomness, as defined below, even
though it does not increase entropy.  This is often not
merely desirable but essential.

  The word means different things to different people,
  but in crypto context the following definition is
  often close enough:
        random means "not guessable by adversaries"

Software contributes a great deal, because every source
of entropy produces less than 100% entropy density.
There is some squish mixed in.  Software is needed to
increase the /density/ of entropy (without increasing
the total entropy) ... and/or to hide the squish so it
cannot feasibly be exploited.

There is no such thing as a RNG that is 100% physics
entropy with 0% algorithmic crypto.  Or vice versa.

> You mean source of randomness,
> entropy is the measure of randomness. [a]

1) Even if that were true, it would be silly.  How to you 
propose to increase a thing without increasing the measure
of the thing?

2) The word "random" means different things to different
people.  Nothing anybody says in this forum is going to
change that.

The definition implied by assertion [a] is not particularly
useful, because it means that PRNGs do not exist.

Let's be clear:  In a great many real-world situations, a
cryptologically strong PRNG is random enough for the purpose
(i.e. not guessable by adversaries) even though its entropy
density is nowhere near 100%, in fact very close to 0%.

A good HRNG produces an entropy density that is within epsilon
of 100%.  However (!) this epsilon is not the only (or even
the primary) measure of quality.  Reducing epsilon is often
not a good use of time and effort; it is better to use crypto
algorithms to make sure epsilon doesn't matter.


More information about the cryptography mailing list