¿Cuáles son las debilidades de la semilla predeterminada de srand() de Perl, publicar la versión 5.004?

Question

Puedo encontrar mucha documentación sobre problemas con el uso de time() antes de la versión 5.004 de Perl, pero nada a continuación.

Para una asignación de tarea, se nos pide que realicen una ingeniería inversa de los resultados de un programa en base a la suposición de que el valor por defecto de Perl srand() sigue siendo defectuoso en la distribución predeterminada. El changelog for the perl 5.004 release indica que el valor predeterminado srand() ahora se basa en "una gran combinación de valores difíciles de predecir que dependen del sistema".

¿Es ese el caso y, de ser así, cuáles son esos valores y tienen alguna debilidad inherente?

Answer 1

(No soy un criptógrafo pero he absorbido mucho a lo largo de los años. Tuve que ayudar a analizar la generación de números aleatorios de un cliente hace años, que es lo que me llevó a encontrar ese error de Crypt :: Random mencionado más adelante)

El código de inicialización tiene más sentido si se sangran adecuadamente todos esos ifdefs. Este es el código en 5.16.0.

U32 
Perl_seed(pTHX) 
{ 
    dVAR; 
    /* 
    * This is really just a quick hack which grabs various garbage 
    * values. It really should be a real hash algorithm which 
    * spreads the effect of every input bit onto every output bit, 
    * if someone who knows about such things would bother to write it. 
    * Might be a good idea to add that function to CORE as well. 
    * No numbers below come from careful analysis or anything here, 
    * except they are primes and SEED_C1 > 1E6 to get a full-width 
    * value from (tv_sec * SEED_C1 + tv_usec). The multipliers should 
    * probably be bigger too. 
    */ 
#if RANDBITS > 16 
# define SEED_C1 1000003 
# define SEED_C4 73819 
#else 
# define SEED_C1 25747 
# define SEED_C4 20639 
#endif 

#define SEED_C2 3 
#define SEED_C3 269 
#define SEED_C5 26107 

#ifndef PERL_NO_DEV_RANDOM 
    int fd; 
#endif 

    U32 u; 

#ifdef VMS 
# include <starlet.h> 
    /* when[] = (low 32 bits, high 32 bits) of time since epoch 
    * in 100-ns units, typically incremented ever 10 ms.  */ 
    unsigned int when[2]; 
#else 
# ifdef HAS_GETTIMEOFDAY 
     struct timeval when; 
# else 
     Time_t when; 
# endif 
#endif 

/* This test is an escape hatch, this symbol isn't set by Configure. */ 
#ifndef PERL_NO_DEV_RANDOM 
# ifndef PERL_RANDOM_DEVICE 
     /* /dev/random isn't used by default because reads from it will block 
      * if there isn't enough entropy available. You can compile with 
      * PERL_RANDOM_DEVICE to it if you'd prefer Perl to block until there 
      * is enough real entropy to fill the seed. */ 
#  define PERL_RANDOM_DEVICE "/dev/urandom" 
# endif 
    fd = PerlLIO_open(PERL_RANDOM_DEVICE, 0); 
    if (fd != -1) { 
     if (PerlLIO_read(fd, (void*)&u, sizeof u) != sizeof u) 
     u = 0; 
    PerlLIO_close(fd); 
    if (u) 
     return u; 
    } 
#endif 

#ifdef VMS 
    _ckvmssts(sys$gettim(when)); 
    u = (U32)SEED_C1 * when[0] + (U32)SEED_C2 * when[1]; 
#else 
# ifdef HAS_GETTIMEOFDAY 
     PerlProc_gettimeofday(&when,NULL); 
     u = (U32)SEED_C1 * when.tv_sec + (U32)SEED_C2 * when.tv_usec; 
# else 
     (void)time(&when); 
     u = (U32)SEED_C1 * when; 
# endif 
#endif 

    u += SEED_C3 * (U32)PerlProc_getpid(); 
    u += SEED_C4 * (U32)PTR2UV(PL_stack_sp); 

#ifndef PLAN9   /* XXX Plan9 assembler chokes on this; fix needed */ 
    u += SEED_C5 * (U32)PTR2UV(&when); 
#endif 

    return u; 
} 

El código es tan confuso porque es realmente varias formas de obtener la entropía todos intercalado entre sí. Básicamente, hay dos caminos: el dispositivo aleatorio del sistema y la recopilación del estado del intérprete y el entorno.

• El sistema dispositivo aleatorio.

Este es el método más simple y probablemente más potente. Si su sistema operativo tiene un dispositivo aleatorio que no bloquea, es decir. /dev/urandom leyó 32 bits de él. ¡Hecho! #ifndef PERL_NO_DEV_RANDOM (buen doble negativo) controla ese bit. Esto se hace en casi todos los sistemas Unix. En este punto, el análisis de la semilla aleatoria de Perl cambia a la implementación de su sistema operativo particular '/dev/urandom.

• Derive algo del reloj, pid y puntero de la pila.

Si su sistema no tiene un dispositivo aleatorio, básicamente Windows, Perl recurre a la obtención de una semilla al mezclar algunos valores del sistema con la esperanza de predecir.

• El tiempo en microsegundos o segundos, depende de si existe gettimeofday().
• La identificación del proceso, PerlProc_getpid().
• La ubicación de la memoria del puntero de pila actual, PTR2UV(PL_stack_sp).

Lo que debe hacer con esa información, y esto es lo que el gran comentario al principio se trata, es ralla juntos usando un algoritmo de hash real. En su lugar, los multiplica por varias constantes (SEED_C1, SEED_C2, etc.) y los suma. Esto seguramente será defectuoso.

Toda esa información es, en teoría, predecible. No sé cuál es el estado del arte para predecir la información del sistema, pero el puntero time + pid + stack es un método bastante común para obtener entropía y seguramente habrá documentos sobre el tema.

Existe un error adicional en común con todos los métodos de Perl, lo hace utilizando solo 32 bits, incluso en máquinas de 64 bits. No extraerá 64 bits de /dev/urandom, solo 32. Solo verá 32 bits de la identificación del proceso, el puntero de la pila o la información del tiempo, incluso si hay 64 bits de información.

Después de leer el código, me preocupan tres cosas.

• Su uso de solo 32 bits de aleatoriedad.

Es posible que el sistema multi-GPU podría hacer fuerza bruta.

• (Unix) Qué tan bueno es su /dev/urandom.

/dev/urandom puede quedarse sin entropía si extrae demasiado de ella demasiado rápido. En lugar de bloquearlo generará una entropía más débil. Esto está fuera del control de Perl, pero es una debilidad de todo el sistema. Además, algunos programas pueden extraer más entropía de la necesaria para agotar /dev/urandom. Encontramos a bug years ago in Crypt::Random que estaba haciendo exactamente eso.

• (Windows) Ese algoritmo hash débil.

Al lado del problema de 32 bits, este es probablemente el enlace más débil.

• ¿Qué función aleatoria usa?

Una vez que se ha proporcionado una semilla, ¿a qué función de número aleatorio lo está pasando? Una función de rand pobre hace que sea más fácil adivinar la semilla. Perl busca varios, generalmente terminando con drand48. Puedes ver lo que está usando con: use Config; print $Config{randfunc}'. No tengo idea de qué tan bien funciona, pero la página de manual de OS X drand48 dice que random(3) es más potente y la página del manual de Linux dice drand48 is obsolete.

La función no se ha tocado desde ... oh querida finales de los 90. Se movió a util.c pero no se ha tocado seriamente. git blame 132efe8bfb7cd0fb1beb15aaf284e33bf44eb1fa^ pp.c muestra la historia real, busque S_seed. Probablemente necesita un poco de amor. La mayoría de los otros idiomas tienen more advanced random number generators.