Computing entropy for a passphrase ( minimal word length ... )

Question

Edit: 2013-05-17 . 2013-05-27

After reading first answer from Tom Leek and some docs around the web, I've begin to write some options to my tool genpassphrase.pl:

$ ./genpassphrase.pl -h
Usage: genpassphrase.pl [-h] [-d dict file] [-i mIn length] [-a mAx length]
   [-e entropy bits] [-r random file] [-w words] [-l lines] [lines]
Version: passphrase.pl v1.3 - (2013-05-12 10:43:14).
    -h           This help.
    -l num       number of phrases to generate  (default: 1)
    -w num       number of words by phrase  (default: 5)
    -e bits      Entropy bits for each words (default: 15)
    -d filename  Dictionary file (default: /usr/share/dict/american-english)
    -i length    Minimal word length (default: 4)
    -a length    Maximal word length (default: 11)
    -r device    Random file or generator (default: /dev/urandom)

The default output look like:

With 5 words over 32768 (     15 entropy bits ) = 1/3.777893e+22 -> 75 bits.
With 5 words from 56947 ( 15.797 entropy bits ) = 1/5.988999e+23 -> 78.987 bits.
  3.736 206.819 foggier     enforced    albatrosses loftiest    foursquare  

First line show count of uniq word found in dictionary, dropped down to 2^Entropy. Second line show initial count of uniq word, and compute theorical entropy based on this.

Each output lines begin with two values, The first is the Shanon's entropy, I'm not clear aboot the meaning and usage of this. The second is based on number of character in the whole line, whith 1/26 for each of them.

Computing entropy reduction

The answer from David Cary confirm that this calcul is very approximative and difficult to represent, but give some good evaluations and a way of thinking:

I think that reducing all value may make some light on my question:

$ ./genpassphrase.pl -i 1 -a 1 -l 4
Warning: Bunch of 26 words too small! Entropy bits dropped down to 4 bits index.
With 5 words over 16 (      4 entropy bits ) = 1/1.048576e+06 -> 20 bits.
With 5 words from 26 (  4.700 entropy bits ) = 1/1.188138e+07 -> 23.502 bits.
  2.322  23.502     f           r           h           j           u           
  1.922  23.502     t           f           g           e           f           
  1.922  23.502     r           k           i           y           r           
  2.322  23.502     y           u           x           f           i           

This make more easy to represent how human selection on this would reduce entropy: For sample if I dislike one, two or upto 10 letters, the final entropy of 4 bits, based on 26 letters is still maintened...

So by extension, if over a bunch of 56947 word, I won't exclude more than 24179 words, the final entropy of 15bit/word is still maintened, but while:

$ ./genpassphrase.pl -a 8
With 5 words over 32768 (     15 entropy bits ) = 1/3.777893e+22 -> 75 bits.
With 5 words from 34954 ( 15.093 entropy bits ) = 1/5.217764e+22 -> 75.466 bits.
  3.397 159.815 corded      boosts      hatters     overhear    rabbles     

If the human won't choose, for sample word longer than character, the number of word to exclude will go down to 2186. Worst: If human refuse to use word longer than 7 character (with my personal dict file), this will drop overall entropy:

$ ./genpassphrase.pl -a 7
Warning: Bunch of 24366 words too small! Entropy bits dropped down to 14 bits index.
With 5 words over 16384 (     14 entropy bits ) = 1/1.180592e+21 -> 70 bits.
With 5 words from 24366 ( 14.573 entropy bits ) = 1/8.588577e+21 -> 72.863 bits.
  3.923 141.013 nitpick     buglers     loaders     arms        promo       

to 70 bits (maybe 72.8 bits??), instead of 75.

From there...

I would like to finalise this tool with some light docs and recommendations.

Original post

After some search for a tool that generate random pass phrases, I've initiate my own...

Take already present dictionary on my desk: /usr/share/dict/american-english and see:

wc -l /usr/share/dict/american-english
98569

After a quick look, I see many 's termination and names that begin with a capitalized letter.

sed -ne '/^[a-z]\{4,99\}$/p' /usr/share/dict/american-english | wc -l
63469

Oh, there is less than 65536, As I can't read only 15.953bit, I will drop this down to 15bits index (using pseudo random as this could be sufficient for now.).

Than with 5 words, I could compute a 75 bits passphrase:

#!/usr/bin/perl -w
use strict;

open my $fh, "</usr/share/dict/american-english" or die;
my @words = map { chomp $_; $_ } grep { /^[a-z]{4,11}$/ } <$fh>;
close $fh;

while (scalar @words > 32768 ) {
    my $rndIdx=int( rand(1) * scalar @words );
    splice @words, $rndIdx, 1 if $words[$rndIdx]=~/s$/ || int(rand()*3)==2;
}

open $fh, "</dev/random" or die;
$_='';
do { sysread $fh, my $buff, 10; $_.=$buff; } while 10 > length;
$_ = unpack "B80", $_;

s/([01]{15})/print "  ".$words[unpack("s",pack("b15",$1))]/eg;
print "\n";

This could produce output like:

  value  nationally  blacktopped  prettify  celebration

From there, I have 3 questions:

.1 What's minimal length for one word? Is 4 chars sufficient? How to compute entropy for a 4 letter word?

In plain alphabet a letter is 1/26 -> 4.7bits, but the following letter is generaly a vowel so 1/6 -> 2.5bits!?

If I'm right, a 4 letter word could not represent more than 14.57bits??

.2 Some could try to run this several time to obtain some choice:

for i in {1..6};do ./gen_pass_phrase.pl ; done
  commons  tweaking  inhered  driveways  sedately
  pantheon  appeaser  inmate  quantifiers  pyrite
  loopier  cloistering  asceticism  auctions  table
  value  nationally  blacktopped  prettify  celebration
  fainer  arthritis  deplete  vestry  fostering
  deuterium  junipers  luckless  burro  harmonic

and choose in this bunch 5 words with is human sensibiliy:

commons  value  fainer  quantifiers  celebration

This will reduce entropy in that:

sexy words would have more chance to be choosed.

But I can't represent this by numeral argumentation.

.3 From the while I play with, I realize that 1/3 words are plurals:

sed -ne '/^[a-z]\{4,9\}$/p' /usr/share/dict/american-english | wc -l
 44476
sed -ne '/^[a-z]\{3,8\}s$/p' /usr/share/dict/american-english | wc -l
 13408

I've tried to compensate them when removing excedent words, as I think to drop every s terminated words is not a good idea too so I remove exedent while s terminated or rand 1/3.

In fine.

The maximum of 75bits of entropy, seem dropped down with this method, but I don't represent how to demonstrate them nor how to compute them.

Answer 1

Entropy is a measure of the password generation process. Suppose that you have a list of 32768 words to choose from. You select 5 words randomly and uniformly from that list (the words are chosen independently of each other, so you might get twice the same). Then you have exactly 75 bits of entropy. Your password generation process can result in precisely 2⁷⁵ distinct passphrases which all have exactly the same probability of being selected. That's 75 bits of entropy, without any ambiguity.

That some words are short and others are long, or some are plurals, or some are sexier than others, has no influence whatsoever on your entropy. Entropy is a property of the generation process, and your generation process pays no attention to the length or sexiness of words. Average human users, when left to their own meat-based devices (their brains), tend to select some words more often than others; they are bad at uniform randomness. For them, computing the actual "entropy" is hard because we don't really know how biased they are. But this has no bearing on your generator, which does not use a brain, but /dev/random. /dev/random does not find some words more attractive than others; its tastes are simpler.

(Speaking of which, you should use /dev/urandom, not /dev/random. See this.)

Answer 2

As Tom Leek correctly noted, entropy is a property of the generation process; it's not a property of any particular passphrase generated by the process.

What's minimal length for one word? Is 4 chars sufficient? How to compute entropy for a 4 letter word?

When you pull 15 bits from a random number generator, and use those bits to uniformly select one of 2^15 unique words from a dictionary, every word has exactly 15 bits of entropy -- it doesn't matter how many characters long it is.

Yes, using a dictionary that only has 4-letter English words would result in passphrases with less than 15 bits of entropy per 4-letter word -- that's another way of saying there are less than 2^15 words that are 4 letters long in a English dictionary. But that's irrelevant in this case -- there's no reason to arbitrarily exclude short words from your dictionary.

Likewise, there are less than 2^15 words that start with "be" in an English dictionary -- so words that start with "be" have less than 15 bits of entropy per word. Likewise, that fact is irrelevant -- there's no reason to arbitrarily exclude words starting with "be" from your dictionary.

... run this several time to obtain some choice: ... and choose in this bunch 5 words with is human ... This will reduce entropy ...

Yes, if you let a human reject some words, then it will reduce entropy.

One way to estimate this is to assume that there is some "real" list of words that the human will accept, and he will reject all others. If that list has only 2^N bits, then each word in the actual human-selected password will have (at best) only N bits of entropy per word. Alas, it is difficult to find out what "N" really is.

Sometimes the reason humans reject certain words is because they don't know how to spell them. One way to avoid this involves a much shorter dictionary that only includes common, easy-to-spell words. For example, compared to the best case of 15 bits/word * 5 words = 75 bits, you get slightly more entropy (77 bits) by uniformly picking 7 words from a much shorter dictionary of 2^11 common words, such as the the S/Key 2048-word dictionary.

Perhaps a better option is for the computer to pick 5-word passphrases as an all-or-nothing list. If you show your user 8 such passphrases, and force the user to pick one of those 8 passphrases (rather than mixing-and-matching any 5 words from a list of 30 words), it can be shown that: In the worst case it reduces the strength of the selected passphrase by 3 bits (to 72 bits). In the best cases (the user always picks the first one, or the user uses 3 fair coin-flips to choose one of the 8), the strength of the selected passphrase is the full entropy of 15 bits * 5 words = 75 bits.

1/3 words are plurals

As long as each word in your dictionary of 2^15 words is unique and uniformly chosen, it is irrelevant whether it is plural. As in the above "be" case, there is no reason to arbitrarily exclude words ending in "s" from your dictionary.

(And I doubt that 1/3 of the words are really true plurals -- your quick test catches words like "abacus" and "bus" and "boss" that are not true plurals).

• What is your way to create good passwords that can actually be remembered?
• How should I make diceware passphrases more memorable?
• An alternative to traditional passwords: is there some merit to this idea?