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

Erik Zenner ez at cryptico.com
Fri Mar 24 04:14:46 EST 2006

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


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

More information about the cryptography mailing list