encryption - tipos - sorteo aleatorio
¿Cómo funciona un generador de números aleatorios criptográficamente seguro? (5)
Cada generador usará su propia estrategia de siembra, pero aquí hay un poco de la documentación de la API de Windows en CryptGenRandom
Con los CSP de Microsoft, CryptGenRandom usa el mismo generador de números aleatorios utilizado por otros componentes de seguridad. Esto permite que numerosos procesos contribuyan a una semilla de todo el sistema. CryptoAPI almacena una semilla aleatoria intermedia con cada usuario. Para formar la semilla para el generador de números aleatorios, una aplicación llamante proporciona los bits que podría tener, por ejemplo, entrada de temporización del mouse o del teclado, que se combinan con la semilla almacenada y varios datos del sistema y datos del usuario como el ID del proceso y ID de hilo, el reloj del sistema, la hora del sistema, el contador del sistema, el estado de la memoria, los clústeres de discos libres, el bloque del entorno de usuario hash. Este resultado se usa para inicializar el generador de números pseudoaleatorios (PRNG).
En Windows Vista con Service Pack 1 (SP1) y posterior, se utiliza una implementación del PRNG basado en el modo AES especificado en la publicación especial NIST 800-90. En Windows Vista, Windows Storage Server 2003 y Windows XP, se utiliza el PRNG especificado en Federal Information Processing Standard (FIPS) 186-2. Si una aplicación tiene acceso a una buena fuente aleatoria, puede llenar el búfer pbBuffer con algunos datos aleatorios antes de llamar a CryptGenRandom. El CSP luego usa estos datos para aleatorizar aún más su semilla interna. Es aceptable omitir el paso de inicialización del búfer pbBuffer antes de llamar a CryptGenRandom.
Entiendo cómo funcionan los generadores de números aleatorios estándar. Pero cuando se trabaja con criptografía, los números aleatorios realmente tienen que ser aleatorios.
Sé que hay instrumentos que leen el ruido blanco cósmico para ayudar a generar hashes seguros, pero su PC estándar no tiene esto.
¿Cómo obtiene un generador de números aleatorios criptográficamente seguro sus valores sin patrones repetibles?
En primer lugar, el objetivo de un PRNG criptográficamente seguro no es generar secuencias totalmente impredecibles. Como ha notado, la ausencia de algo que genere grandes volúmenes de (más o menos) verdadera aleatoriedad 1 lo hace imposible.
Entonces recurres a algo que es difícil de predecir. "Difícil" significa aquí que lleva un tiempo insoportablemente largo en el que lo que fuera necesario sería obsoleto de todos modos. Hay una serie de algoritmos matemáticos que desempeñan un papel en esto: puede echarle un vistazo si toma algunos CSPRNG conocidos y observa cómo funcionan.
Las variantes más comunes para construir un PRNG son:
- Usando un cifrado de flujo, que ya genera una secuencia de bits pseudoaleatoria (supuestamente segura).
- Usar un cifrado de bloque en modo contador
Las funciones hash en un contador también se usan a veces. Wikipedia tiene más información sobre esto .
Los requisitos generales son simplemente que no es factible determinar el vector de inicialización original a partir del flujo de bits de un generador y que el próximo bit no puede predecirse fácilmente.
En cuanto a la inicialización, la mayoría de los CSPRNG usan varias fuentes disponibles en el sistema, que van desde cosas realmente aleatorias como ruido de línea, interrupciones u otros eventos en el sistema, hasta otras cosas, como ciertas ubicaciones de memoria, & c. El vector de inicialización es preferiblemente muy aleatorio y no depende de un algoritmo matemático. Esta inicialización se interrumpió durante un tiempo en la implementación de OpenSSL de Debian, lo que ocasionó graves problemas de seguridad.
1 Lo cual también tiene sus problemas y hay que tener cuidado al eliminar el sesgo, ya que elementos como el ruido térmico tienen diferentes características dependiendo de la temperatura: casi siempre se tienen prejuicios y es necesario eliminarlos. Y esa no es una tarea trivial en sí misma.
Para fines criptográficos, lo que se necesita es que la secuencia sea "computacionalmente indistinguible de bits uniformemente aleatorios". "Computacionalmente" significa que no necesita ser verdaderamente aleatorio, solo que lo parece a cualquiera sin acceso a la computadora de Dios.
En la práctica, esto significa que el sistema primero debe reunir una secuencia de n bits verdaderamente aleatorios. n será lo suficientemente grande como para frustrar la búsqueda exhaustiva, es decir, no será factible probar las 2 ^ n combinaciones de n bits. Esto se logra, con respecto a la tecnología actual, siempre que n sea mayor que 90 o algo así, pero los criptógrafos simplemente aman los poderes de dos, por lo que es costumbre usar n = 128 .
Estos n bits aleatorios se obtienen reuniendo "eventos físicos" que deberían ser impredecibles, en lo que respecta a la física. Por lo general, se usa el tiempo: la CPU tiene un contador de ciclos que se actualiza varios miles de millones de veces por segundo, y algunos eventos ocurren con una cantidad inevitable de fluctuación de fase (paquetes de red entrante, movimientos del mouse, pulsaciones de tecla ...). El sistema codifica estos eventos y luego los "comprime" aplicando una función hash criptográficamente segura como SHA-256 (la salida se trunca para producir nuestros n bits). Lo que importa aquí es que la codificación de los eventos físicos tiene suficiente entropía : en términos generales, dichos eventos podrían haber asumido colectivamente al menos 2 ^ n combinaciones. La función hash, por definición, debería hacer un buen trabajo al concentrar esa entropía en una cadena de n bits.
Una vez que tenemos n bits, usamos un PRNG (Generador de números pseudoaleatorios) para generar tantos bits como sea necesario. Se dice que un PRNG es criptográficamente seguro si, suponiendo que opere sobre una clave n -bit desconocida lo suficientemente amplia, su salida no se puede distinguir computacionalmente de bits uniformemente aleatorios. En los años 90, una elección popular fue RC4 , que es muy simple de implementar y bastante rápido. Sin embargo, resultó tener sesgos mensurables, es decir, no era tan indistinguible como se deseó inicialmente. El proyecto eSTREAM consistió en recopilar diseños más nuevos para PRNG (en realidad codificadores de flujo, porque la mayoría de los cifrados de flujo consisten en un PRNG, cuya salida está codificada por XOR con los datos para encriptar), documentándolos y promoviendo el análisis por criptógrafos. La Cartera eSTREAM contiene siete diseños de PRNG que se consideraron suficientemente seguros (es decir, resistieron el análisis y los criptógrafos tienden a tener una buena comprensión de por qué resistieron). Entre ellos, cuatro están "optimizados para software". La buena noticia es que si bien estos nuevos PRNG parecen ser mucho más seguros que RC4, también son notablemente más rápidos (estamos hablando de cientos de megabytes por segundo, aquí). Tres de ellos son "gratuitos para cualquier uso" y se proporciona el código fuente.
Desde el punto de vista del diseño, PRNG reutiliza gran parte de los elementos de las cifras cifradas. Se usan los mismos conceptos de avalancha y difusión de bits en un estado interno amplio. Alternativamente, se puede construir un PRNG decente a partir de un cifrado de bloques: simplemente use la secuencia de n bits como clave en un cifrado de bloques, y encripte los valores sucesivos de un contador (expresado como una secuencia mbit, si el cifrado por bloques usa m ) bloques de bits). Esto produce una secuencia pseudoaleatoria de bits que es computacionalmente indistinguible de aleatorio, siempre que el cifrado de bloque sea seguro, y la secuencia producida no exceda de m * 2 ^ (m / 2) bits (para m = 128 , esto significa alrededor de 300 mil millones de gigabytes, por lo que es lo suficientemente grande para la mayoría de los propósitos). Ese tipo de uso se conoce como modo de contador (CTR) .
Generalmente, un cifrado de bloque en modo CTR no es tan rápido como un cifrado de flujo dedicado (el punto del cifrado de flujo es que, al perder la flexibilidad de un cifrado de bloque, se espera un mejor rendimiento). Sin embargo, si tienes una de las CPU más recientes de Intel con las instrucciones AES-NI (que básicamente son una implementación de AES en hardware, integrada en la CPU), entonces el modo AES con CTR producirá una velocidad inigualable (varios gigabytes por segundo).
Para que un generador de números aleatorios se considere criptográficamente seguro , necesita ser seguro contra el ataque de un adversario que conoce el algoritmo y un (gran) número de bits previamente generados. Lo que esto significa es que alguien con esa información no puede reconstruir el estado interno oculto del generador y dar predicciones de qué serán los siguientes bits producidos con una precisión superior al 50%.
Los generadores de números pseudoaleatorios normales generalmente no son criptográficamente seguros, ya que reconstruir el estado interno de los bits de salida anteriores es generalmente trivial (a menudo, el estado interno completo es solo los últimos N bits producidos directamente). Cualquier generador de números aleatorios sin buenas propiedades estadísticas tampoco es criptográficamente seguro, ya que su salida es al menos predecible incluso sin conocer el estado interno.
Entonces, en cuanto a cómo funcionan, cualquier buen sistema criptográfico puede usarse como un generador de números aleatorios criptográficamente seguro: use el sistema criptográfico para cifrar la salida de un generador de números aleatorios "normal". Como un adversario no puede reconstruir la salida de texto sin formato del generador de números aleatorios normal, no puede atacarlo directamente. Esta es una definición algo circular que plantea la cuestión de cómo clave el sistema criptográfico para mantenerlo seguro, que es un problema completamente distinto.
Un generador de número aleatorio criptográficamente seguro, como puede usar para generar claves de cifrado, funciona reuniendo entropía, es decir, entrada impredecible, de una fuente que otras personas no pueden observar.
Por ejemplo, / dev / random (4) en Linux recoge información de la variación en el tiempo de las interrupciones de hardware de fuentes tales como discos duros que devuelven datos, pulsaciones de teclas y paquetes de red entrantes. Este enfoque es seguro siempre que el núcleo no sobreestime la cantidad de entropía que ha recolectado. Hace unos años, las estimaciones de entropía de las distintas fuentes se redujeron, haciéndolas mucho más conservadoras. Aquí hay una explicación de cómo Linux calcula la entropía .
Ninguno de los anteriores es particularmente alto rendimiento. / dev / random (4) probablemente sea seguro, pero mantiene esa seguridad al negarse a dar datos una vez que no puede estar seguro de que esos datos sean aleatorios. Si quiere, por ejemplo, generar muchas claves criptográficas y nonces, entonces probablemente quiera recurrir a generadores de números aleatorios de hardware.
A menudo, los RNG de hardware están diseñados para tomar muestras de la diferencia entre un par de osciladores que se ejecutan casi a la misma velocidad, pero cuyas tasas varían ligeramente según el ruido térmico. Si mal no recuerdo, el generador de números aleatorios que se utiliza para la lotería de bonos premium del Reino Unido, ERNIE, funciona de esta manera.
Los esquemas alternativos incluyen muestrear el ruido en un CCD (ver lavaRND ), desintegración radiactiva (ver hotbits ) o ruido atmosférico (ver random.org , o simplemente conectar una radio AM sintonizada en algún lugar que no sea una estación en tu tarjeta de sonido). O puede pedir directamente al usuario de la computadora que golpee su teclado como un chimpancé loco por un minuto, lo que sea que flote su bote.
Disculpas por la falta de enlaces en línea, pero aparentemente tengo que grabar más de mi vida en este sitio web antes de poder publicar más.
EDITAR: asegura eso. Debido a que algunas personas fueron tan amables con esta bolsa de huesos para hacer clic en esa cosa hacia arriba, puntiaguda, a la izquierda, aparentemente me permitieron poner el resto de los enlaces ahora. ¡Gracias gente amable! ^ _ ^
EDITAR: como señaló andras, solo pensé en hablar sobre algunos de los esquemas de entropía más comunes. La respuesta de Thomas Pornin y la respuesta de Johannes Rössel hacen un buen trabajo explicando cómo se puede tratar de destruir la entropía reunida para volver a repartir partes de ella.