Entropia entropica per una passphrase (lunghezza minima delle parole ...)

Modifica: 2013-05-17. 2013/5/27

Dopo aver letto la prima risposta di Tom Leek e alcuni documenti sul Web, ho iniziato a scrivere alcune opzioni sul mio strumento 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)

L'output di default assomiglia a:

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  

Primo numero di visualizzazioni della parola uniq trovata nel dizionario, ridotte a 2^Entropy . La seconda riga mostra il conteggio iniziale della parola uniq e calcola l'entropia teorica in base a questo.

Ogni linea di uscita inizia con due valori, la prima è l'entropia di Shanon , non sono chiara per quanto riguarda il significato e l'utilizzo di questa. Il secondo è basato sul numero di caratteri nell'intera linea, con 1/26 per ciascuno di essi.

Riduzione dell'entropia informatica

La risposta di David Cary conferma che questo calcolo è molto approssimativo e difficile da rappresentare, ma fornisce alcune buone valutazioni e un modo di pensare:

Penso che ridurre tutto il valore possa far luce sulla mia domanda:

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

Questo rende più facile rappresentare come la selezione umana su questo ridurrebbe l'entropia: per esempio se non mi piacciono le lettere da uno, due o fino a 10, l'entropia finale di 4 bit, basata su 26 lettere è ancora mantenuta ...

Quindi per estensione, se su un gruppo di 56947 parole, non escluderò più di 24179 parole, l'entropia finale di 15 bit / parola è ancora mantenuta, ma mentre:

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

Se l'umano non sceglierà, per parole campione più lunghe del carattere, il numero di parole da escludere passerà al 2186. Peggiore: se l'uomo rifiuta di usare parole più lunghe di 7 caratteri (con il mio file personale), questo diminuirà l'entropia complessiva:

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

a 70 bit (forse 72,8 bit ??), invece di 75.

Da lì ...

Vorrei finalizzare questo strumento con alcuni documenti e raccomandazioni chiari.

Post originale

Dopo aver cercato uno strumento che genera frasi a caso, ho iniziato il mio ...

Prendi il dizionario già presente sulla mia scrivania: /usr/share/dict/american-english e vedi:

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

Dopo una rapida occhiata, vedo molti termini di terminazione 's e nomi che iniziano con una lettera maiuscola.

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

Oh, c'è meno di 65536, dato che non posso leggere solo 15.953 bit, lo farò scendere all'indice di 15 bit (usando pseudo random come potrebbe essere sufficiente per ora.)

Che con 5 parole, ho potuto calcolare una passphrase a 75 bit:

#!/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";

Questo potrebbe produrre un output come:

  value  nationally  blacktopped  prettify  celebration

Da lì, ho 3 domande:

.1 Qual è la lunghezza minima per una parola? 4 caratteri sono sufficienti? Come calcolare l'entropia per una parola di 4 lettere?

In alfabeto semplice una lettera è 1/26 - > 4.7bits, ma la lettera seguente è generalmente una vocale così 1/6 - > 2.5bits!?

Se ho ragione, una parola di 4 lettere non può rappresentare più di 14.57 bit ??

.2 Alcuni potrebbero provare a eseguirlo più volte per ottenere una scelta:

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

e scegli in questo gruppo 5 parole con humanisciy :

commons  value  fainer  quantifiers  celebration

Questo ridurrà entropy in questo:

sexy words would have more chance to be choosed.

Ma non posso rappresentarlo con l'argomentazione numerica.

.3 Dal momento in cui gioco, mi rendo conto che 1/3 parole sono plurali:

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

Ho provato a compensarli quando rimuovendo le parole che escono, poiché penso che eliminare tutte le parole terminate con s non sia una buona idea, quindi rimuovo exedent mentre s terminato o rand 1/3.

In fine.

Il massimo di 75 bit di entropia, sembra abbandonato con questo metodo, ma non rappresento come dimostrarlo né come calcolarli.