¿Cómo determinar el estado de un generador de números aleatorios?

3

Siempre se ha dicho que para obtener números criptográficos sólidos en computación, se necesita un buen generador de números aleatorios. Sin una buena fuente de aleatoriedad, un atacante podría determinar el estado del generador de números aleatorios y predecir los siguientes números aleatorios. Obviamente, esto significa que luego tienen o podrían tener sus claves de cifrado y cosas así.

Sé que este debe ser un ataque muy real, pero siempre lo he considerado teórico porque no tengo idea de cómo se haría esto. ¿Cuál sería un buen escenario del mundo real podría explotar la previsibilidad de un generador de números aleatorios no tan bueno (pero mejor que "la cantidad de tiempo desde que abrió el símbolo del sistema")?

Además, ¿sería posible generar una clave con dicho generador y luego hacer que un atacante vuelva a crear esa clave utilizando solo un conocimiento aproximado del sistema en el que se ejecutó el generador?

O, ¿estoy malinterpretando completamente la vulnerabilidad en un generador de números aleatorios más pobre?

    
pregunta Nicholas Dechert 03.11.2016 - 17:00
fuente

1 respuesta

3

Un gran número de protocolos seguros dependen de números pseudoaleatorios aleatorios o seguros. Incluso los identificadores de sesión creados por la mayoría de las aplicaciones web para realizar un seguimiento de qué solicitud web pertenece a qué usuario depende de cadenas aleatorias que se generan utilizando números aleatorios.

Si, por ejemplo, pudiera predecir el próximo ID de sesión generado por una aplicación web, podría secuestrar esta sesión.

Los números aleatorios se utilizan para crear claves de sesión en varios protocolos (ssl, ssh, ...). Si pudiera predecir estas claves, podría descifrar los datos enviados en estas sesiones. También se utilizan como valores nonce, y si puedo predecirlos, puedo romper una serie de protocolos que dependen de que los nonces no sean predecibles.

cómo llegar al estado

Para adivinar el estado de un generador de números aleatorios, generalmente es necesario observar muchos números generados por el RNG.

Esto no significa que tenga que observar la aplicación que solicita estos números. Si tiene acceso al mismo RNG (que es posible si tiene acceso al servidor físico donde reside su aplicación víctima), simplemente puede solicitar un millón o diez millones de números, utilizando otro programa. Pero, por lo general, no tiene acceso directo al RNG, por lo que debe observar las comunicaciones de forma pasiva durante mucho tiempo o engañar al servidor para que proporcione más de estos números (por ejemplo, conectándose como usuario habitual y solicitando rotación de clave de cifrado 100 veces por segundo en un protocolo mal diseñado que permite esto).

Una calidad de los buenos generadores de números aleatorios es que tienen períodos muy largos, por ejemplo. se necesita una gran cantidad de invocaciones antes de que comiencen a repetirse.

Supongamos, por ejemplo, que tiene un generador realmente malo que comienza a repetir su secuencia de números después de solo 256 invocaciones. Ahora, si puede observar algunos de estos números aleatorios, puede señalar fácilmente en qué punto de la secuencia se encuentra el generador de números aleatorios y predecir correctamente todos los números futuros generados.

Un buen generador también debería generar números que pasen varias pruebas estadísticas. Eso significa que, por ejemplo, todos los números en el espacio de salida deberían generarse con aproximadamente la misma frecuencia, que no debería haber patrones detectables (por ejemplo, el RNG siempre alternando entre números pares e impares), etc.

Si logra detectar un patrón específico en un RNG, además de poder predecir partes de un número "aleatorio" futuro, puede descubrir que este patrón siempre ocurre cuando los 8 bits menos importantes en el RNG son En una determinada configuración. Si logró identificar algunos de estos patrones que le permiten inferir partes del estado del RNG, podría combinar estas observaciones para obtener una mayor parte de todo el estado.

Los RNG buenos deben tener en cuenta el estado completo de cada bit de salida que producen. Pero digamos que tienes uno que no hace esto. Por ejemplo, suponga que tiene un RNG que produce números cuyo bit más bajo solo depende de un solo bit del estado RNG. Esto significa que el RNG pierde parte de su estado interno con cada número que produce. Y si el bit más bajo dependiera de dos bits de estado interno, el RNG todavía filtraría información probabilística importante sobre el estado de estos dos bits con cada número producido.

    
respondido por el Pascal 03.11.2016 - 17:44
fuente

Lea otras preguntas en las etiquetas