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.