Un generador de números pseudoaleatorios criptográficamente seguro ( CSPRNG ) o un generador de números pseudoaleatorios criptográficos ( CPRNG ) [1] es un generador de números pseudoaleatorios (PRNG) con propiedades que lo hacen adecuado para su uso en criptografía . También se conoce libremente como un generador criptográfico de números aleatorios ( CRNG ) (consulte Generación de números aleatorios § "Verdadero" frente a números pseudoaleatorios ). [2] [3]
La mayoría de las aplicaciones criptográficas requieren números aleatorios , por ejemplo:
- generación de claves
- nonces
- sales en ciertos esquemas de firma, incluidos ECDSA , RSASSA-PSS
La "calidad" de la aleatoriedad requerida para estas aplicaciones varía. Por ejemplo, crear un nonce en algunos protocolos solo necesita unicidad. Por otro lado, la generación de una clave maestra requiere una mayor calidad, como más entropía . Y en el caso de los blocs de notas de una sola vez , la garantía teórica de la información de un secreto perfecto solo se mantiene si el material clave proviene de una verdadera fuente aleatoria con alta entropía y, por lo tanto, cualquier tipo de generador de números pseudoaleatorios es insuficiente.
Idealmente, la generación de números aleatorios en CSPRNG utiliza entropía obtenida de una fuente de alta calidad, generalmente la API de aleatoriedad del sistema operativo. Sin embargo, se han encontrado correlaciones inesperadas en varios de estos procesos aparentemente independientes. Desde un punto de vista de la teoría de la información, la cantidad de aleatoriedad, la entropía que se puede generar, es igual a la entropía proporcionada por el sistema. Pero a veces, en situaciones prácticas, se necesitan más números aleatorios que entropía disponible. Además, los procesos para extraer la aleatoriedad de un sistema en ejecución son lentos en la práctica. En tales casos, a veces se puede utilizar un CSPRNG. Un CSPRNG puede "estirar" la entropía disponible en más bits.
Requisitos
Los requisitos de un PRNG ordinario también se satisfacen mediante un PRNG criptográficamente seguro, pero lo contrario no es cierto. Los requisitos de CSPRNG se dividen en dos grupos: primero, que pasan las pruebas estadísticas de aleatoriedad ; y en segundo lugar, que aguantan bien los ataques graves, incluso cuando parte de su estado inicial o de ejecución se vuelve disponible para un atacante. [ cita requerida ]
- Cada CSPRNG debe satisfacer la prueba del siguiente bit . Es decir, dados los primeros k bits de una secuencia aleatoria, no existe un algoritmo de tiempo polinomial que pueda predecir el ( k + 1) -ésimo bit con una probabilidad de éxito no despreciable mejor que el 50%. [4] Andrew Yao demostró en 1982 que un generador que pasa la prueba del siguiente bit pasará todas las demás pruebas estadísticas de tiempo polinómico para determinar la aleatoriedad. [5]
- Cada CSPRNG debe soportar "extensiones de compromiso estatal". En el caso de que una parte o la totalidad de su estado haya sido revelado (o adivinado correctamente), debería ser imposible reconstruir el flujo de números aleatorios antes de la revelación. Además, si hay una entrada de entropía durante la ejecución, no debería ser factible utilizar el conocimiento del estado de la entrada para predecir las condiciones futuras del estado de CSPRNG.
- Ejemplo: si el CSPRNG en consideración produce una salida calculando bits de π en secuencia, comenzando desde algún punto desconocido en la expansión binaria, bien puede satisfacer la prueba del siguiente bit y, por lo tanto, ser estadísticamente aleatorio, ya que π parece ser una secuencia aleatoria. . (Esto estaría garantizado si π es un número normal , por ejemplo). Sin embargo, este algoritmo no es criptográficamente seguro; un atacante que determina qué bit de pi (es decir, el estado del algoritmo) está actualmente en uso también podrá calcular todos los bits anteriores.
La mayoría de los PRNG no son adecuados para su uso como CSPRNG y fallarán en ambos casos. Primero, mientras que la mayoría de los resultados de PRNG parecen aleatorios para una variedad de pruebas estadísticas, no resisten la ingeniería inversa determinada. Se pueden encontrar pruebas estadísticas especializadas especialmente ajustadas a un PRNG que muestra que los números aleatorios no son realmente aleatorios. En segundo lugar, para la mayoría de los PRNG, cuando se ha revelado su estado, todos los números aleatorios pasados se pueden volver a predecir, lo que permite que un atacante lea todos los mensajes pasados, así como los futuros.
Los CSPRNG están diseñados explícitamente para resistir este tipo de criptoanálisis .
Definiciones
En el escenario asintótico , una familia de funciones calculables de tiempo polinomial deterministapara algún polinomio p , es un generador de números pseudoaleatorios ( PRNG , o PRG en algunas referencias), si extiende la longitud de su entrada (para cualquier k ), y si su salida es computacionalmente indistinguible de la verdadera aleatoriedad, es decir, para cualquier algoritmo de tiempo polinomial probabilístico A , que genera 1 o 0 como distintivo,
por alguna función insignificante . [6] (La notaciónsignifica que x se elige uniformemente al azar del conjunto X ).
Existe una caracterización equivalente: Para cualquier familia de funciones , G es un PRNG si y solo si el siguiente bit de salida de G no puede predecirse mediante un algoritmo de tiempo polinomial. [7]
Un PRNG seguro hacia adelante con longitud de bloque es un PRNG , donde la cadena de entrada con longitud k es el estado actual en el período i , y la salida (, ) consiste en el siguiente estado y el bloque de salida pseudoaleatorio del período i , que resiste las extensiones de compromiso estatal en el siguiente sentido. Si el estado inicial se elige uniformemente al azar de , luego para cualquier i , la secuencia debe ser computacionalmente indistinguible de , en el que la son elegidos uniformemente al azar de . [8]
Cualquier PRNG se puede convertir en un PRNG seguro hacia adelante con longitud de bloque dividiendo su salida en el siguiente estado y la salida real. Esto se hace configurando, en el cual y ; entonces G es un PRNG seguro hacia adelante con como el siguiente estado y como el bloque de salida pseudoaleatorio del período actual.
Extracción de entropía
Santha y Vazirani demostraron que se pueden combinar varios flujos de bits con una aleatoriedad débil para producir un flujo de bits cuasialeatorio de mayor calidad. [9] Incluso antes, John von Neumann demostró que un algoritmo simple puede eliminar una cantidad considerable de sesgo en cualquier flujo de bits, [10] que debería aplicarse a cada flujo de bits antes de utilizar cualquier variación del diseño Santha-Vazirani.
Diseños
En la discusión a continuación, los diseños de CSPRNG se dividen en tres clases:
- aquellos basados en primitivas criptográficas como cifrados y hashes criptográficos ,
- aquellos basados en problemas matemáticos que se consideran difíciles, y
- diseños para fines especiales.
El último a menudo introduce entropía adicional cuando está disponible y, estrictamente hablando, no son generadores de números pseudoaleatorios "puros", ya que su salida no está completamente determinada por su estado inicial. Esta adición puede prevenir ataques incluso si el estado inicial está comprometido.
Diseños basados en primitivas criptográficas
- Un cifrado de bloque seguro se puede convertir en un CSPRNG ejecutándolo en modo contador [ dudoso ] . Esto se hace eligiendo una clave aleatoria y encriptando un 0, luego encriptando un 1, luego encriptando un 2, etc. El contador también puede iniciarse en un número arbitrario distinto de cero. Suponiendo un cifrado de bloque de n bits, la salida se puede distinguir de los datos aleatorios después de alrededor de 2 n / 2 bloques, ya que, después del problema del cumpleaños , los bloques en colisión deberían ser probables en ese punto, mientras que un cifrado de bloque en modo CTR nunca generará bloques idénticos. . Para los cifrados de bloques de 64 bits, esto limita el tamaño de salida seguro a unos pocos gigabytes, con bloques de 128 bits, la limitación es lo suficientemente grande como para no afectar las aplicaciones típicas. Sin embargo, cuando se usa solo, no cumple con todos los criterios de un CSPRNG (como se indicó anteriormente) ya que no es fuerte contra las "extensiones de compromiso del estado": con conocimiento del estado (en este caso, un contador y una clave) puede predecir toda la producción pasada.
- Un hash criptográficamente seguro de un contador también podría actuar como un buen CSPRNG en algunos casos. En este caso, también es necesario que el valor inicial de este contador sea aleatorio y secreto. Sin embargo, ha habido poco estudio de estos algoritmos para su uso de esta manera, y al menos algunos autores advierten contra este uso. [ vago ] [11]
- La mayoría de los cifrados de flujo funcionan generando un flujo pseudoaleatorio de bits que se combinan (casi siempre con XOR ) con el texto sin formato ; ejecutar el cifrado en un contador devolverá un nuevo flujo pseudoaleatorio, posiblemente con un período más largo. El cifrado solo puede ser seguro si el flujo original es un buen CSPRNG, aunque este no es necesariamente el caso (consulte el cifrado RC4 ). Nuevamente, el estado inicial debe mantenerse en secreto.
Diseños teóricos de números
- El algoritmo Blum Blum Shub tiene una prueba de seguridad basada en la dificultad del problema de residuosidad cuadrática . Dado que la única forma conocida de resolver ese problema es factorizar el módulo, generalmente se considera que la dificultad de la factorización entera proporciona una prueba de seguridad condicional para el algoritmo Blum Blum Shub. Sin embargo, el algoritmo es muy ineficaz y, por lo tanto, poco práctico a menos que se necesite una seguridad extrema.
- El algoritmo de Blum-Micali tiene una prueba de seguridad basada en la dificultad del problema del logaritmo discreto, pero también es muy ineficiente.
- Daniel Brown de Certicom ha escrito una prueba de seguridad en 2006 para Dual_EC_DRBG , basada en la dureza asumida del supuesto Decisional Diffie-Hellman , el problema del logaritmo x y el problema del punto truncado . La prueba de 2006 asume explícitamente un outlen más bajo [ aclaración necesaria ] que en el estándar Dual_EC_DRBG, y que la P y Q en el estándar Dual_EC_DRBG (que se reveló en 2013 como probablemente respaldada por la NSA) se reemplazan con valores sin respaldo.
Diseños especiales
Hay una serie de PRNG prácticos que se han diseñado para ser criptográficamente seguros, que incluyen
- el algoritmo Milenrama que intenta evaluar la calidad entrópica de sus entradas. Milenrama se usa en macOS y otros sistemas operativos de Apple hasta aproximadamente diciembre de 2019. Apple ha cambiado a Fortuna desde entonces. (Ver / dev / random ).
- el algoritmo ChaCha20 reemplazó a RC4 en OpenBSD (versión 5.4), [12] NetBSD (versión 7.0), [13] y FreeBSD (versión 12.0). [14]
- ChaCha20 también reemplazó a SHA-1 en Linux en la versión 4.8. [15]
- el algoritmo Fortuna , el sucesor de Yarrow, que no intenta evaluar la calidad entrópica de sus entradas. Fortuna se utiliza en FreeBSD. Apple cambió a Fortuna para la mayoría o todos los sistemas operativos de Apple a partir de diciembre de 2019.
- la función CryptGenRandom proporcionada en Microsoft 's de aplicaciones de cifrado de interfaz de programación
- ISAAC basado en una variante del cifrado RC4
- Algoritmo evolutivo basado en NIST Statistical Test Suite. [16] [17]
- arc4random
- AES - CTR DRBG se utiliza a menudo como generador de números aleatorios en sistemas que utilizan cifrado AES. [18] [19]
- Estándar ANSI X9.17 ( Gestión de claves de instituciones financieras (mayorista) ), que también ha sido adoptado como estándar FIPS . Toma como entrada un paquete de claves TDEA ( opción de codificación 2 ) k y (el valor inicial de) una semilla aleatoria s de 64 bits . [20] Cada vez que se requiere un número aleatorio:
- Obtiene la fecha / hora actual D con la máxima resolución posible.
- Calcula un valor temporal t = TDEA k ( D )
- Calcula el valor aleatorio x = TDEA k ( s ⊕ t ) , donde ⊕ denota bit a bit exclusivo o .
- Actualiza la semilla s = TDEA k ( x ⊕ t )
- Obviamente, la técnica se generaliza fácilmente a cualquier cifrado de bloques; Se ha sugerido AES . [21]
Estándares
Se han estandarizado varios CSPRNG. Por ejemplo,
- FIPS 186-4
- NIST SP 800-90A :
- Este estándar retirado tiene cuatro PRNG. Dos de ellos son indiscutibles y probados: los CSPRNG llamados Hash_DRBG [22] y HMAC_DRBG. [23]
- El tercer PRNG de este estándar, CTR DRBG , se basa en un cifrado de bloque que se ejecuta en modo contador . Tiene un diseño no controvertido, pero se ha demostrado que es más débil en términos de ataque distintivo que el nivel de seguridad del cifrado de bloque subyacente cuando el número de bits de salida de este PRNG es mayor que dos a la potencia del tamaño de bloque del cifrado de bloque subyacente. en bits. [24]
- Cuando el número máximo de bits de salida de este PRNG es igual al tamaño de 2 bloques , la salida resultante ofrece el nivel de seguridad matemáticamente esperado que se esperaría que generara el tamaño de la clave, pero se muestra que la salida no es indistinguible de un número aleatorio verdadero. generador. [24] Cuando el número máximo de bits de salida de este PRNG es menor, se entrega el nivel de seguridad esperado y la salida parece ser indistinguible de un verdadero generador de números aleatorios. [24]
- Se observa en la próxima revisión que la fuerza de seguridad declarada para CTR_DRBG depende de limitar el número total de solicitudes de generación y los bits proporcionados por solicitud de generación.
- El cuarto y último PRNG de este estándar se denomina Dual_EC_DRBG . Se ha demostrado que no es criptográficamente seguro y se cree que tiene una puerta trasera cleptográfica de la NSA. [25]
- NIST SP 800-90A Rev.1: Esto es esencialmente NIST SP 800-90A con Dual_EC_DRBG eliminado, y es el reemplazo del estándar retirado.
- ANSI X9.17-1985 Apéndice C
- ANSI X9.31-1998 Apéndice A.2.4
- ANSI X9.62-1998 Anexo A.4, obsoleto por ANSI X9.62-2005, Anexo D (HMAC_DRBG)
NIST mantiene una buena referencia .
También existen estándares para las pruebas estadísticas de los nuevos diseños de CSPRNG:
- Un estadístico de pruebas para aleatorio y generadores de números pseudoaleatorios , Publicación Especial NIST 800-22 .
Puerta trasera cleptográfica de la NSA en Dual_EC_DRBG PRNG
The Guardian y The New York Times informaron en 2013 que la Agencia de Seguridad Nacional (NSA) insertó una puerta trasera en un generador de números pseudoaleatorios (PRNG) de NIST SP 800-90A que permite a la NSA descifrar fácilmente el material cifrado con la ayuda. de Dual_EC_DRBG . Ambos documentos informan [26] [27] que, como los expertos en seguridad independientes sospecharon durante mucho tiempo, [28] la NSA ha estado introduciendo debilidades en el estándar CSPRNG 800-90; esto fue confirmado por primera vez por uno de los documentos ultrasecretos filtrados a The Guardian por Edward Snowden . La NSA trabajó encubiertamente para obtener su propia versión del borrador del estándar de seguridad NIST aprobada para uso mundial en 2006. El documento filtrado afirma que "eventualmente, la NSA se convirtió en el único editor". A pesar del potencial conocido de una puerta trasera cleptográfica y otras deficiencias significativas conocidas con Dual_EC_DRBG, varias empresas como RSA Security continuaron usando Dual_EC_DRBG hasta que se confirmó la puerta trasera en 2013. [29] RSA Security recibió un pago de $ 10 millones de la NSA para hacer entonces. [30]
Fallas de seguridad
Ataque DUHK
El 23 de octubre de 2017, Shaanan Cohney , Matthew Green y Nadia Heninger , criptógrafos de la Universidad de Pensilvania y la Universidad Johns Hopkins, publicaron detalles del ataque DUHK (No utilice claves codificadas) en WPA2, donde los proveedores de hardware utilizan un código codificado. clave semilla para el algoritmo ANSI X9.31 RNG junto con el uso del generador de números aleatorios ANSI X9.31, "un atacante puede utilizar datos encriptados por fuerza bruta para descubrir el resto de los parámetros de encriptación y deducir la clave de encriptación maestra utilizada para cifrar sesiones web o conexiones de red privada virtual (VPN) ". [31] [32]
Máquina de cifrado PÚRPURA japonesa
Durante la Segunda Guerra Mundial , Japón utilizó una máquina de cifrado para las comunicaciones diplomáticas; Estados Unidos pudo descifrarlo y leer sus mensajes , principalmente porque los "valores clave" utilizados no eran lo suficientemente aleatorios.
Referencias
- ^ Huang, Andrew (2003). Hackear la Xbox: Introducción a la ingeniería inversa . No hay series de prensa de almidón. Sin prensa de almidón . pag. 111 . ISBN 9781593270292. Consultado el 24 de octubre de 2013 .
[...] el generador de flujo de claves se [...] puede considerar como un generador de números pseudoaleatorios criptográficos (CPRNG).
- ^ Dufour, Cédric. "Cómo asegurar la entropía y la correcta generación de números aleatorios en máquinas virtuales" . Exoescala .
- ^ "/ dev / random se parece más a / dev / urandom con Linux 5.6 - Phoronix" . www.phoronix.com .
- ^ Katz, Jonathan; Lindell, Yehuda (2008). Introducción a la criptografía moderna . Prensa CRC. pag. 70 . ISBN 978-1584885511.
- ^ Andrew Chi-Chih Yao . Teoría y aplicaciones de las funciones de trampilla . En Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science, 1982.
- ^ Goldreich, Oded (2001), Fundamentos de la criptografía I: Herramientas básicas , Cambridge: Cambridge University Press, ISBN 978-0-511-54689-1, def 3.3.1.
- ^ Goldreich, Oded (2001), Fundamentos de la criptografía I: Herramientas básicas , Cambridge: Cambridge University Press, ISBN 978-0-511-54689-1, Teorema 3.3.7.
- ^ Dodis, Yevgeniy, Lecture 5 Notes of Introduction to Cryptography (PDF) , consultado el 3 de enero de 2016, def 4.
- ^ Miklos Santha, Umesh V. Vazirani (24 de octubre de 1984). "Generación de secuencias cuasialeatorias a partir de fuentes ligeramente aleatorias" (PDF) . Actas del 25º Simposio del IEEE sobre fundamentos de la informática . Universidad de California . págs. 434–440. ISBN 0-8186-0591-X. Consultado el 29 de noviembre de 2006 .
- ^ John von Neumann (1 de marzo de 1963). "Varias técnicas para usar en relación con dígitos aleatorios". Las obras completas de John von Neumann . Pergamon Press . págs. 768–770. ISBN 0-08-009566-6.
- ^ Adam Young, Moti Yung (1 de febrero de 2004). Criptografía maliciosa: exponer la criptovirología . secta 3.2: John Wiley & Sons . pag. 416. ISBN 978-0-7645-4975-5.Mantenimiento de CS1: ubicación ( enlace )
- ^ "Registro CVS de arc4random.c" . CVS. 1 de octubre de 2013.
- ^ "Registro CVS de arc4random.c" . CVS. 16 de noviembre de 2014.
- ^ "Notas de la versión de FreeBSD 12.0-RELEASE: bibliotecas en tiempo de ejecución y API" . FreeBSD.org . 5 de marzo de 2019 . Consultado el 24 de agosto de 2019 .
- ^ "Confirmación de Github de random.c" . Github. 2 de julio de 2016.
- ^ "Un conjunto de pruebas estadísticas para generadores de números aleatorios y pseudoaleatorios para aplicaciones criptográficas" (PDF) . Publicación especial. NIST. Abril de 2010.
- ^ Poorghanad, A .; Sadr, A .; Kashanipour, A. (mayo de 2008). "Generación de números pseudo aleatorios de alta calidad mediante métodos evolutivos" (PDF) . Congreso IEEE sobre Inteligencia y Seguridad Computacional . 9 : 331–335.
- ^ Kleidermacher, David; Kleidermacher, Mike (2012). Seguridad de sistemas integrados: métodos prácticos para el desarrollo de sistemas y software seguros . Elsevier. pag. 256. ISBN 9780123868862.
- ^ Cox, George; Dike, Charles; Johnston, DJ (2011). "Generador de números aleatorios digitales de Intel (DRNG)" (PDF) . Cite journal requiere
|journal=
( ayuda ) - ^ Menezes, Alfred ; van Oorschot, Paul ; Vanstone, Scott (1996). "Capítulo 5: Secuencias y bits pseudoaleatorios" (PDF) . Manual de criptografía aplicada . Prensa CRC.
- ^ Young, Adam; Yung, Moti (1 de febrero de 2004). Criptografía maliciosa: exponer la criptovirología . sección 3.5.1: John Wiley & Sons . ISBN 978-0-7645-4975-5.Mantenimiento de CS1: ubicación ( enlace )
- ^ Kan, Wilson (4 de septiembre de 2007). "Análisis de supuestos subyacentes en NIST DRBG" (PDF) . Consultado el 19 de noviembre de 2016 .
- ^ Ye, Katherine Qinru (abril de 2016). "El notorio PRG: verificación formal del generador de números pseudoaleatorios HMAC-DRBG" (PDF) . Consultado el 19 de noviembre de 2016 .
- ^ a b c Campagna, Matthew J. (1 de noviembre de 2006). "Límites de seguridad para el generador de bits aleatorios determinista basado en el libro de códigos NIST" (PDF) . Consultado el 19 de noviembre de 2016 .
- ^ Perlroth, Nicole (10 de septiembre de 2013). "Gobierno anuncia pasos para restaurar la confianza en los estándares de cifrado" . The New York Times . Consultado el 19 de noviembre de 2016 .
- ^ James Borger; Glenn Greenwald (6 de septiembre de 2013). "Revelado: cómo las agencias de espionaje de EE. UU. Y el Reino Unido derrotan la privacidad y la seguridad de Internet" . The Guardian . The Guardian . Consultado el 7 de septiembre de 2013 .
- ^ Nicole Perlroth (5 de septiembre de 2013). "NSA capaz de frustrar las salvaguardias básicas de la privacidad en la Web" . The New York Times . Consultado el 7 de septiembre de 2013 .
- ^ Bruce Schneier (15 de noviembre de 2007). "¿La NSA puso una puerta trasera secreta en un nuevo estándar de cifrado?" . Cableado . Consultado el 7 de septiembre de 2013 .
- ^ Matthew Green. "RSA advierte a los desarrolladores que no utilicen productos RSA" .
- ^ Joseph Menn (20 de diciembre de 2013). "Exclusivo: contrato secreto vinculado a la NSA y pionero de la industria de la seguridad" . Reuters .
- ^ Shaanan Cohney ; Matthew D. Green ; Nadia Heninger . "Ataques prácticos de recuperación de estado contra implementaciones RNG heredadas" (PDF) . duhkattack.com .
- ^ "DUHK Crypto Attack recupera claves de cifrado, expone conexiones VPN" . slashdot.org . Consultado el 25 de octubre de 2017 .
enlaces externos
- RFC 4086 , Requisitos de aleatoriedad para la seguridad
- "Grupo de entropía" de Java para números aleatorios impredecibles criptográficamente seguros.
- Clase estándar de Java que proporciona un generador de números pseudoaleatorios (PRNG) criptográficamente fuerte.
- Número aleatorio criptográficamente seguro en Windows sin usar CryptoAPI
- Seguridad conjeturada de la curva elíptica RNG ANSI-NIST , Daniel RL Brown, IACR ePrint 2006/117.
- Un análisis de seguridad del generador de números aleatorios de curva elíptica NIST SP 800-90 , Daniel RL Brown y Kristian Gjosteen, IACR ePrint 2007/048. A aparecer en CRYPTO 2007.
- Criptoanálisis del generador pseudoaleatorio de curva elíptica dual , Berry Schoenmakers y Andrey Sidorenko, IACR ePrint 2006/190.
- Generadores pseudoaleatorios eficientes basados en la suposición de DDH , Reza Rezaeian Farashahi y Berry Schoenmakers y Andrey Sidorenko, IACR ePrint 2006/321.
- Análisis del generador de números aleatorios de Linux , Zvi Gutterman y Benny Pinkas y Tzachy Reinman.
- Descarga de documentación y software de NIST Statistical Test Suite.