[Cryptography] Entropy is forever ...

dj at deadhat.com dj at deadhat.com
Tue Apr 21 02:28:37 EDT 2015

>In the crypto business, more often than not, when people
>talk about «the» distribution they are talking about the
>distribution /as seen by the attacker/ ... but I am not
>touting this as a reliable rule.

I don't like that definition much, not because it's wrong, but because
it's far from the worst case.

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.

The adversary may see the output of a seeded PRNG as effectively full
entropy is she is ignorant of the generation process of the seed and the
algorithm of the PRNG. Without the compute power to do the brute force
thing, she's out of luck and can predict no better than chance. The
'distribution' looks uniform to her, but may look far from uniform to a
better informed observer.

>From the system design point of view, you want to judge it by the
min-entropy of the source process, because it's the best informed view and
therefore the worst case metric.

The whole notion of measuring entropy (and min-entropy) from distributions
doesn't sit well with me because you can't actually do it. With a full
entropy source, all distributions from all samplings are equally possible.
With a non stationary source (and all real sources are non stationary),
the distribution is not a simple thing to analyze because it's a function
of when you look. The short term distribution is completely different to
the distribution over the lifetime of the hardware. So which mode of
observation are you going to use? The 'over all time' one, or the one that
matters when the hardware is used?

With a source which has gaussian behavior, those tails go out to infinity.
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%

One aspect of RNG design that I've concluded is good practice is to have a
pool structure entropy extractor where the pool size is (1) The same size
as the reseed needs of the PRNG and no bigger and (2) at least big enough
that it's simple to show the 'asymptotically approaches zero' case won't
happen in the lifetime of this universe. 256 is a good size, but it
depends on your entropy source and extraction algorithm. It's not
necessarily the best way, but it's a way that permits simple analysis by
anyone with a basic grasp of statistics.

My views may have been skewed by having to design RNGs for high volume
products for the past few years and also having to evaluate and test other
people's RNGs. There are more ways to get it wrong than a jaded skeptic
like me can thing up of an evening.

More information about the cryptography mailing list