PRNG: ¿La combinación de algos inseguros ayuda?

3

Al leer acerca de lo insegura que es la función rand de PHP , estaba preguntándose si ayuda a combinar funciones aleatorias. La función sugerida allí, openssl_random_pseudo_bytes , también puede ser criptográficamente insegura (ver la segunda argumento). Combinar la salida de esto y rand () y quizás también mt_rand () podría alargar el período:

function more_randomness() {
    $n = 0;
    $n += rand(0, 255);
    $n += mt_rand(0, 255);
    $n += ord(openssl_random_pseudo_bytes(1));
    return round($n / 3);
}

Si esto es completamente estúpido, solo dímelo. También dígame cómo generar números aleatorios seguros criptográficamente cuando esto devuelva falso:

function has_bad_prng() {
    openssl_random_pseudo_bytes(1, $is_bad);
    return $is_bad;
}
    
pregunta Luc 10.08.2012 - 16:03
fuente

3 respuestas

7

Un PRNG puede ser inseguro por varias razones, pero una de ellas está utilizando como semilla algunos datos que pueden tener solo un número limitado de valores distintos. Por ejemplo, si usa la hora actual como semilla, entonces el atacante conoce ese valor, o al menos potencialmente lo sabe con un esfuerzo no tan difícil: incluso si tiene un reloj interno con precisión de microsegundos, y el atacante sabe que el reloj solo llega a una precisión de aproximadamente un segundo, entonces esto equivale a solo un millón o menos de valores de semilla posibles.

Al enumerar los posibles valores de inicialización, el atacante puede volver a calcular los mismos flujos posibles que usted. Puedes sumar cientos de PRNG con cualquier algoritmo que desees; si todos usan la hora actual como semilla, esto no lo salvará.

"Agregar" juntos varios PRNG podría ayudar si PRNG está correctamente sembrado (con fuentes distintas) y algunos de los PRNG son criptográficamente débiles. Pero hay detalles sutiles; No es fácil hacerlo bien, y por lo general no vale la pena el esfuerzo.

Si openssl_random_pseudo_bytes() devuelve "inseguro", entonces hay muy poco que puedas hacer para salvarlo. Además, esto no sucede en la práctica, a menos que su sistema esté dañado de alguna manera. Cualquier servidor decente, ya sea Linux, Windows, MacOS, FreeBSD ... mantiene un PRNG criptográficamente sólido con eventos de hardware (que es /dev/urandom , CryptGenRandom() ...) y eso es lo que utiliza OpenSSL. Si esto no funciona, entonces las cosas se han agriado mucho en su sistema y es hora de entrar en pánico (es decir, generar excepciones y alertar al administrador de sistemas).

    
respondido por el Thomas Pornin 10.08.2012 - 17:47
fuente
2

Técnicamente, mejora la seguridad un poco, pero no tiene un final útil.

Los números aleatorios generalmente provienen de un generador de números pseudoaleatorios (PRNG) que a su vez se siembra con un valor aleatorio. El propósito del PRNG es estirar la semilla original para producir una salida muy larga. Los números aleatorios se suelen invocar por dos razones:

  • Para crear datos de apariencia aleatoria para un uso un tanto casual. Tal vez para dar a los personajes de un videojuego una estrategia de aspecto aleatorio, tal vez ejecutar un algoritmo aleatorio , etc. El requisito general es que los valores aleatorios están bien distribuidos y pasan pruebas estadísticas básicas, aunque el uso exacto determina exactamente cuáles son los requisitos.

  • Para proporcionar seguridad criptográfica. Quizás para generar una clave secreta, para iniciar la búsqueda de un número primo aleatorio, etc. El requisito es que los valores aleatorios estén muy bien distribuidos, pasen muchas pruebas estadísticas avanzadas, tengan un espacio semilla muy grande y no proporcionen información sobre otros valores en la salida o algo sobre la semilla del PRNG.

Los PRNG generalmente están diseñados para uno de esos requisitos y no se parecen en nada. Los PRNG para uso casual tienden a ser muy simples, extremadamente rápidos y no cumplen ninguno de los requisitos de un PRNG criptográfico. Es muy difícil convertir un PRNG simple en un PRNG criptográfico; para hacerlo, es probable que se parezca muy poco al PRNG original que queda en el esquema final de PRNG seguro.

Estos son algunos de los problemas con la combinación de PRNG débiles:

  • Duración del período. Cuando combina dos PRNG de forma lineal (como en el OP), en el mejor de los casos, combinará las longitudes de sus semillas. Los PRNG simples generalmente tienen 32 bits o menos de longitud de semilla, lo cual es criptográficamente muy inseguro. Por lo general, debe tener al menos 128 bits de espacio semilla.

  • Protección de semillas. La combinación de las salidas de PRNG no necesariamente evitará que la semilla se modifique mediante ingeniería inversa a partir de la salida de PRNG. Si un atacante puede derivar parte de la semilla, puede reducir su carga de trabajo drásticamente. Derivar la semilla de la salida de un PRNG simple a veces es trivial en circunstancias adecuadas.

  • Sesgo de salida. La combinación lineal de las salidas de PRNG no ocultará necesariamente sus salidas defectuosas. Definitivamente debería mejorar el sesgo, pero es poco probable que sean tan buenos como un PRNG criptográfico. (En la práctica, esto probablemente sea una preocupación menor, pero aún así vale la pena mencionarlo).

Y eso supone que siembras el PRNG correctamente. Aún debe hacer esa siembra de forma manual, ya que cualquiera que sea la siembra por defecto que utilizan los PRNG simples, probablemente se basa en algo de muy baja calidad, como una marca de tiempo.

El simple resumen es que la combinación de PRNG débiles proporciona una mejor seguridad, pero no el nivel de seguridad que debe esperar de un PRNG criptográficamente seguro. La solución es obtener un PRNG criptográfico real y sembrarlo con datos aleatorios de una buena fuente, como /dev/random o CryptGenRandom() . O simplemente puede usar la salida de esos directamente, ya que técnicamente son PRNG sembrados por otros datos aleatorios.

Si openssl_random_pseudo_bytes establece el indicador que indica que no generó bytes aleatorios seguros, parecería que hay algún problema con el entorno porque los manuales sugieren que debería esperarse que regrese true en condiciones normales. Compruebe para ver qué versión de PHP / OpenSSL está instalada y si puede actualizarla. Si no puede hacerlo funcionar, considere simplemente obtener sus datos aleatorios directamente de /dev/random o CryptGenRandom() .

    
respondido por el B-Con 10.08.2012 - 17:55
fuente
1

Si la razón por la que las funciones son inseguras es porque puede agotar el espacio de semilla después de ver un número muy pequeño de valores, entonces este enfoque podría dar la suma del número de bits de seguridad de la semilla, suponiendo que las semillas fueran perfectamente aleatorias.

Si el problema es que tienen un período corto, si las funciones tienen períodos co-primarios por pares, entonces el período de la función compuesta es el múltiplo de los tres períodos, de lo contrario es el múltiplo común más bajo.

En general, el aumento de la seguridad es probablemente marginal, dado que es probable que los períodos sean poderes de dos, y que una combinación de agotar el espacio semilla de uno y el período del otro sea una táctica efectiva. En teoría, podría tener un aumento exponencial de la seguridad, pero lo más probable es que se encuentre rápidamente un ataque combinado. Por ejemplo, la semilla de uno podría no ser independiente de las semillas de los demás si están basadas en el tiempo y las llamadas son secuenciales.

Para responder la segunda parte de su pregunta, he visto este enlace en SO a algún código que pueda hacer lo que quieras.

    
respondido por el jhoyla 10.08.2012 - 16:38
fuente

Lea otras preguntas en las etiquetas