Generador de números pseudoaleatorios criptográficamente seguro

Un generador de números pseudoaleatorios criptográficamente seguro (CSPRNG, del inglés «Cryptographically Secure PseudoRandom Number Generator») es un Generador de números pseudoaleatorios (PRNG) con características que lo hacen adecuado para su uso en criptografía.

Muchos aspectos de la criptografía requieren números aleatorios, por ejemplo:

• Generación de claves
• Nonces
• Sales en ciertos esquemas de firmas, incluyendo ECDSA, RSASSA-PSS.
• Libretas de un solo uso

La «calidad» de aleatoriedad requerida por estas aplicaciones varía. Por ejemplo, crear una nonce en algunos protocolos necesita que solo sea única. En el otro extremo, la generación de una clave maestra requiere tanto una mayor calidad, como una mayor entropía. Y en el caso de Libretas de un solo uso, la garantía teórica del secreto perfecto sólo vale si el material para la clave es obtenido de una fuente realmente aleatoria con alta entropía.

Idealmente, la generación de números aleatorios en un CSPRNG usa entropía obtenida de una fuente de alta calidad, que puede ser un generador de números pseudoaleatorios en hardware o incluso procesos de sistemas impredecibles —aunque se han encontrado correlaciones inesperadas en varios procesos ostensiblemente independientes. Desde un punto de vista teórico, la cantidad de aleatoriedad y la entropía que puede ser generada es igual a la entropía provista por el sistema. Pero, algunas veces —en situaciones prácticas— es necesario mayor cantidad de números aleatorios que la entropía disponible. También, en la práctica, los procesos que extraen aleatoriedad del sistema en marcha son lentos. En tales instancias, un CSPRNG puede ser usado. Un CSPRNG puede «alargar» la entropía disponible sobre más bits.

Cuando toda la entropía que se dispone está disponible antes que la ejecución del algoritmo comience, realmente tenemos un cifrador de flujo. Sin embargo, algunos diseños de criptosistemas permiten el ingreso de entropía durante la ejecución, en cuyo caso no es realmente un cifrador de flujo y por ende no puede ser usado como tal. Por lo tanto, el diseño de CSPRNG y cifradores de flujo están estrechamente relacionados.

Requerimientos

Los requerimientos de un CSPRNG ordinario también satisfacen los de un PRNG, pero no al contrario. Los requerimientos de un CSPRNG caen en dos grupos: primero, que sus propiedades estadísticas sean buenas (pasar pruebas estadísticas de aleatoriedad); y segundo, que puedan salir airosos bajo ataques severos, incluso si parte de su estado inicial o actual estado está disponible a un atacante.

• Todo CSPRNG debe satisfacer la «prueba del siguiente bit». Esta prueba consiste en: Dado los primeros k bits de una secuencia aleatoria, no hay ningún algoritmo de tiempo polinómico que pueda predecir el (k+1)ésimo bit con probabilidad de éxito mayor a 0.5 (50%). Andrew Yao probó en 1982 que un generador que pasa la prueba del siguiente bit va a pasar cualquier otra prueba estadística de aleatoriedad en tiempo polinómico.

• Todo CSPRNG debe soportar «extensiones de compromiso de estado». En caso de que parte o toda la información de su estado ha sido revelado (o adivinado correctamente), debe ser imposible reconstruir un flujo de números aleatorios generados antes de la obtención del estado. Adicionalmente, si hay ingreso de entropía mientras corre, debe ser imposible usar conocimiento del estado de la entrada para predecir futuras condiciones del estado del CSPRNG.

Ejemplo: Si un CSPRNG bajo consideración produce su salida computando los bits de π en secuencia, comenzando desde un punto desconocido de la expansión binaria, puede muy bien satisfacer la prueba del siguiente bit y ser entonces estadísticamente aleatorio, ya que π parece ser una secuencia aleatoria. (Esto estaría garantizado si pi es un número normal, por ejemplo.) Sin embargo, este algoritmo no es criptográficamente seguro; un atacante que determina qué bit de pi está actualmente en uso (i.e. el estado del algoritmo) puede entonces usarlo para calcular todos los bits generados anteriormente.

La mayoría de los PRNGs no son aptos para ser usados como CSPRNG y pueden fallar en ambos ámbitos. Primero, mientras que la mayoría de las salidas de los PRNG parecen ser aleatorias ante pruebas estadísticas clasificadas, no son capaces de resistir ciertos tipos de ingeniería reversa. Pueden encontrarse pruebas estadísticas especializadas —diseñadas específicamente para un cierto PRNG— que evidencian la poca o nula aleatoriedad de los números generados. Segundo, para la mayoría de los PRNG —cuando su estado ha sido revelado— todos los números aleatorios generados anteriormente pueden ser obtenidos, permitiendo a un atacante leer todos los mensajes pasados, como también los futuros.

Los CSPRNG están diseñados explícitamente para resistir este tipo de Criptoanálisis.

Contexto histórico

Santha y Vazirani probaron que varios flujos de bit con aleatoriedad débil pueden ser combinados para producir un flujo de bits quasi-aleatorios de mejor calidad. Incluso antes, John von Neumann probó que un algoritmo simple puede remover una cantidad considerable de sesgo de cualquier flujo de bits que debería ser aplicado a cada flujo de bits antes de usar cualquier variación del diseño de Santha-Vazirani. El campo fue llamado extracción de entropía y es objeto de investigación activa (ej., N Nisan, S Safra, R Shaltiel, A Ta-Shma, C Umans, D Zuckerman).

Diseños

En la discusión de esta sección, los diseños de los CSPRNG son divididos en tres clases:

1. Aquellos basados en Cifrado por bloques.
2. Basados en problemas matemáticos «difíciles».
3. Diseños de propósito especial.

Estándares

Varios CSPRNG han sido estandarizados. Por ejemplo:

• FIPS 186-2
• NIST SP 800-90(Inglés): Hash_DRBG, HMAC_DRBG, CTR_DRBG and Dual EC DRBG.
• ANSI X9.17-1985 Apédice 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)

Una buena referencia (en inglés) es mantenida por el NIST.

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

• A Statistical Test Suite for Random and Pseudorandom Number Generators, NIST Special Publication 800-22(inglés).

Referencias

Enlaces externos

• RFC 4086, Randomness Requirements for Security
• Java "entropy pool" for cryptographically-secure unpredictable random numbers. Archivado el 2 de diciembre de 2008 en Wayback Machine.
• Cryptographically Secure Random number on Windows without using CryptoAPI
• Conjectured Security of the ANSI-NIST Elliptic Curve RNG, Daniel R. L. Brown, IACR ePrint 2006/117.
• A Security Analysis of the NIST SP 800-90 Elliptic Curve Random Number Generator, Daniel R. L. Brown and Kristian Gjosteen, IACR ePrint 2007/048. To appear in CRYPTO 2007.
• Cryptanalysis of the Dual Elliptic Curve Pseudorandom Generator, Berry Schoenmakers and Andrey Sidorenko, IACR ePrint 2006/190.
• Efficient Pseudorandom Generators Based on the DDH Assumption, Reza Rezaeian Farashahi and Berry Schoenmakers and Andrey Sidorenko, IACR ePrint 2006/321.
• Analysis of the Linux Random Number Generator, Zvi Gutterman and Benny Pinkas and Tzachy Reinman.