[21574] in cryptography@c2.net mail archive
RE: Entropy Definition (was Re: passphrases with more than 160 bits of entropy)
daemon@ATHENA.MIT.EDU (Erik Zenner)
Fri Mar 24 11:04:30 2006
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
Date: Fri, 24 Mar 2006 10:14:46 +0100
From: "Erik Zenner" <ez@cryptico.com>
To: <cryptography@metzdowd.com>
> Shannon entropy is the one most people know, but it's all=20
> wrong for deciding how many samples you need to derive a key.=20
> The kind of classic illustration of this is the probability=20
> distirbution:
>=20
> 0 occurs with probability 1/2
> each other number from 1 to 2^{160}+1 happens with=20
> probability 2^{-161}.
>=20
> The Shannon entropy on this distribution is 81.5 bits. But=20
> if you tried to sample it once to generate an 80-bit Skipjack=20
> key, half the time, I'd guess your key on my first try. =20
It's entirely correct that entropy is the wrong measure here, but
the question is how a good measure would look like.=20
Assume that you have a sample space with N elements and an intelligent=20
attacker (i.e., one that tries the most probable elements first). Then=20
what you actually are interested in is that the attacker's probability=20
of success after q sampling attempts is as close as possible to the=20
lowest possible, namely q * 2^{-N}. A natural way of measuring this=20
seems to be some kind of distance between Pr[succ after q samples] and=20
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=20
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@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.=20
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
