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

Groups > sci.crypt > #33028 > unrolled thread

Entropy Estimations for die and pass phrases

Back to article view | Back to sci.crypt

Contents

  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

#33028 — Entropy Estimations for die and pass phrases

Just a short table of entropy estimates (Shannon entropy for the purest  
hair splitters)

6 sided dice 2.58 bits per throw
8 sided dice 3.99 bits per throw
10 dided dice 3.32 bits per throw
Letters from a Scrabble set 4.32 bits per tile (this is higher because the  
distribution of letters is a little more even than in natural language  
because some letter must have one tile even though they represent less  
than 1% of language)

Making a password from the first letter of every word in a pass-phrase  
yield about 3.9 - 4.0 bits per letter.

However, Professor Unruh has mentioned his experiments with all lower case  
words taken from his texts which yielded 4.1 bits per word. This accords  
very well with the Scrabble result and leads me to conclude that although  
the difference is relatively small there is no reason to use mixed cases  
when and only when) making a pass phrase from the first letter of words in  
a sentence.

[toc] | [next] | [standalone]

#33029

On Sun, 18 Oct 2015 12:05:41 +1000, "David Eather" <eather@tpg.com.au>
wrote:

>Just a short table of entropy estimates (Shannon entropy for the purest  
>hair splitters)
>
>6 sided dice 2.58 bits per throw
>8 sided dice 3.99 bits per throw


Eh?  3.00 bits per throw?


>10 dided dice 3.32 bits per throw
>Letters from a Scrabble set 4.32 bits per tile (this is higher because the  
>distribution of letters is a little more even than in natural language  
>because some letter must have one tile even though they represent less  
>than 1% of language)
>
>Making a password from the first letter of every word in a pass-phrase  
>yield about 3.9 - 4.0 bits per letter.
>
>However, Professor Unruh has mentioned his experiments with all lower case  
>words taken from his texts which yielded 4.1 bits per word. This accords  
>very well with the Scrabble result and leads me to conclude that although  
>the difference is relatively small there is no reason to use mixed cases  
>when and only when) making a pass phrase from the first letter of words in  
>a sentence.

[toc] | [prev] | [next] | [standalone]

#33033

On Sun, 18 Oct 2015 15:14:43 +1000, Robert Wessel  
<robertwessel2@yahoo.com> wrote:

> On Sun, 18 Oct 2015 12:05:41 +1000, "David Eather" <eather@tpg.com.au>
> wrote:
>
>> Just a short table of entropy estimates (Shannon entropy for the purest
>> hair splitters)
>>
>> 6 sided dice 2.58 bits per throw
>> 8 sided dice 3.99 bits per throw
>
>
> Eh?  3.00 bits per throw?

yep typo


>
>
>> 10 dided dice 3.32 bits per throw
>> Letters from a Scrabble set 4.32 bits per tile (this is higher because  
>> the
>> distribution of letters is a little more even than in natural language
>> because some letter must have one tile even though they represent less
>> than 1% of language)
>>
>> Making a password from the first letter of every word in a pass-phrase
>> yield about 3.9 - 4.0 bits per letter.
>>
>> However, Professor Unruh has mentioned his experiments with all lower  
>> case
>> words taken from his texts which yielded 4.1 bits per word. This accords
>> very well with the Scrabble result and leads me to conclude that  
>> although
>> the difference is relatively small there is no reason to use mixed cases
>> when and only when) making a pass phrase from the first letter of words  
>> in
>> a sentence.

[toc] | [prev] | [next] | [standalone]

#33034

On Sun, 18 Oct 2015 12:05:41 +1000, David Eather <eather@tpg.com.au> wrote:

> Just a short table of entropy estimates (Shannon entropy for the purest  
> hair splitters)
>
> 6 sided dice 2.58 bits per throw
> 8 sided dice 3.99 bits per throw

                ^^^^ that is 3.00 bits per throw



> 10 dided dice 3.32 bits per throw
> Letters from a Scrabble set 4.32 bits per tile (this is higher because  
> the distribution of letters is a little more even than in natural  
> language because some letter must have one tile even though they  
> represent less than 1% of language)
>
> Making a password from the first letter of every word in a pass-phrase  
> yield about 3.9 - 4.0 bits per letter.
>
> However, Professor Unruh has mentioned his experiments with all lower  
> case words taken from his texts which yielded 4.1 bits per word. This  
> accords very well with the Scrabble result and leads me to conclude that  
> although the difference is relatively small there is no reason to use  
> mixed cases when and only when) making a pass phrase from the first  
> letter of words in a sentence.

[toc] | [prev] | [next] | [standalone]

#33051

On 18.10.15 04:05, David Eather wrote:
> Just a short table of entropy estimates (Shannon entropy for the purest
> hair splitters)
>
> 6 sided dice 2.58 bits per throw
> 8 sided dice 3.99 bits per throw
> 10 dided dice 3.32 bits per throw
>
How about using a 16 side hex dice and drawing a 128 bit result as 
keyword? This way one can use the full range of all 256 chars of the 
ASCII set.

https://mccormick.cx/news/entries/3d-printable-sixteen-sided-hexadecimal-die

https://www.thediceshoponline.com/dice/4411/Hexidice-D16-Hexadecimal-Dice

--- news://freenews.netfront.net/ - complaints: news@netfront.net ---

[toc] | [prev] | [next] | [standalone]

#33060

On 18-10-2015 22:22, Karl-Uwe Frank wrote:
> On 18.10.15 04:05, David Eather wrote:
>> Just a short table of entropy estimates (Shannon entropy for the purest
>> hair splitters)
>>
>> 6 sided dice 2.58 bits per throw
>> 8 sided dice 3.99 bits per throw
>> 10 dided dice 3.32 bits per throw
>>
> How about using a 16 side hex dice and drawing a 128 bit result as
> keyword? This way one can use the full range of all 256 chars of the
> ASCII set.
>
> https://mccormick.cx/news/entries/3d-printable-sixteen-sided-hexadecimal-die

This "die" looks awful! It doesn't seem to try to give the same 
probabilities for every symbol at all.

> https://www.thediceshoponline.com/dice/4411/Hexidice-D16-Hexadecimal-Dice

This one seems much, much better.

-- 
Paulo Marques - www.grupopie.com

"You're just jealous because the voices only talk to me."

[toc] | [prev] | [next] | [standalone]

#33054

On 2015-10-18 02:05:41 +0000, 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. Going full Kerchoffs here, the 
attacker knows the distribution and is going to guess the most likely 
first. Note that when a distribution is uniform, min-entropy == Shannon 
entropy, but min-entropy is a better measure when assessing threat.

> 6 sided dice 2.58 bits per throw
> 8 sided dice 3.99 bits per throw
> 10 dided dice 3.32 bits per throw

Right. And if you look at the original Diceware(TM) scheme, it took 
five throws of a 6-sided die to select a word, so 12.92 bits per word.

> Letters from a Scrabble set 4.32 bits per tile (this is higher because 
> the distribution of letters is a little more even than in natural 
> language because some letter must have one tile even though they 
> represent less than 1% of language)

But here is where min-entropy should be used. Assuming Scrabble(TM) 
distribution with replacement, the attacker when going after, say, an 
eight character password should guess "eeeeeeee" and "qqqqqqqq" last. 
So we are looking at 3.06 bits per letter.


> Making a password from the first letter of every word in a pass-phrase 
> yield about 3.9 - 4.0 bits per letter.

Again, it is going to be much lower than that when considering that 
some letters are much more common first letters than others.

> However, Professor Unruh has mentioned his experiments with all lower 
> case words taken from his texts which yielded 4.1 bits per word. This 
> accords very well with the Scrabble result and leads me to conclude 
> that although the difference is relatively small there is no reason to 
> use mixed cases when and only when) making a pass phrase from the first 
> letter of words in a sentence.

Yeah. People will only remember "mixed case" if it is the first letter 
of a meaningful unit or the last letter of the password. So it is only 
a few extra bits, and makes typing on a mobile keyboard harder.

Cheers,

-j

[toc] | [prev] | [next] | [standalone]

#33058

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? By definition, Shannon entropy
already includes weighting by probability of each symbol
in the alphabet [for each "x_i" in {X} there is a "P(x_i)"]:

    H(X) = - Sum_i ( P(x_i)*log_b(P(x_i)) ))  ;"b" usually 2 for crypto.

An unbiased coin flip gives you 1 bit/flip, as expected:

    -( (0.5 * log2(0.5)) + (0.5 * log2(0.5))) => 1

Whereas if you have a *badly* biased coin, say, 99% tails,
it's only ~0.081 bits/flip:

    -( (0.99 * log2(0.99)) + (0.01 * log2(0.01))) => 0.0807931+

You can apply the same weightings to choosing diceware words,
assuming you have a way to compute the weighting of a given word
based on its English statistics. Just make sure your weighting
is unitary! [I.e., the sum of probabilities of all possible
outcomes must add up to 1.]

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


-Rob

-----
Rob Warnock		<rpw3@rpw3.org>
627 26th Avenue		<http://rpw3.org/>
San Mateo, CA 94403

[toc] | [prev] | [next] | [standalone]

#33063

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

[toc] | [prev] | [next] | [standalone]

#33073

Jeffrey Goldberg <nobody@goldmark.org> writes:

>Also remember that Shannon entropy is designed to characterize
>something like the average information content of a message.

I'd say that is was the average number of bits required to
store/transmit a long sequence of words from that random source.

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

I'd agree that Massey's paper was the start of something interesting
here. There are also several interesting papers in between Massey's
and Bonneau's paper - Plaim did some interesting thinking about it
around 2000:

	http://scholar.google.com/citations?user=neO-8uYAAAAJ&hl=en

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

Agreed!

	David.

[toc] | [prev] | [next] | [standalone]

#33085

On 2015-10-20 08:00:12 +0000, David Malone said:

> Jeffrey Goldberg <nobody@goldmark.org> writes:
> 
>> Also remember that Shannon entropy is designed to characterize
>> something like the average information content of a message.
> 
> I'd say that is was the average number of bits required to
> store/transmit a long sequence of words from that random source.

Yep. That's a better way of putting it. I was trying to focus
on the "average".

> I'd agree that Massey's paper was the start of something interesting
> here. There are also several interesting papers in between Massey's
> and Bonneau's paper - Plaim did some interesting thinking about it
> around 2000:
> 
> 	http://scholar.google.com/citations?user=neO-8uYAAAAJ&hl=en

That is one of those things I'm "aware of, but haven't read".

And of course another interesting paper between Massay's and
Bonneau's is


@article{malone2004guesswork,
	Author = {Malone, David and Sullivan, Wayne G},
	Journal = {IEEE Transactions on Information Theory},
	Number = {3},
	Pages = {525--526},
	Title = {Guesswork and entropy},
	Volume = {50},
	Year = {2004}}

One of the things that I am guilty of is not checking out the full
literature before tackling this problem myself. But I would like
to take this opportunity to warn others here of making the same
mistake.

How to characterize the strength of password generation schemes
or distributions is something that has been looked at by a number
of very smart people.

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

I'm not at all surprised.

For those of you not familiar with David Malone, he knows a thing
or two about the distribution of human created passwords. He has
shown that although they might superficially appear to follow a
power-law distribution, when you do the statistics right you will
find that they don't:


@article{MaloneMaher11:CoRR,
	Author = {Malone, David and Maher, Kevin},
	Journal = {CoRR},
	Title = {Investigating the Distribution of Password Choices},
	Volume = {abs/1104.3722},
	Year = {2011}}

(Which reminds me that I really should post my analysis of the Adobe
breach, which is fully consistant with what you've said. Because
Adobe encrypted passwords without salt, we know the distribution
even if we don't know the individual passwords.)

Cheers,

-j

[toc] | [prev] | [standalone]

Back to top | Article view | sci.crypt

csiph-web