Computar la entropía para una frase de contraseña (longitud de palabra mínima ...)

4

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

Después de leer la primera respuesta de Tom Leek y algunos documentos en la web, comienzo a escribir algunas opciones en mi herramienta 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)

La salida predeterminada se ve así:

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  

La primera línea muestra el recuento de la palabra uniq que se encuentra en el diccionario, se redujo a 2^Entropy . La segunda línea muestra el recuento inicial de palabras uniq y calcula la entropía teórica basada en esto.

Cada línea de salida comienza con dos valores, el primero es la entropía de Shanon , no tengo claro el significado y el uso de esto. El segundo se basa en el número de caracteres en toda la línea, con 1/26 para cada uno de ellos.

Reducción de la entropía informática

La respuesta de David Cary confirma que este cálculo es muy aproximado y difícil de representar, pero ofrece algunas buenas evaluaciones y una forma de pensar:

Creo que reducir todo el valor puede aclarar mi pregunta:

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

Esto hace que sea más fácil representar cómo la selección humana en esto reduciría la entropía: Para muestra si no me gustan una, dos o hasta 10 letras, la entropía final de 4 bits, basada en 26 letras, aún se mantiene ...

Entonces, por extensión, si sobre una cantidad de 56947 palabras, no excluiré más de 24179 palabras, la entropía final de 15 bits / palabra todavía se mantiene, pero mientras:

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

Si el humano no elige, para la palabra de muestra más larga que el carácter, el número de palabra que se excluirá se reducirá a 2186. Peor: si el humano se niega a usar la palabra con más de 7 caracteres (con mi archivo de dictado personal), esto reducirá la entropía general:

$ ./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 bits (¿tal vez 72.8 bits ??), en lugar de 75.

Desde allí ...

Me gustaría finalizar esta herramienta con algunos documentos y recomendaciones ligeros.

Publicación original

Después de buscar algo para una herramienta que genera frases de paso aleatorias, he iniciado mi propia ...

Tomar el diccionario ya presente en mi escritorio: /usr/share/dict/american-english y ver:

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

Después de un vistazo rápido, veo muchos 's terminación y nombres que comienzan con una letra mayúscula.

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

Oh, hay menos de 65536, ya que no puedo leer solo 15.953 bits, caeré a un índice de 15 bits (usando pseudoaleatorio, ya que esto podría ser suficiente por ahora).

Con 5 palabras, podría calcular una frase de contraseña de 75 bits:

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

Esto podría producir una salida como:

  value  nationally  blacktopped  prettify  celebration

A partir de ahí, tengo 3 preguntas:

.1 ¿Cuál es la longitud mínima para una palabra? ¿Es suficiente 4 caracteres? ¿Cómo calcular la entropía para una palabra de 4 letras?

En el alfabeto llano, una letra es 1/26 - > 4.7bits, pero la siguiente letra es generalmente una vocal, por lo que 1/6 - > 2.5bits !?

Si tengo razón, ¿una palabra de 4 letras no puede representar más de 14.57 bits?

.2 Algunos podrían intentar ejecutar esto varias veces para obtener alguna opción:

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

y elija en este grupo 5 palabras con sensibilidad humana :

commons  value  fainer  quantifiers  celebration

Esto reducirá entropía en eso:

  

las palabras sexys tendrían más posibilidades de ser elegidas.

Pero no puedo representar esto mediante una argumentación numérica.

.3 Desde que juego, me doy cuenta de que 1/3 de las palabras son plurales:

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

Traté de compensarlos al eliminar las palabras que faltan, ya que creo que eliminar cada s palabras terminadas tampoco es una buena idea, así que elimino exedent mientras que s terminó o rand 1/3.

En bien.

El máximo de 75 bits de entropía parece haberse reducido con este método, pero no represento cómo demostrarlos ni cómo calcularlos.

    
pregunta F. Hauri 07.04.2013 - 21:37
fuente

2 respuestas

11

La entropía es una medida del proceso de generación de contraseña. Supongamos que tiene una lista de 32768 palabras para elegir. Seleccionas 5 palabras al azar y de manera uniforme de esa lista (las palabras se eligen de forma independiente, por lo que es posible que obtengas el doble). Entonces tienes exactamente 75 bits de entropía . El proceso de generación de su contraseña puede dar como resultado exactamente 2 75 frases de contraseña distintas que tienen exactamente la misma probabilidad de ser seleccionadas. Son 75 bits de entropía, sin ambigüedad alguna.

Que algunas palabras son cortas y otras son largas, o algunas son plurales, o algunas son más atractivas que otras, no tiene influencia alguna en tu entropía. La entropía es una propiedad del proceso de generación, y el proceso de generación de su no presta atención a la longitud o atractivo de las palabras. Los usuarios humanos promedio , cuando se los deja a sus propios dispositivos basados en carne (sus cerebros), tienden a seleccionar algunas palabras con más frecuencia que otras; son malos en la aleatoriedad uniforme. Para ellos , calcular la "entropía" real es difícil porque realmente no sabemos qué tan sesgados son. Pero esto no tiene relación con su generador, que no usa un cerebro, pero /dev/random . /dev/random no encuentra algunas palabras más atractivas que otras; Sus gustos son más sencillos.

(Hablando de eso, debe usar /dev/urandom , no /dev/random . Ver this .)

    
respondido por el Tom Leek 07.04.2013 - 21:52
fuente
3

Como Tom Leek señaló correctamente, la entropía es una propiedad del proceso de generación; no es una propiedad de ninguna frase de contraseña en particular generada por el proceso.

  

¿Cuál es la longitud mínima para una palabra? ¿Es suficiente 4 caracteres? Cómo   ¿Calcular la entropía para una palabra de 4 letras?

Cuando extrae 15 bits de un generador de números aleatorios, y utiliza esos bits para seleccionar de manera uniforme una de 2 ^ 15 palabras únicas de un diccionario, cada palabra tiene exactamente 15 bits de entropía. no importa la cantidad de caracteres que sea.

Sí, usar un diccionario que solo tenga palabras en inglés de 4 letras daría como resultado frases de contraseña con menos de 15 bits de entropía por palabra de 4 letras; esa es otra forma de decir que hay menos de 2 ^ 15 palabras de 4 letras en un diccionario de inglés. Pero eso es irrelevante en este caso, no hay razón para excluir arbitrariamente palabras cortas de su diccionario.

Del mismo modo, hay menos de 2 ^ 15 palabras que comienzan con "be" en un diccionario de inglés, por lo que las palabras que comienzan con "be" tienen menos de 15 bits de entropía por palabra. Del mismo modo, ese hecho es irrelevante: no hay razón para excluir arbitrariamente de su diccionario las palabras que comienzan con "ser".

  

... ejecute esto varias veces para obtener alguna opción:   ... y elige en este grupo 5 palabras con es humano   ... Esto reducirá la entropía ...

Sí, si permites que un humano rechace algunas palabras, se reducirá la entropía.

Una forma de estimar esto es asumir que hay una lista "real" de palabras que el humano aceptará, y rechazará todas las demás. Si esa lista tiene solo 2 ^ N bits, entonces cada palabra en la contraseña seleccionada por el ser humano tendrá (en el mejor de los casos) solo N bits de entropía por palabra. Por desgracia, es difícil descubrir qué es realmente la "N".

A veces la razón por la que los humanos rechazan ciertas palabras es porque no saben cómo deletrearlas. Una forma de evitar esto implica un diccionario mucho más corto que solo incluya palabras comunes y fáciles de deletrear. Por ejemplo, comparado con el mejor caso de 15 bits / palabra * 5 palabras = 75 bits, obtienes un poco más de entropía (77 bits) al seleccionar de manera uniforme 7 palabras de un diccionario mucho más corto de 2 ^ 11 palabras comunes, como el S / Key diccionario de 2048 palabras.

Quizás una mejor opción es que la computadora elija frases de contraseña de 5 palabras como una lista de todo o nada. Si le muestra a su usuario 8 frases de contraseña de este tipo y lo obliga a elegir una de esas 8 frases de contraseña (en lugar de mezclar y combinar 5 palabras de una lista de 30 palabras), se puede mostrar que: En el peor de los casos reduce la fuerza de la frase de contraseña seleccionada en 3 bits (a 72 bits). En el mejor de los casos (el usuario siempre elige el primero, o el usuario usa 3 tiros de moneda normales para elegir uno de los 8), la fuerza de la frase de contraseña seleccionada es la entropía completa de 15 bits * 5 palabras = 75 bits.

  

1/3 palabras son plurales

Siempre que cada palabra en su diccionario de 2 ^ 15 palabras sea única y sea elegida de manera uniforme, es irrelevante si es plural. Como en el caso anterior de "be", no hay razón para excluir arbitrariamente las palabras que terminan en "s" de su diccionario.

(Y dudo que 1/3 de las palabras sean realmente plurales verdaderos - su prueba rápida detecta palabras como "ábaco" y "bus" y "jefe" que no son plurales verdaderos).

respondido por el David Cary 13.05.2013 - 19:30
fuente

Lea otras preguntas en las etiquetas