stringtranslate.com

Generador de números pseudoaleatorios criptográficamente seguro

Un generador de números pseudoaleatorios criptográficamente seguro ( CSPRNG ) o generador de números pseudoaleatorios criptográficos ( CPRNG ) es un generador de números pseudoaleatorios (PRNG) con propiedades que lo hacen adecuado para su uso en criptografía . También se lo conoce como generador de números aleatorios criptográficos ( CRNG ).

Fondo

La mayoría de las aplicaciones criptográficas requieren números aleatorios , por ejemplo:

La "calidad" de la aleatoriedad requerida para estas aplicaciones varía. Por ejemplo, la creación de un nonce en algunos protocolos solo necesita unicidad. Por otro lado, la generación de una clave maestra requiere una calidad superior, como más entropía . Y en el caso de los blocs de un solo uso , la garantía teórica de la información de un secreto perfecto solo se cumple si el material de la clave proviene de una fuente verdaderamente 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 números con más aleatoriedad que la que puede proporcionar la entropía disponible. Además, los procesos para extraer aleatoriedad de un sistema en ejecución son lentos en la práctica real. En tales casos, a veces se puede utilizar un CSPRNG. Un CSPRNG puede "estirar" la entropía disponible sobre más bits.

Requisitos

Los requisitos de un PRNG ordinario también se cumplen con un PRNG criptográficamente seguro, pero no sucede lo contrario. Los requisitos de CSPRNG se dividen en dos grupos:

  1. Pasan pruebas de aleatoriedad estadística :
    • Todo CSPRNG debe satisfacer la prueba del siguiente bit . Es decir, dados los primeros k bits de una secuencia aleatoria, no existe ningún algoritmo de tiempo polinomial que pueda predecir el bit ( k +1) con una probabilidad de éxito no despreciable mejor que el 50%. [1] Andrew Yao demostró en 1982 que un generador que pase la prueba del siguiente bit pasará todas las demás pruebas estadísticas de tiempo polinomial para determinar su aleatoriedad. [2]
  2. Se mantienen bien ante ataques serios, incluso cuando parte de su estado inicial o de ejecución queda disponible para un atacante: [3]
    • Todo CSPRNG debería resistir "ataques de extensión de compromiso de estado". [3] : 4  En el caso de que se haya revelado parte o la totalidad de su estado (o se haya 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, debería ser inviable utilizar el conocimiento del estado de la entrada para predecir las condiciones futuras del estado del CSPRNG.

Por ejemplo, si el PRNG en cuestión produce una salida calculando bits de pi en secuencia, comenzando desde algún punto desconocido en la expansión binaria, bien podría satisfacer la prueba del siguiente bit y, por lo tanto, ser estadísticamente aleatorio, ya que se supone que pi es un número normal . Sin embargo, este algoritmo no es criptográficamente seguro; un atacante que determine qué bit de pi está en uso actualmente (es decir, el estado del algoritmo) 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 aspectos. En primer lugar, si bien los resultados de la mayoría de los PRNG parecen aleatorios para diversas pruebas estadísticas, no resisten una determinada ingeniería inversa. Se pueden encontrar pruebas estadísticas especializadas especialmente ajustadas a un PRNG de este tipo que muestran que los números aleatorios no son verdaderamente aleatorios. En segundo lugar, para la mayoría de los PRNG, cuando se ha revelado su estado, todos los números aleatorios anteriores se pueden predecir de forma retroactiva, lo que permite a un atacante leer 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 entorno asintótico , una familia de funciones computables en tiempo polinomial determinista para 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 aleatoriedad verdadera, es decir, para cualquier algoritmo de tiempo polinomial probabilístico A , que genera 1 o 0 como diferenciador,

para alguna función despreciable . [4] (La notación significa 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. [5]

Un PRNG seguro hacia delante 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 extensiones de compromiso de estado en el siguiente sentido. Si el estado inicial se elige de manera uniforme al azar de , entonces para cualquier i , la secuencia debe ser computacionalmente indistinguible de , en el que los se eligen de manera uniforme al azar de . [6]

Cualquier PRNG puede convertirse en un PRNG seguro hacia adelante con longitud de bloque dividiendo su salida en el siguiente estado y la salida real. Esto se hace estableciendo , en el que 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 varios flujos de bits con aleatoriedad débil se pueden combinar para producir un flujo de bits cuasialeatorio de mayor calidad. [7] Incluso antes, John von Neumann demostró que un algoritmo simple puede eliminar una cantidad considerable de sesgo en cualquier flujo de bits, [8] que se debe aplicar a cada flujo de bits antes de usar cualquier variación del diseño de Santha-Vazirani.

Diseños

Los diseños CSPRNG se dividen en dos clases:

  1. Diseños basados ​​en primitivos criptográficos como cifrados y hashes criptográficos
  2. Diseños basados ​​en problemas matemáticos que se consideran difíciles

Diseños basados ​​en primitivos criptográficos

Diseños basados ​​en la teoría de números

Esquemas prácticos

Los esquemas CSPRNG "prácticos" no sólo incluyen un algoritmo CSPRNG, sino también una forma de inicializarlo (" sembrarlo ") mientras se mantiene la semilla en secreto. Se han definido varios esquemas de este tipo, entre ellos:

Obviamente, la técnica se puede generalizar fácilmente a cualquier cifrado de bloques; se ha sugerido AES . [18] Si se filtra la clave k , se puede predecir todo el flujo X9.17; esta debilidad se cita como una razón para crear Yarrow. [19]

Todos estos esquemas mencionados anteriormente, excepto X9.17, también mezclan el estado de un CSPRNG con una fuente adicional de entropía. Por lo tanto, no son generadores de números pseudoaleatorios "puros", en el sentido de que la salida no está completamente determinada por su estado inicial. Esta adición tiene como objetivo evitar ataques incluso si el estado inicial se ve comprometido. [a]

Normas

Se han estandarizado varios CSPRNG. Por ejemplo:

Este estándar retirado tiene cuatro PRNG. Dos de ellos no son controvertidos y están probados: CSPRNG llamados Hash_DRBG [22] y HMAC_DRBG. [23]

El tercer PRNG de este estándar, CTR_DRBG , se basa en un cifrador de bloques 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 distinción de ataques que el nivel de seguridad del cifrador de bloques subyacente cuando el número de bits de salida de este PRNG es mayor que dos elevado a la potencia del tamaño de bloque del cifrador de bloques subyacente en bits. [24]

Cuando el número máximo de bits de salida de este PRNG es igual al tamaño de bloque 2 , la salida resultante proporciona el nivel de seguridad matemáticamente esperado que se esperaría que generara el tamaño de la clave, pero se demuestra que la salida no es indistinguible de un verdadero generador de números aleatorios. [24] Cuando el número máximo de bits de salida de este PRNG es menor que él, se proporciona el nivel de seguridad esperado y la salida parece ser indistinguible de un verdadero generador de números aleatorios. [24]

En la próxima revisión se observa que la fortaleza 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]

En esencia, se trata de NIST SP 800-90A con Dual_EC_DRBG eliminado, y es el reemplazo del estándar retirado.

El NIST mantiene una buena referencia . [26]

También existen estándares para pruebas estadísticas de nuevos diseños CSPRNG:

Fallas de seguridad

Puerta trasera cleptográfica de la NSA en el PRNG Dual_EC_DRBG

En 2013, The Guardian y The New York Times informaron de que la Agencia de Seguridad Nacional (NSA) había insertado una puerta trasera en un generador de números pseudoaleatorios (PRNG) del NIST SP 800-90A , que permite a la NSA descifrar fácilmente material cifrado con la ayuda de Dual EC DRBG . Ambos periódicos informaron [28] [29] de que, como sospechaban desde hacía tiempo los expertos en seguridad independientes, [30] la NSA había estado introduciendo debilidades en el estándar CSPRNG 800-90; esto se confirmó por primera vez en uno de los documentos de alto secreto filtrados a The Guardian por Edward Snowden . La NSA trabajó de forma encubierta para conseguir que su propia versión del borrador del estándar de seguridad del NIST fuera aprobada para su uso mundial en 2006. El documento filtrado afirma que "finalmente, la NSA se convirtió en el único editor". A pesar del potencial conocido de una puerta trasera cleptográfica y otras deficiencias significativas conocidas de Dual_EC_DRBG, varias empresas como RSA Security continuaron usando Dual_EC_DRBG hasta que se confirmó la puerta trasera en 2013. [31] RSA Security recibió un pago de 10 millones de dólares de la NSA para hacerlo. [32]

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 use claves codificadas) en WPA2, donde los proveedores de hardware usan una clave semilla codificada para el algoritmo ANSI X9.31 RNG, afirmando que "un atacante puede forzar brutamente los datos cifrados para descubrir el resto de los parámetros de cifrado y deducir la clave de cifrado maestra utilizada para cifrar sesiones web o conexiones de red privada virtual (VPN)". [33] [34]

Máquina de cifrado japonesa PURPLE

Durante la Segunda Guerra Mundial , Japón utilizó una máquina de cifrado para las comunicaciones diplomáticas; Estados Unidos logró descifrarla y leer sus mensajes , principalmente porque los "valores clave" utilizados no eran lo suficientemente aleatorios.

Referencias

  1. ^ El uso de la mezcla de entropía después de la inicialización de CSPRNG ha sido cuestionado por Daniel J. Bernstein . [20]
  1. ^ Katz, Jonathan; Lindell, Yehuda (2008). Introducción a la criptografía moderna. CRC Press. pág. 70. ISBN 978-1584885511.
  2. ^ Andrew Chi-Chih Yao . Teoría y aplicaciones de las funciones de trampilla. En Actas del 23.º Simposio IEEE sobre Fundamentos de la Ciencia de la Computación, 1982.
  3. ^ ab Kelsey, John; Schneier, Bruce; Wagner, David; Hall, Chris (1998). "Ataques criptoanalíticos a generadores de números pseudoaleatorios". Fast Software Encryption (PDF) . Berlín, Heidelberg: Springer Berlin Heidelberg. doi :10.1007/3-540-69710-1_12. ISBN 978-3-540-64265-7. ISSN  0302-9743.
  4. ^ Goldreich, Oded (2001), Fundamentos de criptografía I: Herramientas básicas , Cambridge: Cambridge University Press, ISBN 978-0-511-54689-1, definición 3.3.1.
  5. ^ Goldreich, Oded (2001), Fundamentos de criptografía I: Herramientas básicas , Cambridge: Cambridge University Press, ISBN 978-0-511-54689-1, Teorema 3.3.7.
  6. ^ Dodis, Yevgeniy, Notas de la lección 5 de Introducción a la criptografía (PDF) , consultado el 3 de enero de 2016, definición 4.
  7. ^ Miklos Santha, Umesh V. Vazirani (24 de octubre de 1984). "Generación de secuencias cuasi aleatorias a partir de fuentes ligeramente aleatorias" (PDF) . Actas del 25.º Simposio 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 .
  8. ^ John von Neumann (1 de marzo de 1963). "Varias técnicas para su uso en relación con dígitos aleatorios". The Collected Works of John von Neumann . Pergamon Press . págs. 768–770. ISBN 0-08-009566-6.
  9. ^ 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.
  10. ^ Cox, George; Dike, Charles; Johnston, DJ (2011). "Generador de números aleatorios digitales (DRNG) de Intel" (PDF) .
  11. ^ Bernstein, Daniel J. "2017.07.23: Generadores de números aleatorios con borrado rápido de claves: un esfuerzo por limpiar varios desastres simultáneamente. #rng #forwardsecrecy #urandom #cascade #hmac #rekeying #proofs".
  12. ^ "Commit de Github de random.c". Github. 2 de julio de 2016.
  13. ^ "El generador de números aleatorios de Linux 5.17 experimenta aumentos de velocidad al cambiar de SHA1 a BLAKE2 - Phoronix". www.phoronix.com .
  14. ^ "Registro CVS de arc4random.c". CVS. 1 de octubre de 2013.
  15. ^ "Registro CVS de arc4random.c". CVS. 16 de noviembre de 2014.
  16. ^ "Notas de la versión de FreeBSD 12.0-RELEASE: bibliotecas de ejecución y API". FreeBSD.org . 5 de marzo de 2019 . Consultado el 24 de agosto de 2019 .
  17. ^ Menezes, Alfred ; van Oorschot, Paul ; Vanstone, Scott (1996). "Capítulo 5: Bits y secuencias pseudoaleatorios" (PDF) . Manual de criptografía aplicada. CRC Press.
  18. ^ Young, Adam; Yung, Moti (1 de febrero de 2004). Criptografía maliciosa: exposición de la criptovirología. John Wiley & Sons , sección 3.5.1. ISBN 978-0-7645-4975-5.
  19. ^ Kelsey, John; Schneier, Bruce; Ferguson, Niels (agosto de 1999). "Yarrow-160: Notas sobre el diseño y análisis del generador de números pseudoaleatorios criptográficos Yarrow" (PDF) . Sexto taller anual sobre áreas seleccionadas en criptografía . Notas de clase en informática. Vol. 1758. págs. 13–33. doi :10.1007/3-540-46513-8_2. ISBN. 978-3-540-67185-5.
  20. ^ Daniel J. Bernstein (5 de febrero de 2014). "cr.yp.to: 5 de febrero de 2014: ¡Ataques de entropía!". ¿Existe algún argumento serio que avale que agregar nueva entropía todo el tiempo es algo bueno? La página del manual de Linux /dev/urandom afirma que sin nueva entropía el usuario es "teóricamente vulnerable a un ataque criptográfico", pero (como he mencionado en varios lugares) este es un argumento ridículo.
  21. ^ "FIPS 186-4" (PDF) .
  22. ^ Kan, Wilson (4 de septiembre de 2007). "Análisis de los supuestos subyacentes en los DRBG del NIST" (PDF) . Consultado el 19 de noviembre de 2016 .
  23. ^ 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 .
  24. ^ abc Campagna, Matthew J. (1 de noviembre de 2006). "Límites de seguridad para el generador de bits aleatorios determinístico basado en el libro de códigos del NIST" (PDF) . Consultado el 19 de noviembre de 2016 .
  25. ^ Perlroth, Nicole (10 de septiembre de 2013). "Gobierno anuncia medidas para restablecer la confianza en los estándares de cifrado" . The New York Times . Consultado el 19 de noviembre de 2016 .
  26. ^ División de Seguridad Informática, Laboratorio de Tecnología de la Información (24 de mayo de 2016). "Número aleatorio". CSRC | NIST .
  27. ^ Rukhin, Andrew; Soto, Juan; Nechvatal, James; Smid, Miles; Barker, Elaine; Leigh, Stefan; Levenson, Mark; Vangel, Mark; Banks, David; Heckert, N.; Dray, James; Vo, San; Bassham, Lawrence (30 de abril de 2010). "Un conjunto de pruebas estadísticas para generadores de números aleatorios y pseudoaleatorios para aplicaciones criptográficas". NIST . doi : 10.6028/NIST.SP.800-22r1a – vía csrc.nist.gov.
  28. ^ James Borger; Glenn Greenwald (6 de septiembre de 2013). "Revelado: cómo las agencias de espionaje de Estados Unidos y el Reino Unido derrotan la privacidad y la seguridad en Internet". The Guardian . Consultado el 7 de septiembre de 2013 .
  29. ^ Nicole Perlroth (5 de septiembre de 2013). "NSA Able to Foil Basic Safeguards of Privacy on Web" (La NSA puede frustrar las salvaguardas básicas de la privacidad en la Web). The New York Times . Consultado el 7 de septiembre de 2013 .
  30. ^ Bruce Schneier (15 de noviembre de 2007). "¿La NSA puso una puerta trasera secreta en el nuevo estándar de cifrado?". Wired . Consultado el 7 de septiembre de 2013 .
  31. ^ Matthew Green (20 de septiembre de 2013). "RSA advierte a los desarrolladores que no utilicen los productos de RSA".
  32. ^ Joseph Menn (20 de diciembre de 2013). "Exclusiva: Un contrato secreto vincula a la NSA con un pionero de la industria de la seguridad". Reuters .
  33. ^ Shaanan Cohney; Matthew D. Green ; Nadia Heninger . "Ataques prácticos de recuperación de estado contra implementaciones de RNG heredadas" (PDF) . duhkattack.com .
  34. ^ "Ataque criptográfico DUHK recupera claves de cifrado y expone conexiones VPN". slashdot.org . 25 de octubre de 2017 . Consultado el 25 de octubre de 2017 .

Enlaces externos