Entropy Definition

Perry E. Metzger perry at piermont.com
Fri Mar 24 11:13:38 EST 2006


"Erik Zenner" <ez at cryptico.com> writes:
>> Shannon entropy is the one most people know, but it's all 
>> wrong for deciding how many samples you need to derive a key. 
>>  The kind of classic illustration of this is the probability 
>> distirbution:
>> 
>> 0 occurs with probability 1/2
>> each other number from 1 to 2^{160}+1 happens with 
>> probability 2^{-161}.
>> 
>> The Shannon entropy on this distribution is 81.5 bits.  But 
>> if you tried to sample it once to generate an 80-bit Skipjack 
>> key, half the time, I'd guess your key on my first try.  
>
> It's entirely correct that entropy is the wrong measure here, but
> the question is how a good measure would look like. 

I think that, in practice, what you want is pretty easy. If you are
picking a key, you want the key generator to have an absolutely flat
distribution.

In fact, I think that the "randomness distillation" problem for key
generation that people try to solve with hash functions can be
expressed this way:

Given an M bit pool with an entropy of at least K bits, M > K, produce
a J bit output, with J < K, and with the symbols of the J bit output
being of an absolutely flat distribution in repeated experiments even
though the M bits of the pool are not of a flat distribution in
repeated experiments. In other words, you want something with skew but
at least K bits of entropy to turn into something without skew and J
bits.

In that sort of case, if I use the output to pick a cryptographic key,
I am probably fairly safe.

Alternatively, one could go for a more direct definition. One could
claim that what one wants is to turn an M bit pool pool that at each
iteration gets K fresh bits of entropy but which may have a skewed
probability distribution into a sequence of J bit values such that,
even given all the members of the sequence up until now, one cannot
guess the value of the next element of the sequence with probability
greater than 1/(2^J).

Perry

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com



More information about the cryptography mailing list