¿Hay algún sesgo en esta selección aleatoria de un diccionario?

2

Estoy generando contraseñas seleccionando palabras aleatorias de un diccionario y contando entropy=words_in_passphrase*log(dictionary_size)/log(2) . Este algoritmo supone que las palabras se seleccionarán del diccionario con una distribución uniforme.

Creo que el principio de diseño es sólido, pero no estoy seguro de la implementación. Estoy leyendo de /dev/urandom de bytes suficientes para expresar un índice en el diccionario @words , y convertir esos bytes en un entero de manera algo incómoda.

El código parece para funcionar correctamente, pero ¿hay alguna advertencia a Perl o / dev / urandom que distorsione los resultados? Fuente completa.

my $entropy_per_word = log (@words) / log (2);

my $pw = "";
my $pw_entropy = 0;

# maybe /dev/random ?
open my $random_source, '<', "/dev/urandom" or die "Could not open /dev/urandom";

binmode $random_source or die $!;

my $random_buffer = "";

my $random_bytes = ceil ($entropy_per_word / 8);

die "Tried to read no random bytes." if ($random_bytes < 1);

while ($pw_entropy < $entropy)
{
    die "Could not read random bytes"
    if ($random_bytes !=
        read ($random_source, $random_buffer, $random_bytes));

    my @bytes = unpack 'C ' x $random_bytes, $random_buffer;

    my $n = 0;

    foreach (@bytes)
    {
        $n *= 256;
        $n += $_ * 1;
    }

    next if ($n >= @words); # don't use %, it will bias the randomness

    $pw .= ' ' if ("" ne $pw);

    foreach (split //, $words[$n])
    {
        # sprinkle some capitalization for good measure
        $_ = uc if (rand > 0.8);

        $pw .= $_;
    }

    $pw_entropy += $entropy_per_word;
}
    
pregunta spraff 22.10.2016 - 14:48
fuente

1 respuesta

7

Tiene razón al usar /dev/urandom . No use /dev/random : no es mejor que /dev/urandom , y de alguna manera es peor. Esta página es un buen resumen sobre ese tema.

El cálculo de la entropía es correcto. Entropy es una medida de lo que podría generar el proceso de generación de contraseña, no de lo que ha producido; por lo tanto, si tiene n palabras en su lista y selecciona cada palabra de manera aleatoria y uniforme, entonces obtendrá exactamente n bits de entropía por palabra (logaritmo de base 2 aquí) . La entropía no se reduce si toca varias veces la misma palabra. Puede encontrar explicaciones más detalladas en esta respuesta .

Su prueba de bucle:

next if ($n >= @words); # don't use %, it will bias the randomness

es correcto. Evitó el sesgo inducido por la operación de módulo. Sin embargo, hay una ligera ineficiencia aquí, ya que genera un número integral de bytes . Por ejemplo, si su lista contiene, digamos, 1000 palabras, producirá secuencias de dos bytes, por lo tanto, un número en el rango de 0..65535. Tendrá que recorrer un promedio de 65.536 veces antes de llegar a un número en el rango de 0..999. Dependiendo de su contexto, esto puede o no importar; las computadoras modernas son muy rápidas, y si la generación de contraseñas es manejada por humanos (usted produce una contraseña única para un usuario humano que la está esperando), entonces la computadora tiene mucho poder de computación de sobra, y las docenas / cientos de bucles ganaron ni siquiera ser notable.

Si desea ser más eficiente, se pueden realizar principalmente dos mejoras:

  • Trunca la secuencia de bytes a la longitud mínima en bits. Por ejemplo, si tiene una lista de 1000 palabras, la longitud de bit mínima es 10 (porque 2 10 = 1024). Esto implicaría enmascarar (es decir, borrar) los 6 bits superiores del entero aleatorio de 16 bits. En ese caso específico, esto significaría que el bucle ocurriría solo en el 2.4% de los casos, es decir, muy raramente. Sobre una base más general, el truncamiento a la longitud de bit correcta garantiza que el número promedio de instancias de bucle no sea más de 2.

  • Use una combinación de exclusión (cuando el número es demasiado alto) y reducción de módulo. Con una lista de 1000 palabras, esto significaría generar un número en el rango 0..64999 y luego reducir el módulo 1000: la cláusula next se activará solo cuando el entero de 16 bits caiga en el rango 65000..65535 (es decir, no muy a menudo), y el módulo no induciría un sesgo porque 65000 es un múltiplo de 1000. Es posible que desee inspirarse en la documentación para Java java.util.Random.nextInt(int bound) (la documentación incluye un extracto de código que es ilustrativo; esto es Java, pero el concepto se aplica a otros idiomas también).

No recomendaría las capitalizaciones aleatorias: no dañan directamente la seguridad, pero consumen recursos de memoria humana para una ganancia de entropía relativamente mediocre. Es decir, si al no usar el uso de mayúsculas, deja suficiente espacio en su cerebro para recordar un par de palabras adicionales, entonces eso es probablemente una mejor oferta. Además, tener una contraseña en minúscula facilita la entrada de la contraseña, especialmente en los teléfonos inteligentes.

    
respondido por el Thomas Pornin 22.10.2016 - 15:54
fuente

Lea otras preguntas en las etiquetas