Predecir la salida del rand de PHP ()

He leído en numerosas fuentes que la salida del rand () de PHP es predecible ya que es un PRNG, y en su mayoría lo acepto como un hecho simplemente porque lo he visto en muchos lugares.

Estoy interesado en una prueba de concepto: ¿cómo haría para predecir la salida de rand ()? Al leer este artículo , entiendo que el número aleatorio es un número devuelto de una lista que comienza en un puntero (la semilla), pero no puedo imaginar cómo esto es predecible.

¿Alguien podría averiguar razonablemente qué # aleatorio se generó a través de rand () en un momento dado en el tiempo dentro de unos pocos miles de conjeturas? o incluso 10.000 conjeturas? ¿Cómo?

Esto está surgiendo porque vi una biblioteca de autenticación que usa rand () para producir un token para usuarios que han perdido contraseñas, y supuse que esto era un agujero de seguridad potencial. Desde entonces, he reemplazado el método con una combinación de hashing openssl_random_pseudo_bytes(), la contraseña hash original y microtime. Después de hacer esto, me di cuenta de que si estuviera mirando hacia afuera, no tendría idea de cómo adivinar el token, incluso sabiendo que era un md5 de rand ().

La capacidad de adivinar el siguiente valor randestá vinculada a la capacidad de determinar con qué srandse llamó. En particular, ¡ sembrar srandcon un número predeterminado da como resultado un resultado predecible ! Desde el mensaje interactivo de PHP:

[charles@charles-workstation ~]$ php -a
Interactive shell

php > srand(1024);
php > echo rand(1, 100);
97
php > echo rand(1, 100);
97
php > echo rand(1, 100);
39
php > echo rand(1, 100);
77
php > echo rand(1, 100);
93
php > srand(1024);
php > echo rand(1, 100);
97
php > echo rand(1, 100);
97
php > echo rand(1, 100);
39
php > echo rand(1, 100);
77
php > echo rand(1, 100);
93
php > 

Esto no es solo una casualidad. La mayoría de las versiones de PHP ^* en la mayoría de las plataformas ^** generarán la secuencia 97, 97, 39, 77, 93 cuando srandesté en 1024.

Para ser claros, esto no es un problema con PHP, es un problema con la implementación de randsí mismo. El mismo problema aparece en otros idiomas que usan la misma implementación (o similar), incluido Perl.

El truco es que cualquier versión sensata de PHP se habrá sembrado previamente srandcon un valor "desconocido". Oh, pero no es realmente desconocido. De ext/standard/php_rand.h:

#define GENERATE_SEED() (((long) (time(0) * getpid())) ^ ((long) (1000000.0 * php_combined_lcg(TSRMLS_C))))

Entonces, es algo de matemática con time(), el PID y el resultado de php_combined_lcg, que se define en ext/standard/lcg.c. No voy a hacer c & p aquí, ya que, bueno, mis ojos estaban vidriosos y decidí dejar de cazar.

Un poco de Google muestra que otras áreas de PHP no tienen las mejores propiedades de generación de aleatoriedad , y llama a php_combined_lcgdestacar aquí, especialmente este bit de análisis:

Esta función ( gettimeofday) no solo nos devuelve una marca de tiempo precisa del servidor en bandeja de plata, sino que también agrega salida LCG si solicitamos "más entropía" (de PHP uniqid).

Si esouniqid . Parece que el valor de php_combined_lcges lo que vemos cuando miramos los dígitos hexadecimales resultantes después de llamar uniqidcon el segundo argumento establecido en un valor verdadero.

Ahora, donde estabamos?

Oh si. srand.

Por lo tanto, si el código del que está tratando de predecir valores aleatorios no llama srand, tendrá que determinar el valor proporcionado por php_combined_lcg, que puede obtener (¿indirectamente?) A través de una llamada a uniqid. Con ese valor en la mano, es factible aplicar la fuerza bruta al resto del valor time(), el PID y algunas matemáticas. El problema de seguridad vinculado se trata de romper sesiones, pero la misma técnica funcionaría aquí. De nuevo, del artículo:

Aquí hay un resumen de los pasos de ataque descritos anteriormente:

• Espere a que el servidor se reinicie
• buscar un valor uniqid
• fuerza bruta la semilla RNG de este
• sondear el estado en línea para esperar a que aparezca el objetivo
• intercalar encuestas de estado con encuestas uniqid para realizar un seguimiento de la hora actual del servidor y el valor RNG
• ID de sesión de fuerza bruta contra el servidor usando el intervalo de tiempo y valor de RNG establecido en el sondeo

Simplemente reemplace el último paso según sea necesario.

(Este problema de seguridad se informó en una versión anterior de PHP (5.3.2) de la que tenemos actualmente (5.3.6), por lo que es posible que el comportamiento de uniqidy / o php_combined_lcghaya cambiado, por lo que esto es específico técnica podría no ser viable por más tiempo. YMMV.)

Por otro lado, si el código que está tratando de llamarsrand al producto se llama manualmente , a menos que estén usando algo muchas veces mejor que el resultado php_combined_lcg, probablemente será mucho más fácil adivinar el valor y sembrar su local generador con el número correcto. La mayoría de las personas que llamarían manualmente srandtampoco se darían cuenta de lo horrible que es esta idea y, por lo tanto, es probable que no usen mejores valores.

Vale la pena señalar que mt_randtambién se ve afectado por el mismo problema. La siembra mt_srandcon un valor conocido también producirá resultados predecibles. Basar su entropía openssl_random_pseudo_byteses probablemente una apuesta más segura.

tl; dr: Para obtener mejores resultados, no siembres el generador de números aleatorios de PHP y, por el amor de Dios, no expongas uniqida los usuarios. Hacer uno o ambos de estos puede hacer que sus números aleatorios sean más adivinables.

Actualización para PHP 7:

PHP 7.0 presenta random_bytesy random_intcomo funciones principales. Utilizan la implementación CSPRNG del sistema subyacente, lo que los libera de los problemas que tiene un generador de números aleatorios. Son efectivamente similares a openssl_random_pseudo_bytes, solo sin necesidad de instalar una extensión. Un polyfill está disponible para PHP5 .

*: El parche de seguridad Suhosin cambia el comportamiento de randymt_rand siempre se reinicia con cada llamada. Suhosin es proporcionado por un tercero. Algunas distribuciones de Linux lo incluyen por defecto en sus paquetes oficiales de PHP, mientras que otros lo hacen una opción, y otros lo ignoran por completo.

**: Dependiendo de la plataforma y las llamadas a la biblioteca subyacente que se utilicen, se generarán diferentes secuencias de las documentadas aquí, pero los resultados aún deberían ser repetibles a menos que se use el parche Suhosin.

Para ilustrar visualmente cuán no aleatoria es la rand()función, aquí hay una imagen donde todos los píxeles están formados por valores "aleatorios" de rojo, verde y azul:

Normalmente no debería haber ningún patrón en las imágenes.

He intentado llamar srand()con diferentes valores, no cambia cuán predecible es esta función.

Tenga en cuenta que ambos no son criptográficamente seguros y producen resultados predecibles.

la salida de rand () de PHP es predecible ya que es un PRNG

Es un generador de congruencia lineal. . Eso significa que tiene una función que es efectiva: NEW_NUMBER = (A * OLD_NUMBER + B) MOD C. Si grafica NEW_NUMBER vs OLD_NUMBER, comenzará a ver líneas diagonales. Algunas de las notas en la documentación RAND de PHP dan ejemplos de cómo hacerlo.

Esto está surgiendo porque vi una biblioteca de autenticación que usa rand () para producir un token para usuarios que han perdido contraseñas, y supuse que esto era un agujero de seguridad potencial.

En una máquina con Windows, el valor máximo de RAND es 2 ^ 15. Esto le da al atacante solo 32,768 posibilidades de verificar.

¿Alguien podría averiguar razonablemente qué # aleatorio se generó a través de rand () en un momento dado en el tiempo dentro de unos pocos miles de conjeturas? o incluso 10.000 conjeturas? ¿Cómo?

Mientras este artículo no es exactamente el que está buscando, muestra cómo algunos investigadores tomaron una implementación existente de un generador de números aleatorios y lo usaron para ganar dinero en Texas Holdem. Hay 52! posibles barajas barajadas, pero la implementación usó un generador de números aleatorios de 32 bits (que es el número máximo de mt_getrandmax en una máquina con Windows), y lo sembró con el tiempo en milisegundos desde la medianoche. Esto redujo el número de posibles barajas barajadas de aproximadamente 2 ^ 226 a aproximadamente 2 ^ 27, lo que permite buscar en tiempo real y saber qué baraja se ha repartido.

Después de hacer esto, me di cuenta de que si estuviera mirando hacia afuera, no tendría idea de cómo adivinar el token, incluso sabiendo que era un md5 de rand ().

Recomiendo usar algo de la familia SHA-2 ya que los federales consideran que md5 está roto. Algunas personas usan google para descifrar los hash md5 porque son muy comunes. Simplemente hash algo y luego arroja el hash en una búsqueda en google, básicamente google se ha convertido en una mesa gigante de arcoiris .

Es realmente más exacto decir que dado un número generado aleatoriamente, el siguiente es relativamente predecible. Solo hay tantos números que puede ser. Pero eso no significa que puedas adivinarlo, más que puedas escribir un programa que lo haga, bastante rápido.