[Cryptography] Entropy is forever ...

Thierry Moreau thierry.moreau at connotech.com
Tue Apr 21 10:10:55 EDT 2015


Hi!

Thanks for this feedback from the practitioner perspective.

See below for a comment.

On 04/21/15 06:28, dj at deadhat.com wrote:
>> 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

My suspicion (in trying to adapt the theoretical work to trustworthy 
implementations) is that no heuristic can do this entropy extraction 
with 100% efficiency. Here is an ideal extractor algorithm and an 
artificial distribution that (I guess) shows what I mean. 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 entropy extractor designer does not know for sure the 2^264 bit 
message distribution.

The ideal extractor is a fixed pseudo-random mapping from 264 bit 
strings to 256 bits ready to seed the PRNG (it is "pseudorandom" in 
order to wipe out statistical defects not considered in the artificial 
distribution). The mapping of the singular message creates a statistical 
defect in the seeding operation.

So, even if the minimum entropy is larger than the PRNG seed size, it 
seems impossible to design an extractor that can reach full entropy for 
the PRNG seed.

 From the practitioner perspective, the artificial distribution is a 
secondary consideration but the conclusion inferred from it may be 
relevant. This is why I prefer a larger PRNG seed (and internal state) 
larger than the key space sizes for the cryptography downstream in the 
random data processing flow.

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

Yes, "it's not necessarily the best way" because there seems to be no 
best way.

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

Again, thanks for the feedback.



More information about the cryptography mailing list