Entropy Definition (was Re: passphrases with more than 160 bits of entropy)

[John Kelsey]

>From: Erik Zenner <ez at cryptico.com>
>Sent: Mar 24, 2006 4:14 AM
>To: cryptography at metzdowd.com
>Subject: RE: Entropy Definition (was Re: passphrases with more than 160 bits of entropy)

...
>> [I wrote:]
>> 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. 

There are a bunch of different entropy measures.  Shannon entropy is
the right one for compression ratios and channel capacity, but not for
difficulty of guessing the string.

>Assume that you have a sample space with N elements and an intelligent 
>attacker (i.e., one that tries the most probable elements first). Then 
>what you actually are interested in is that the attacker's probability 
>of success after q sampling attempts is as close as possible to the 
>lowest possible, namely q * 2^{-N}. A natural way of measuring this 
>seems to be some kind of distance between Pr[succ after q samples] and 
>the ideal function q * 2^{-N}. Such a measure might allow a designer
>to decide whether a non-perfect distribution is still "acceptable" or
>simply "far out". Is anyone aware of whether (and where) this was 
>discussed in the literature, or what other approaches are taken?

The best discussion I've seen of this is in a couple papers by John
Pliam, about something he calls the work function, W(n).  This is just
the probability of having guessed some secret value after n operations
(typically n guesses). You can generalize this to the number of
operations you have to carry out to have a given probability of
violating any security property (repeating a nonce, getting a block
collision in a block cipher chaining mode, etc).  It's a very general
way of thinking about limiting parameters of crypto algorithms.
You're basically heading toward this idea in what you said above.

Let's think of this for an ideal case: a 128-bit key.  When you have
done 2^k guesses of the key, you have a 2^{n-k} chance of having
guessed the key correctly.  So if you graphed the work vs probability
of success on a log/log chart, you'd get a straight line for the ideal
case.  W(n) = 2^{-128} n, as you said above.  

Now, consider the case where you are generating a 128-bit key from a
bunch of sampled events on your computer that have been concatenated
together in a string S.  Imagine making a list of all the possible
values of that string, and sorting them in descending order of
probability.  You now have the best possible sequence of guesses.
W(n) is the sum of the first n probabilities.  

If W(n) > 2^{-128} n for any n, then the attacker has some point where
it is to his advantage to guess S instead of guessing your key.

So, this is where min-entropy comes in.  Min-entropy is just
-lg(P[max]), the base 2 log of the maximum probability in the
distribution.  You can convince yourself than if the min-entropy of S
is at least 128, then it's never easier to guess S than to guess K.
This is because each possible input string must have probability lower
than 2^{-128}, so the sum of the first n, W(n) < n 2^{-128}.  

This doesn't solve the much harder engineering/data analysis problem
of getting some reasonable approximation for the probabilities of S,
unfortunately.  The easy way to solve that is to design a hardware RNG
in such a way that you pretty-much know the probabilty model to use
and can work out how to sample it to get a good estimate of the
probabilities.  However, it is kind of nice to recognize that you only
have to estimate the largest probability to compute the min-entropy.
(It ought to be the easiest probability to measure and bound!)  

>Erik
>
>--
>Dr. Erik Zenner       Phone:  +45 39 17 96 06    Cryptico A/S
>Chief Cryptographer   Mobile: +45 60 77 95 41    Fruebjergvej 3
>ez at cryptico.com       www.cryptico.com           DK 2100 Copenhagen

--John Kelsey, NIST


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