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

[Erik Zenner]

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

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?

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

This e-mail may contain confidential information which is intended for
the addressee(s) only and which may not be reproduced or disclosed to
any other person. If you receive this e-mail by mistake, please contact
Cryptico immediately and destroy the e-mail. Thank you.

As e-mail can be changed electronically, Cryptico assumes no
responsibility for the message or any attachments. Nor will Cryptico be
responsible for any intrusion upon this e-mail or its attachments. 


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