Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > sci.crypt > #33063

Re: Entropy Estimations for die and pass phrases

Show all headers | View raw

On 2015-10-19 12:00:54 +0000, Rob Warnock said:

> Jeffrey Goldberg  <jeffrey+news@goldmark.org> wrote:
> +---------------
> | David Eather said:
> | > Just a short table of entropy estimates
> | > (Shannon entropy for the purest hair splitters)
> |
> | It's not just hair splitting. Shannon entropy is not
> | the right measure when the distribution isn't uniform.
> +---------------
> 
> Just curious... Why not?

Imagine a password generation scheme like the following:

If it comes up 10 pick uniformly from a set of 2^512 elements.
But if it comes up with any other number use the password
"sekret".

The Shannon entropy of that is going to 51.66 bits, yet
nine times out of ten, the password will be "sekret".
Which better characterizes the strength of this password
generation scheme, H_0 at 51.6 bits or min-entropy at 0.15?

Now sure my example distribution is contrived to be extreme.
But that is only to help highlight what to look for in distributions
that may make Shannon entropy go awry. People have a very large space
password space to choose from, and anything within that space has a
non-zero chance of being used, but there is a much smaller subset that
will be chosen from.

Also remember that Shannon entropy is designed to characterize
something like the average information content of a message. But
average information content isn't the right thing for us. The attacker
doesn't care how much information there in a candidate password,
she only cares how frequent it is and will go after the most frequent
ones first.

The first attempt that I know of to explicitly replace Shannon Entropy
for this kind is


@inproceedings{Massey94:ISMT,
	Address = {Trondheim, Norway},
	Author = {Massey, James L.},
	Booktitle = {{IEEE} International Symposium on Information Theory},
	Organization = {IEEE},
	Pages = {204},
	Title = {Guessing and Entropy},
	Year = {1994}}

But that also is based on averages, entirely ignoring that fact that
with some distributions who can guess most things very very quickly,
and that the "average" case is rare.

So a much more useful notion of "guessing entropy" is in


@inproceedings{Bonneau2012:Guessing,
	Author = {Bonneau, Joseph.},
	Booktitle = {Security and Privacy (SP), 2012 IEEE Symposium on},
	Pages = {538-552},
	Title = {The Science of Guessing: Analyzing an Anonymized Corpus of 70 
Million Passwords},
	Year = {2012}}

(Sadly, I wasn't aware of that paper when I re-invented much
of it a year later.)

Now Bonnau wants to maintain some modified form of guessing
entropy when talking about the strength of an individual password,
but when talking about a password distribution, as a whole, I'm
not sure that that holds up.

The intuition with min-entropy is that because the "worst
case" is also the most common case, we should evaluate the
scheme based on that worst case.


> Shannon entropy does *NOT* require a uniform distribution!
> Never has

Yes. I very much know that. I'm sorry if I said anything that
suggested otherwise. I was trying to point out that it is
an inappropriate measure for the strength of a password
generation scheme when that scheme doesn't produce a uniform
distribution.

Cheers,

-j

Back to sci.crypt | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Entropy Estimations for die and pass phrases  "David Eather" <eather@tpg.com.au> - 2015-10-18 12:05 +1000
  Re: Entropy Estimations for die and pass phrases Robert Wessel <robertwessel2@yahoo.com> - 2015-10-18 00:14 -0500
    Re: Entropy Estimations for die and pass phrases "David Eather" <eather@tpg.com.au> - 2015-10-18 16:40 +1000
  Re: Entropy Estimations for die and pass phrases  "David Eather" <eather@tpg.com.au> - 2015-10-18 16:41 +1000
  Re: Entropy Estimations for die and pass phrases Karl-Uwe Frank <karl.frank@freecx.co.uk> - 2015-10-18 23:22 +0200
    Re: Entropy Estimations for die and pass phrases Paulo Marques <pmarques@grupopie.com> - 2015-10-19 15:24 +0100
  Re: Entropy Estimations for die and pass phrases Jeffrey Goldberg <nobody@goldmark.org> - 2015-10-19 00:17 -0500
    Re: Entropy Estimations for die and pass phrases rpw3@rpw3.org (Rob Warnock) - 2015-10-19 12:00 +0000
      Re: Entropy Estimations for die and pass phrases Jeffrey Goldberg <nobody@goldmark.org> - 2015-10-19 14:52 -0500
        Re: Entropy Estimations for die and pass phrases David Malone <dwmalone@walton.maths.tcd.ie> - 2015-10-20 08:00 +0000
          Re: Entropy Estimations for die and pass phrases Jeffrey Goldberg <nobody@goldmark.org> - 2015-10-20 12:32 -0500

csiph-web