Predecir la salida del rand de PHP ()

21

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 ().

Erik
fuente
"pero no puedo imaginar cómo esto es predecible"? Primero debe leer " en.wikipedia.org/wiki/Linear_congruential_generator " para poder comenzar a imaginar cómo es predecible. Luego, puede revisar su pregunta para eliminar el asombro y pasar a los temas más prácticos de ingeniería inversa del PHP fuente función rand para ver cómo funciona.
S. Lott
"Supuse que esto era un agujero de seguridad potencial"? Solo si Evil Hacker podría obtener la contraseña aleatoria de algún usuario, use una tabla de arco iris para deshacer el hash MD5 para recuperar el valor original (pre-hash) y luego garantizar que hicieron la próxima solicitud de contraseña. Teóricamente posible, supongo. Pero solo si tenían una mesa arcoiris en funcionamiento para un número aleatorio.
S.Lott
@ S.Lott: no se trata de una contraseña. El sistema le permite restablecer la contraseña y le envía por correo electrónico un token que se utiliza en una URL. El token se genera a través de MD5 (rand ()). Si puede predecir la salida de rand (), puede cambiar la contraseña de cualquier persona, sin tener el hash para el original, o sin saber el original.
Erik
@Erik. Correcto. Reemplace "contraseña aleatoria" con "token aleatorio" si eso ayuda. El token solo se puede abusar si alguien puede desenrollar el hash MD5 para recuperar el número aleatorio Y asegurarse de que obtendrá el siguiente número aleatorio. Predecir el próximo rand es solo una pequeña parte. Deshacer el MD5 es la parte difícil.
S.Lott
1
Tenga en cuenta que MD5 (rand ()) solo tiene la misma seguridad que rand (). Es práctico construir una tabla de búsqueda de MD5 (rand ()) -> rand () para el conjunto muy limitado de números involucrados. Con el dominio limitado de rand (), puede probar la fuerza bruta simple a menos que exista un mecanismo para evitar intentos repetidos.
MZB

Respuestas:

28

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.

Charles
fuente
Gracias Charles: entre tu respuesta y la lectura del enlace en el generador de congruencia lineal de Tangurena, siento que lo entiendo mejor. Ya "sabía" que usar rand () de esta manera era una mala idea, pero sé que sé por qué .
Erik
Wow, accesorios para una respuesta bien explicada, ¡gracias!
David Hobs
10

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:

Valores aleatorios RGB

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.

minipif
fuente
7

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 .

Tangurena
fuente
1

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.

pdr
fuente
1
Creo que el siguiente número es completamente determinista. No "relativamente" pero absolutamente. El problema con los generadores de números pseudoaleatorios es que una secuencia pasará pruebas estadísticas. Dos números adyacentes, aunque totalmente deterministas, tendrán muchas propiedades estadísticas en común con los números aleatorios reales.
S.Lott
1
El siguiente número es completamente determinista. Eso es lo que significa el "pseudo" en el generador de números pseudoaleatorios. Por otro lado, la información necesaria para determinar que el próximo número es casi imposible de adquirir en la práctica.
Rein Henrichs
@ S.Lott: tenía la impresión de que un número podía aparecer varias veces en las 2 ^ 32 salidas posibles y que cada vez que aparecía podía ir seguido de un número diferente. Pero dada una semilla de X, que devuelve un resultado de Y, el siguiente resultado siempre será el mismo. Por lo tanto, en la práctica, puede haber un puñado de números que siguen a Y. Sin embargo, puedo estar equivocado; Ha pasado mucho tiempo desde que realmente miré las PRNG.
pdr