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 un 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 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.^[1]​ Incluso antes, John von Neumann probó que un algoritmo simple puede remover una cantidad considerable de sesgo de cualquier flujo de bits^[2]​ 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.

Diseños basados en primitivas criptográficas

• Un Cifrador por bloques seguro puede ser convertido a un CSPRNG si se corre en modo conteo. Esto se realiza si se elige una clave al azar y cifrando un 0, después cifrando un 1, después cifrando un 2, etc. El contador puede ser inicializado en un número arbitrario distinto de 0. Obviamente, el periodo va a ser 2ⁿ para un Cifrador de bloques de n-bit; de igual forma, los valores iniciales (ie, clave y «Texto plano») no deben ser conocidos por el atacante, ya que no importando cuan buena sea la construcción de este tipo de CSPRNG, toda su seguridad estará perdida de conocerseo dichos valores.

• Una función de hash segura de un contador también podría ser un buen CSPRNG en algunos casos. Para ello, es necesario que el valor inicial del contador sea aleatorio y secreto. Si el contador es un número de Precisión arbitraria, entonces el CSPRNG podría tener un periodo infinito. Sin embargo, ha habido pocos estudios de estos algoritmos para ser usados de esta forma, y algunos autores aconsejan no usarlo (Young and Yung, Malicious Cryptography, Wiley, 2004, secc. 3.2).

• La mayoría de los Cifradores de flujo trabajan generando un flujo de bits que es combinado (casi siempre es XOReado) con el Texto plano; corriendo el cifrador con un contador que va a retornar un nuevo flujo pseudo-aleatorio, posiblemente de mayor periodo. El cifrador es solo seguro si el flujo original es un buen CSPRNG (que no siempre es el caso: ver cifrador RC4).

Un diseño de este tipo de clase está incluido en el estándar ANSI X9.17 (Financial Institution Key Management (wholesale), en español Manejo de Claves de Instituciones Financieras (mayorista)), y también ha sido adoptado como un estándar FIPS. Trabaja de la siguiente forma:

• entrada: una semilla aleatoria de 64 bit s, y una clave DES k.

cada vez que un número aleatorio es requerido:

• usando la información de hora/fecha actual D (en la máxima resolución disponible), computar I = DES_k (D)
• salida x=DES_k(I xor s), y actualizar la semilla s a DES_k(x xor I)

Se ha sugerido que este algoritmo podría ser improvisado usando AES en vez de DES (Young and Yung, op cit, secc 3.5.1)

Diseños de teoría numérica

• Blum Blum Shub tiene una fuerte, aunque condicional, prueba de seguridad, basada en la dificultad de Factorización de enteros. Sin embargo, las implementaciones son más lentas comparadas con otros diseños.

Diseños especiales

Hay un número de PRNG prácticas que han sido diseñadas para ser criptográficamente seguras, incluyendo:

• El algoritmo de Yarrow que intenta evaluar la calidad de la entropía de sus entradas, y una versión actualizada, Fortuna, que no lo hace
• El archivo especial de UNIX /dev/random
• La función CryptGenRandom de la CryptoAPI de Microsoft
• ISAAC basado en una variante del [RC4|cifrador RC4]]

Estándares

Varios CSPRNG han sido estandarizados. Por ejemplo:

• FIPS 186-2
• (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 (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, (inglés).

Referencias

1. Miklos Santha, Umesh V. Vazirani (1984). «Generating quasi-random sequences from slightly-random sources (inglés)». Proceedings of the 25th IEEE Symposium on Foundations of Computer Science. ISBN 0-8186-0591-X, páginas 434–440. 
2. John von Neumann (1 de marzo de 1963). «Various techniques for use in connection with random digits». The Collected Works of John von Neumann. Pergamon Press. pp.  768-770. ISBN 0-08-009566-6. 

Enlaces externos

• RFC 4086, Randomness Requirements for Security
• Java "entropy pool" for cryptographically-secure unpredictable random numbers.
• 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.

•   Datos: Q1790389