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?
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
More information about the cryptography
mailing list