The Passcode Designer Entropy Calculation

The Passcode Designer Entropy Question


Set Name    Characters   Entropy per
             in the Set   Character

Set Changes      4        2.00000

Other Char.     33        5.04439
Upper Case      26        4.70044
Lower Case      26        4.70044
Numbers         10        3.32193

Characters      95        6.56986


14 character 12 Star passcode with set changes.

  Set       Number     Bits of       Number of       Probability for
                       Entropy    Unique passcodes   a given passcode
Other         3       15.13317
Upper         4       18.80176
Lower         4       18.80176
Numbers       3        9.96579

Total        14       62.70248

Set Changes  12       24.00000

Total                 86.70248  =  1.25906 E+26      7.94241 E-27


14 character passcode from a single 95 character set.

Set        Number     Bits of
                       Entropy
Characters   14       91.97804

Total                 91.97804  =  4.87696 E+27      2.05046 E-28


Entropy per character is calculated by:

Binary Entropy = log(N)/log(2)  Where N is the number of states in 
the set and the states have equal probability.

The set change entropy almost made up for the difference in procedure.

Basic information courtesy of Mark Cross.
Gerry

0

Gerry 5/17/2011 12:16:09 AM

Gerry wrote:
        The Passcode Designer Entropy Question (revised)

Set Name    Characters   Entropy per
             in the Set   Character

Sets             4        2.00000

Other Char.     33        5.04439
Upper Case      26        4.70044
Lower Case      26        4.70044
Numbers         10        3.32193

Characters      95        6.56986

*********
14 character passcode with set changes.

  Set       Number     Bits of       Number of       Probability for
                       Entropy    Unique passcodes   a given passcode
Other         3       15.13317
Upper         4       18.80176
Lower         4       18.80176
Numbers       3        9.96579

Total        14       62.70248

   Set        14       28.00000
selection

Total                 90.70248  =  2.01450 E+27      4.96401 E-28

*********
14 character passcode from a single 95 character set.

Set        Number     Bits of
                       Entropy
Characters   14       91.97804

Total                 91.97804  =  4.87696 E+27      2.05046 E-28


I have decided that each character selected receives the 2 bit entropy
because it is a 1 of 4 selection.  This brings the total bit entropy
of each case quite close.  I believe that the variation is probably 
due to the uneven distribution of the characters in the 4 sets.

Probably the users unevenness of selection will cause greater 
differences.

Gerry

0

Gerry 5/17/2011 5:23:49 PM

On 05/17/2011 11:23 AM, Gerry wrote:
> [...]
> 
> I have decided that each character selected receives the 2 bit entropy
> because it is a 1 of 4 selection.  This brings the total bit entropy
> of each case quite close.  I believe that the variation is probably due
> to the uneven distribution of the characters in the 4 sets.

There are four options but for each of the four options there are many
possibilities.

lowercase alpha = log(26)/log(2)
upper = log(26)/log(2)
decimal = log(10)/log(2)
symbols = log(94 - 10 - 26 - 26)/log(2)

So it would be

A = # of upper case alpha
a = # of lower case alpha
d = # of digits
s = # of symbols
c = total # of characters

entropy =
4.70043972 * A + 4.70043972 * a + 3.32192809 * d + 5 * s

(the decimals are just the computed logarithms above)

The stars and exclamation mark system will help users create a memorable
password that is close to the ideal log_2(94^c) as if the characters
were purely random.

-- 
FireXware
WWW:     http://ossbox.com/     http://crackstation.net/
When cryptography is outlawed, bayl bhgynjf jvyy unir cevinpl.

0

FireXware 5/18/2011 4:30:09 AM

FireXware wrote:
> On 05/17/2011 11:23 AM, Gerry wrote:
>> [...]
>>
>> I have decided that each character selected receives the 2 bit entropy
>> because it is a 1 of 4 selection.  This brings the total bit entropy
>> of each case quite close.  I believe that the variation is probably due
>> to the uneven distribution of the characters in the 4 sets.
> 
> There are four options but for each of the four options there are many
> possibilities.
> 
> lowercase alpha = log(26)/log(2)
> upper = log(26)/log(2)
> decimal = log(10)/log(2)
> symbols = log(94 - 10 - 26 - 26)/log(2)
> 
> So it would be
> 
> A = # of upper case alpha
> a = # of lower case alpha
> d = # of digits
> s = # of symbols
> c = total # of characters
> 
> entropy =
> 4.70043972 * A + 4.70043972 * a + 3.32192809 * d + 5 * s
> 
> (the decimals are just the computed logarithms above)

I agree with the above except point out that s = 33 for my example. 
But I must insist that when you choose one of the octagons and press 
it you are actually doing two things.  You are choosing one of the 
four sets (2 bits of entropy) and also selecting a random member 
from that set of characters (4.70044 bits of entropy for lower case 
letters), at the same time. This happens for each character that is 
added to the password even if it is in the same set as the last 
character.  The added 2 bits of entropy for each character in the 
passcode makes the total entropy almost identical to the single set 
example for the same number of characters.

> 
> The stars and exclamation mark system will help users create a memorable
> password that is close to the ideal log_2(94^c) as if the characters
> were purely random.
>

I agree that the red marks and Stars are simply social engineering 
to help the user use the diverse sets of characters.  (2^total entropy)

Gerry

0

Gerry 5/18/2011 8:09:12 AM

FireXware wrote:

> symbols = log(94 - 10 - 26 - 26)/log(2)

Why 94?

Well, I assume that you are thinking about the very limited set of ASCII 
characters in the lower part (no sign bit set) of an octet. And also the 
very limited view of English-American text:

       ! " # $ % & ' ( ) * + , - . /
     0 1 2 3 4 5 6 7 8 9 : ; < = > ?
     @ A B C D E F G H I J K L M N O
     P Q R S T U V W X Y Z [ \ ] ^ _
     ` a b c d e f g h i j k l m n o
     p q r s t u v w x y z { | } ~ 


But, anyway, in such case, the count should be 95:
   128
 -  32 control chars (not printable)
 -   1 Backspace or character number 127 (dec).
 =  95

That makes the count something like this:
 +  26 lower case English letters »»abcdefghijklmnopqrstuvwxyz««
 +  26 Upper case English letters »»ABCDEFGHIJKLMNOPQRSTUVWXYZ««
 +  10 English numerals.          »»0123456789««
 +  33 ASCII symbols              »» !"#$%&'()*+,-./:;<=>?@[\]^_`{|}~««

There are, however, a lot of other symbols used in languages different than 
English. Those range from the simple accented chars (diacritical marks) like 
Ã¨ or Ã© used in Spanish, French, Italian, to the more specific chars of 
German Ã Portuguese Ã§Ã, Swedish or Finnish Ã¦Ã, not to name Russian 
(Cyrillic) Ð´ÑÐµÓÑÐ¶ÓÓÐ· Japaneese ã©ãã¯ãªã äºè¼ªä»£è¡¨ä¸ or Chinese ç¶²/ç½è½æ³¨/è½¬æ³¨

The page accepts things like any of those (just copy the next line into the 
page, even if you are not able to see each of the characters):

  Ã¨Ã©ÃÃ§ÃÃ±Ã¦Ã ÐÐÐÐÐÐÐÐÑ² Ð´ÑÐµÓÑÐ¶ÓÓÐ· ã©ãã¯ãªã äºè¼ªä»£è¡¨ä¸ ç¶²/ç½è½æ³¨/è½¬æ³¨

Even if, I am pretty sure Steve have not intended to include such big list 
of all extended chars into the page (he specified the simpler iso-8859-1 
charset) none the less all work and are processed correctly in Javascript.

So, the count for "Any Other Symbols" in that page is more in-the-order of 
"thousands" than the simple ASCII count of 33.

-- 
Mark Cross @ 05/18/2011 12:07 p.m.
If Linux doesn't have the solution, you have the wrong problem.

0

Mark 5/18/2011 4:09:45 PM

While Mark Cross dreams of electric sheep...:

> The page accepts things like any of those (just copy the next 
> line into the page, even if you are not able to see each of the 
> characters):
> 
> Ã¨Ã©ÃÅ¸Ã§Ã¡Ã±Ã¦Ã  ÃÃÃÃÃ¢Ã¦ÃÃËÃ² Ã´ÃÃµÃÃÃ¶ÃÃÃ· 
> Ã£Æ©Ã£Æ°Ã£¯Ã£ÆªÃ£Æ¢ Ã¤ºÃ¨¼ªÃ¤»£Ã¨¡¨Ã¤¸¡ Ã§¶²/Ã§½Ã¨½°Ã¦³¨/Ã¨½¬Ã¦³¨

On a fluke I copied that into the link from the following thread
about how secure is the password and came back:
[quote]
It would take

About 26 googol years

for a desktop PC to crack your password
[/quote]

But looks like only the first 16 characters are tested.
Unfortunately I can't see any stars or exclaims on my setup for some
reason (See PD update thread). How good does this password look in PD ?
-- 
Where's there's smoke, There are mirrors.
Give me Free as in Freedom not Speech or Beer.
Thank You and Welcome to the Internet.

0

DarkWolf 5/18/2011 5:40:09 PM

On 05/17/2011 10:30 PM, FireXware wrote:
> entropy =
> 4.70043972 * A + 4.70043972 * a + 3.32192809 * d + 5 * s

Actually, that doesn't account for the order of the characters, so it's
actually more.

If the user's selection of "character sets" is truly random, then the
entropy of the passcode will be the same as if it were randomly chosen
from the full printable ASCII set.

If we assume that the user will not choose randomly (an attacker can
predict exactly which character sets the user selected) then it becomes

c = # of characters

entropy = ideal - 2*c

-- 
FireXware
WWW:     http://ossbox.com/     http://crackstation.net/
When cryptography is outlawed, bayl bhgynjf jvyy unir cevinpl.

0

FireXware 5/18/2011 11:12:14 PM

On 05/18/2011 10:09 AM, Mark Cross wrote:
> But, anyway, in such case, the count should be 95:
>    128
>  -  32 control chars (not printable)
>  -   1 Backspace or character number 127 (dec).
>  =  95
> 

Right but I didn't count the spacebar because it's not in any of the
categories in Steve's app.

-- 
FireXware
WWW:     http://ossbox.com/     http://crackstation.net/
When cryptography is outlawed, bayl bhgynjf jvyy unir cevinpl.

0

FireXware 5/18/2011 11:15:45 PM