Ataque a PRNG

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 1 de enero de 2021; las comprobaciones requieren 2 ediciones .

Un ataque a un generador de números pseudoaleatorios es un ataque destinado a revelar los parámetros de un generador de números pseudoaleatorios ( PRNG ) para poder predecir aún más los números pseudoaleatorios.

Relevancia

La seguridad de los sistemas criptográficos a menudo depende de algunos datos que solo deberían conocer los usuarios autorizados y que deberían ser difíciles de adivinar para un atacante. Ejemplos de tales datos pueden ser claves de sesión que inicializan vectores, sal , parámetros únicos en funciones EDS y muchos otros objetos. Para lograr el nivel requerido de imprevisibilidad, dada la generación frecuente de números aleatorios, se requiere una fuente confiable de números aleatorios. Desafortunadamente, muchas aplicaciones criptográficas no tienen una fuente confiable de secuencias aleatorias de valores, como el ruido térmico en los circuitos eléctricos o el tiempo exacto entre un par de contadores Geiger. En su lugar, debe utilizar generadores de números pseudoaleatorios (PRNG). El PRNG recibe como entrada un flujo de datos de una fuente con baja entropía e intenta convertirlo en una secuencia de valores que es prácticamente indistinguible de una secuencia aleatoria real. Un ataque exitoso a un PRNG puede romper muchos sistemas criptográficos, sin importar cuán cuidadosamente hayan sido diseñados. Sin embargo, algunos sistemas usan PRNG mal diseñados o lo hacen de una manera que reduce la complejidad de los ataques. Además, solo se necesita una infiltración exitosa para comprometer todo el sistema.

Tipos de ataques a PRNG

Dependiendo de qué datos PRNG sean más fáciles de rastrear (valores de salida, valores de entrada o estado interno), se pueden implementar los siguientes tipos de ataques.

Ataque criptoanalítico directo

Si un atacante puede monitorear directamente la salida de PRNG e investigar el patrón de su ocurrencia, entonces este es un ataque criptoanalítico directo. Este tipo de ataque se extiende a la mayoría de los algoritmos que usan PRNG. Sin embargo, si, por ejemplo, el PRNG se usa únicamente para la generación de claves, como se hace en Triple DES , entonces no puede ser vulnerable a este tipo de ataque, ya que las salidas del PRNG nunca son directamente visibles.

Ataques basados en entrada

Este tipo de ataque es posible en los casos en que un atacante puede usar el conocimiento de las señales de entrada PRNG o controlarlas. Los ataques basados en entradas se pueden dividir en ataques con entradas conocidas, ataques con entradas reproducibles y ataques contra entradas seleccionadas.

Los ataques de entrada conocidos son factibles en situaciones en las que alguna entrada que el diseñador del sistema espera que sea difícil de predecir resulta ser fácil de adivinar en algunos casos particulares.

Los ataques de entrada reproducibles se pueden usar en las mismas situaciones, pero requieren sistemas de piratería menos sofisticados y un análisis menos sofisticado por parte del atacante.

Los ataques de entrada seleccionados se pueden implementar prácticamente en sistemas que utilizan tarjetas inteligentes o tokens. Además, dicho ataque puede ser peligroso para las aplicaciones que usan mensajes de texto, contraseñas definidas por el usuario, estadísticas de red, tiempo, etc. como señales de entrada en PRNG.

Ataques basados en revelar el estado interno

Al realizar este tipo de ataque, el atacante intenta usar ataques exitosos anteriores en el PRNG, que revelaron su estado interno, para predecir el estado de los estados futuros o anteriores del PRNG, en la medida de lo posible. Dichos ataques pueden tener éxito cuando el PRNG comienza desde un estado conocido o predecible. En la práctica, es muy difícil determinar el hecho de que el estado interno se ha visto comprometido. Es por eso que los PRNG deben resistirse a comprometer el estado interno. Hay al menos 4 opciones para tal ataque:

Un ataque de reversión utiliza el estado abierto del PRNG en un punto en el tiempo para restaurar los estados del PRNG y, en consecuencia, sus salidas a puntos anteriores en el tiempo. $S$ $t_0$

El compromiso permanente del estado es posible para los sistemas en los que, una vez que el estado se revela en un momento dado, todos los estados anteriores y posteriores son vulnerables a ataques posteriores. $S$ $t_0$

Un ataque de suposición iterativo utiliza el conocimiento del estado en el momento t y las salidas intermedias del PRNG para averiguar en el momento t cuándo las entradas recopiladas durante ese período de tiempo son adivinables (pero desconocidas) para el atacante. $S$ $t_0$ $S$ $t_{0}+\Delta t$

La reunión en el medio es esencialmente una combinación de un ataque de suposición iterativo y un ataque de reversión. Conocimiento en puntos en el tiempo y permitir que el atacante restablezca el estado en puntos en el tiempo , así como en todo el intervalo de tiempo desde hasta . $S$ $t_0$ $t_{0}+2\Delta t$ $S$ $t_{0}+\Delta t$ $t_0$ $t_{0}+2\Delta t$

Ejemplos de sistemas poco fiables

Las primeras versiones del protocolo de encriptación SSL de Netscape usaban números pseudoaleatorios generados por un PRNG cuya fuente de entropía eran los valores de tres variables: hora del día, ID del proceso e ID del proceso principal. Estas cantidades son predecibles y tienen una entropía relativamente baja. En consecuencia, esta versión de SSL se consideró insegura. Netscape fue notificado del problema por Phillip Halam-Baker en 1994, entonces investigador del CERN . Sin embargo, el problema no se resolvió hasta el lanzamiento del producto de software. Posteriormente, en 1995, Ian Goldberg y David A. Wagner [1] volvieron a hablar sobre el problema . Tuvieron que aplicar ingeniería inversa a los módulos de objetos , ya que Netscape se negó a revelar los detalles de la generación de números aleatorios. PRNG se ha corregido en versiones posteriores (versión 2 y posteriores) al cambiar la fuente de entropía para que sea más aleatoria y con un nivel de entropía más alto.

Microsoft utiliza un algoritmo no publicado para generar números aleatorios en los sistemas operativos Windows . Este algoritmo está disponible para el usuario a través de la utilidad CryptGenRandom . En noviembre de 2007, Leo Dorredorf, junto con coautores de la Universidad de Haifa y la Universidad Hebrea de Jerusalén , publicaron un artículo titulado Cryptanalysis of the Random Number Generator of the Windows Operating System [2] . El artículo demuestra las graves deficiencias del algoritmo presentado por Microsoft. Las conclusiones dadas en el artículo se formularon como resultado del estudio del código desensamblado del sistema Windows 2000 , pero según Microsoft, también pueden aplicarse a Windows XP [3] .

El Instituto Nacional de Estándares y Tecnología (EE. UU.) en marzo de 2007 publicó "generadores de números pseudoaleatorios deterministas" recomendados, que se estandarizaron en la Publicación Especial NIST 800-90 [4] . Uno de los PRNG dados, Dual EC DRBG , introducido en el estándar por la Agencia de Seguridad Nacional [5] , se basa en criptografía elíptica y contiene un determinado conjunto de constantes recomendadas. En agosto de 2007, Dan Shumov y Nils Fergeson de Microsoft demostraron que las constantes se pueden elegir de tal manera que se produzca una puerta trasera en el algoritmo [6] .

En mayo de 2008, el investigador Luciano Bello publicó un artículo que indica que los cambios realizados en 2006 a PRNG en el paquete openssl distribuido con Debian Linux y otras distribuciones basadas en Debian reducen significativamente la entropía de los valores generados, lo que hace que las claves sean vulnerables a los ataques. [1] [2] El problema fue causado por los cambios realizados por uno de los desarrolladores de Debian al código de openssl en respuesta a las advertencias del compilador sobre un código aparentemente redundante. Esta vulnerabilidad se solucionó el mismo día en que se conoció [7] .

Formas de protegerse contra ataques a PRNG

Use funciones hash para ocultar los valores de salida PRNG reales. Utilice los resultados de la función hash de los valores de salida PRNG en lugar de los valores mismos para evitar ataques criptoanalíticos directos. Esta técnica, aunque no garantiza una seguridad completa, hace que el sistema sea más fiable.
Hash la fuente de entropía con marcas de tiempo, valores de contador u otros valores que cambian constantemente. Hashing la fuente de entropía con un valor que cambia constantemente antes de ingresar al PRNG puede proteger el sistema de los ataques basados en la entrada.
Cambia periódicamente el estado interno del PRNG. Cambie el estado interno del PRNG por completo de vez en cuando. Esto ayudará a defenderse de los ataques basados en revelar el estado interno, o al menos reducir el daño causado por un ataque exitoso.

Véase también

Generador de números pseudoaleatorios

Notas

↑ Randomness y Netscape Browser . Consultado el 9 de diciembre de 2011. Archivado desde el original el 22 de mayo de 2016. (indefinido)
↑ Criptoanálisis del generador de números aleatorios del sistema operativo Windows, Leo Dorrendorf (enlace no disponible) . Consultado el 9 de diciembre de 2011. Archivado desde el original el 6 de septiembre de 2012. (indefinido)
↑ Microsoft confirma que XP contiene un error en el generador de números aleatorios. Archivado el 22 de junio de 2008.
↑ Recomendación para la generación de números aleatorios mediante generadores de bits aleatorios deterministas, publicación especial NIST 800-90 archivada el 26 de septiembre de 2007 .
↑ ¿La NSA puso una puerta trasera secreta en el nuevo estándar de cifrado?
↑ Sobre la posibilidad de una puerta trasera en el NIST SP800-90 Dual Ec Prng . Fecha de acceso: 9 de diciembre de 2011. Archivado desde el original el 26 de febrero de 2014. (indefinido)
↑ Error de seguridad de Debian OpenSSL . Consultado el 9 de diciembre de 2011. Archivado desde el original el 6 de septiembre de 2018. (indefinido)

Literatura

La aleatoriedad y el navegador Netscape , Ian Goldberg y David Wagner, Dr. Diario de Dobb , enero de 1996, pp66-70.
Kelsey J. , Schneier B. , Wagner D. A. , Hall C. Cryptanalytic Attacks on Pseudorandom Number Generators // Fast Software Encryption :, FSE' 98 Paris, France, March 23–25, 1998 Proceedings / S Vaudenay - Berlin , Heidelberg , Nueva York, NY , Londres [etc.] : Springer Berlin Heidelberg , 1998. - P. 168-188. - ( Lecture Notes in Computer Science ; Vol. 1372) - ISBN 978-3-540-64265-7 - ISSN 0302-9743 ; 1611-3349 - doi:10.1007/3-540-69710-1_12
Análisis del generador de números aleatorios de Linux Zvi Gutterman, Benny Pinkas y Tzachy Reinman, en IEEE S&P (Oakland Conference), mayo de 2006, págs. 371-385.
Requisitos de aleatoriedad para la seguridad. D. Eastlake, J. Schiller, S. Crocker, RFC 4086 (obsoleta RFC1750), 2006.
Recomendación para la generación de números aleatorios utilizando generadores de bits aleatorios deterministas , Elaine Barker y John Kelsey, NIST Special Publication 800-90. marzo de 2007