Generador de números aleatorios de hardware - Hardware random number generator

Esta tarjeta de computadora aceleradora de TLS utiliza un generador de números aleatorios de hardware para generar claves criptográficas para cifrar los datos enviados a través de redes de computadoras.

En informática , un generador de números aleatorios por hardware ( HRNG ) o un generador de números aleatorios verdaderos ( TRNG ) es un dispositivo que genera números aleatorios a partir de un proceso físico , en lugar de mediante un algoritmo . Estos dispositivos a menudo se basan en fenómenos microscópicos que generan señales de " ruido " estadísticamente aleatorias de bajo nivel, como el ruido térmico , el efecto fotoeléctrico , que involucra un divisor de haz y otros fenómenos cuánticos . Estos procesos estocásticos son, en teoría, completamente impredecibles mientras una ecuación que gobierne tales fenómenos sea desconocida o incontestable, y las afirmaciones de imprevisibilidad de la teoría estén sujetas a pruebas experimentales . Esto contrasta con el paradigma de generación de números pseudoaleatorios comúnmente implementado en programas de computadora .

Un generador de números aleatorios de hardware generalmente consiste en un transductor para convertir algún aspecto de los fenómenos físicos en una señal eléctrica, un amplificador y otros circuitos electrónicos para aumentar la amplitud de las fluctuaciones aleatorias a un nivel medible y algún tipo de analógico a convertidor digital para convertir la salida en un número digital, a menudo un simple dígito binario 0 o 1. Al muestrear repetidamente la señal que varía aleatoriamente, se obtiene una serie de números aleatorios.

La principal aplicación de los generadores de números aleatorios de hardware electrónico es la criptografía , donde se utilizan para generar claves criptográficas aleatorias para transmitir datos de forma segura. Se utilizan ampliamente en protocolos de cifrado de Internet como Transport Layer Security (TLS).

Los generadores de números aleatorios también se pueden construir a partir de procesos macroscópicos "aleatorios", utilizando dispositivos como el lanzamiento de monedas , los dados , las ruedas de la ruleta y las máquinas de lotería . La presencia de imprevisibilidad en estos fenómenos puede justificarse por la teoría de los sistemas dinámicos inestables y la teoría del caos . Aunque los procesos macroscópicos son deterministas bajo la mecánica newtoniana , el resultado de un dispositivo bien diseñado como una rueda de ruleta no se puede predecir en la práctica, porque depende de los microdetalles sensibles de las condiciones iniciales de cada uso.

Aunque los dados se han utilizado principalmente en los juegos de azar y como elementos "aleatorios" en los juegos (por ejemplo, juegos de rol ), el científico victoriano Francis Galton describió una forma de utilizar los dados para generar explícitamente números aleatorios con fines científicos en 1890.

Los generadores de números aleatorios de hardware generalmente producen solo un número limitado de bits aleatorios por segundo. Con el fin de aumentar la tasa de datos de salida disponibles, a menudo se utilizan para generar la " semilla " para un generador de números pseudoaleatorios criptográficamente seguro más rápido , que luego genera una secuencia de salida pseudoaleatoria a una tasa de datos mucho más alta.

Usos

Los números aleatorios impredecibles se investigaron por primera vez en el contexto de los juegos de azar , y muchos dispositivos aleatorios, como dados , barajar cartas y ruedas de ruleta , se desarrollaron por primera vez para tal uso. Los números aleatorios producidos de manera justa son vitales para los juegos de azar electrónicos y las formas de crearlos a veces están reguladas por comisiones gubernamentales de juegos.

Los números aleatorios también se utilizan para fines no relacionados con los juegos de azar, tanto cuando su uso es matemáticamente importante, como el muestreo para las encuestas de opinión , como en situaciones en las que la equidad se aproxima mediante la aleatorización , como las loterías de reclutamiento militar y la selección de jurados .

Criptografía

El uso principal de los generadores de números aleatorios de hardware está en el campo del cifrado de datos , por ejemplo, para crear claves criptográficas aleatorias y nonces necesarios para cifrar y firmar datos. Son una alternativa más segura a los generadores de números pseudoaleatorios (PRNG), programas de software comúnmente utilizados en computadoras para generar números "aleatorios". Los PRNG utilizan un algoritmo determinista para producir secuencias numéricas. Aunque estas secuencias pseudoaleatorias pasan las pruebas de patrones estadísticos de aleatoriedad , al conocer el algoritmo y las condiciones utilizadas para inicializarlo, llamado "semilla", se puede predecir la salida. Debido a que la secuencia de números producida por un PRNG es en principio predecible, los datos cifrados con números pseudoaleatorios son potencialmente vulnerables al criptoanálisis . Los generadores de números aleatorios de hardware producen secuencias de números que se supone que no son predecibles y, por lo tanto, brindan la mayor seguridad cuando se utilizan para cifrar datos.

Trabajo temprano

Una forma temprana de producir números aleatorios fue mediante una variación de las mismas máquinas utilizadas para jugar al keno o seleccionar números de lotería . Estos involucraron pelotas de ping-pong numeradas mezcladas con aire soplado, quizás combinado con agitación mecánica, y usaron algún método para retirar las pelotas de la cámara de mezcla ( Patente de Estados Unidos 4.786.056 ). Este método da resultados razonables en algunos sentidos, pero los números aleatorios generados por este medio son costosos. El método es inherentemente lento y no se puede utilizar para la mayoría de las aplicaciones informáticas.

El 29 de abril de 1947, RAND Corporation comenzó a generar dígitos aleatorios con una "rueda de ruleta electrónica", que constaba de una fuente de pulsos de frecuencia aleatoria de aproximadamente 100.000 pulsos por segundo cerrada una vez por segundo con un pulso de frecuencia constante y alimentada a un contador binario de cinco bits. . Douglas Aircraft construyó el equipo, la aplicación de la sugerencia de Cecil Hasting (RAND P-113) para una fuente de ruido (lo más probable el comportamiento conocido del gas en miniatura 6D4 thyratron tubo, cuando se coloca en un campo magnético). Veinte de los 32 posibles valores del contador se asignaron a los 10 dígitos decimales y los otros 12 valores del contador se descartaron.

Los resultados de una larga ejecución de la máquina RAND, filtrados y probados, se convirtieron en una tabla, que se publicó en 1955 en el libro A Million Random Digits with 100,000 Normal Deviates . La tabla RAND fue un avance significativo en la entrega de números aleatorios porque nunca antes había estado disponible una tabla tan grande y cuidadosamente preparada. Ha sido una fuente útil para simulaciones, modelado y para derivar las constantes arbitrarias en algoritmos criptográficos para demostrar que las constantes no se seleccionaron maliciosamente. Los cifrados en bloque Khufu y Khafre se encuentran entre las aplicaciones que utilizan la tabla RAND. Ver: Nada bajo mis números de la manga .

Fenómenos físicos con propiedades aleatorias.

Propiedades cuánticas aleatorias

Hay dos fuentes fundamentales de aleatoriedad física de la mecánica cuántica práctica : la mecánica cuántica a nivel atómico o subatómico y el ruido térmico (algunos de los cuales son de origen mecánico cuántico). La mecánica cuántica predice que ciertos fenómenos físicos, como la desintegración nuclear de los átomos, son fundamentalmente aleatorios y, en principio, no pueden predecirse (para un análisis de la verificación empírica de la imprevisibilidad cuántica, consulte los experimentos de prueba de Bell ). Y, debido a que el mundo existe a una temperatura superior al cero absoluto , cada sistema tiene alguna variación aleatoria en su estado; por ejemplo, las moléculas de gases que componen el aire rebotan constantemente entre sí de forma aleatoria ( ver mecánica estadística ). Esta aleatoriedad es también un fenómeno cuántico ( ver fonón ).

Debido a que el resultado de los eventos de la mecánica cuántica no se puede predecir ni siquiera en principio, son el " estándar de oro " para la generación de números aleatorios. Algunos fenómenos cuánticos utilizados para la generación de números aleatorios incluyen:

Propiedades aleatorias clásicas

Los fenómenos térmicos son más fáciles de detectar. Son algo vulnerables al ataque al bajar la temperatura del sistema, aunque la mayoría de los sistemas dejarán de funcionar a temperaturas lo suficientemente bajas como para reducir el ruido en un factor de dos (por ejemplo, ~ 150 K). Algunos de los fenómenos térmicos utilizados incluyen:

En ausencia de efectos cuánticos o ruido térmico, se pueden utilizar otros fenómenos que tienden a ser aleatorios, aunque de formas que no se caracterizan fácilmente por las leyes de la física. Cuando varias de estas fuentes se combinan cuidadosamente (como en, por ejemplo, el algoritmo Yarrow o Fortuna CSPRNG ), se puede recopilar suficiente entropía para la creación de claves criptográficas y nonces , aunque generalmente a tasas restringidas. La ventaja es que este enfoque no necesita, en principio, hardware especial. La desventaja es que un atacante suficientemente informado puede modificar subrepticiamente el software o sus entradas, reduciendo así la aleatoriedad de la salida, quizás sustancialmente. La fuente principal de aleatoriedad que se usa típicamente en tales enfoques es la sincronización precisa de las interrupciones causadas por dispositivos mecánicos de entrada / salida, como teclados y unidades de disco , varios contadores de información del sistema, etc.

Este último enfoque debe implementarse con cuidado y puede estar sujeto a ataques si no lo es. Por ejemplo, la seguridad de avance del generador en el kernel de Linux 2.6.10 podría romperse con una complejidad de tiempo de 2 64 o 2 96 .

Desviación del reloj

Otro fenómeno físico variable que es fácil de medir es la deriva del reloj. Hay varias formas de medir y utilizar la deriva del reloj como fuente de aleatoriedad.

El chip Intel 82802 Firmware Hub (FWH) incluía un RNG de hardware que usaba dos osciladores de ejecución libre, uno rápido y otro lento. Se utiliza una fuente de ruido térmico (ruido de modo no común de dos diodos) para modular la frecuencia del oscilador lento, que luego activa una medición del oscilador rápido. Luego, esa salida se desvanece mediante un paso de descorrelación de tipo von Neumann (ver más abajo). La tasa de salida de este dispositivo es algo menos de 100.000 bit / s. Este chip era un componente opcional de la familia de chipsets 840 que admitía un bus Intel anterior. No está incluido en las PC modernas.

Todos los microprocesadores VIA C3 han incluido un RNG de hardware en el chip del procesador desde 2003. En lugar de utilizar ruido térmico, los bits sin procesar se generan mediante el uso de cuatro osciladores de funcionamiento libre que están diseñados para funcionar a diferentes velocidades. La salida de dos se aplica mediante XOR para controlar la polarización en un tercer oscilador, cuya salida sincroniza la salida del cuarto oscilador para producir el bit en bruto. Las variaciones menores en la temperatura, las características del silicio y las condiciones eléctricas locales provocan variaciones continuas de la velocidad del oscilador y, por lo tanto, producen la entropía de los bits sin procesar. Para garantizar aún más la aleatoriedad, en realidad hay dos RNG de este tipo en cada chip, cada uno colocado en diferentes entornos y girado sobre el silicio. El resultado final es una combinación de estos dos generadores. La tasa de salida bruta es de decenas a cientos de megabits por segundo, y la tasa de blanqueamiento es de unos pocos megabits por segundo. El software del usuario puede acceder al flujo de bits aleatorio generado utilizando nuevas instrucciones en lenguaje de máquina sin privilegios.

Una implementación de software de una idea relacionada en hardware ordinario se incluye en CryptoLib, una biblioteca de rutinas criptográficas. El algoritmo se llama truerand . La mayoría de las computadoras modernas tienen dos osciladores de cristal, uno para el reloj de tiempo real y otro para el reloj de la CPU principal; truerand explota este hecho. Utiliza un servicio de sistema operativo que establece una alarma y se ejecuta fuera del reloj en tiempo real. Una subrutina configura esa alarma para que suene en un tic del reloj (generalmente 1/60 de segundo). Luego, otro entra en un bucle while esperando a que se dispare la alarma. Dado que la alarma no siempre se activará exactamente en un tic, los bits menos significativos de un recuento de iteraciones de bucle, entre el establecimiento de la alarma y su activación, variarán aleatoriamente, posiblemente lo suficiente para algunos usos. Truerand no requiere hardware adicional, pero en un sistema multitarea se debe tener mucho cuidado para evitar interferencias no aleatorias de otros procesos (p. Ej., En la suspensión del proceso de ciclo de conteo cuando el programador del sistema operativo inicia y detiene diversos procesos). ).

El RDRANDcódigo de operación devolverá valores de un generador de números aleatorios de hardware integrado. Está presente en los procesadores Intel Ivy Bridge y los procesadores AMD64 desde 2015.

Lidiando con el sesgo

El flujo de bits de tales sistemas tiende a estar sesgado, con predominio de unos o ceros. Hay dos enfoques para lidiar con el sesgo y otros artefactos. El primero es diseñar el RNG para minimizar el sesgo inherente al funcionamiento del generador. Un método para corregir esto retroalimenta el flujo de bits generado, filtrado por un filtro de paso bajo, para ajustar la polarización del generador. Según el teorema del límite central , el circuito de retroalimentación tenderá a estar bien ajustado " casi todo el tiempo ". Los generadores de números aleatorios de velocidad ultrarrápida suelen utilizar este método. Incluso entonces, los números generados suelen estar algo sesgados.

Blanqueamiento de software

Un segundo enfoque para hacer frente al sesgo es reducirlo después de la generación (en software o hardware). Existen varias técnicas para reducir el sesgo y la correlación, a menudo llamadas algoritmos de " blanqueamiento ", por analogía con el problema relacionado de producir ruido blanco a partir de una señal correlacionada.

John von Neumann inventó un algoritmo simple para corregir un sesgo simple y reducir la correlación. Considera dos bits a la vez (no superpuestos), tomando una de tres acciones: cuando dos bits sucesivos son iguales, se descartan; una secuencia de 1,0 se convierte en 1; y una secuencia de 0,1 se convierte en cero. Por tanto, representa un flanco descendente con un 1 y un flanco ascendente con un 0. Esto elimina el sesgo simple y es fácil de implementar como un programa de computadora o en lógica digital. Esta técnica funciona independientemente de cómo se hayan generado los bits. Sin embargo, no puede asegurar la aleatoriedad en su salida. Lo que puede hacer (con un número significativo de bits descartados) es transformar un flujo de bits aleatorio sesgado en uno no sesgado.

Otra técnica para mejorar un flujo de bits casi aleatorio es el flujo de bits exclusivo o con la salida de un generador de números pseudoaleatorios criptográficamente seguro de alta calidad como Blum Blum Shub o un cifrado de flujo fuerte . Esto puede mejorar la descorrelación y el sesgo de dígitos a bajo costo; se puede realizar mediante hardware, como una FPGA, que es más rápido que hacerlo mediante software.

Un método relacionado que reduce el sesgo en un flujo de bits casi aleatorio es tomar dos o más flujos de bits casi aleatorios no correlacionados y excluirlos juntos. Sea 1/2 + e la probabilidad de que un flujo de bits produzca un 0  , donde −1/2 ≤  e  ≤ 1/2. Entonces e es el sesgo del flujo de bits. Si dos trenes de bits no correlacionados con sesgo e son exclusivos o ed juntos, entonces el sesgo del resultado será 2 e 2 . Esto puede repetirse con más flujos de bits (consulte también el lema de acumulación ).

Algunos diseños aplican funciones hash criptográficas como MD5 , SHA-1 o RIPEMD-160 o incluso una función CRC a todo o parte del flujo de bits, y luego utilizan la salida como flujo de bits aleatorio. Esto es atractivo, en parte porque es relativamente rápido.

Se pueden utilizar muchos fenómenos físicos para generar bits que están muy sesgados, pero cada bit es independiente de los demás. Un contador Geiger (con un tiempo de muestra mayor que el tiempo de recuperación del tubo) o un detector de fotones espejo semitransparente generan flujos de bits que son en su mayoría "0" (silencioso o transmisión) con el "1" ocasional (clic o reflexión). Si cada bit es independiente de los demás, la estrategia de Von Neumann genera un bit de salida no sesgado aleatorio para cada uno de los raros "1" bits en un flujo de bits tan sesgado. Las técnicas de blanqueamiento como la estrategia avanzada de niveles múltiples (AMLS) pueden extraer más bits de salida (bits de salida que son igualmente aleatorios e insesgados) de un flujo de bits tan sesgado.

PRNG con clave aleatoria actualizada periódicamente

Otros diseños utilizan lo que se cree que son verdaderos bits aleatorios como clave para un algoritmo de cifrado de bloques de alta calidad , tomando la salida cifrada como el flujo de bits aleatorio. Sin embargo, se debe tener cuidado en estos casos para seleccionar un modo de bloqueo apropiado . En algunas implementaciones, el PRNG se ejecuta para un número limitado de dígitos, mientras que el dispositivo de generación de hardware produce una nueva semilla.

Usando eventos observados

Los ingenieros de software sin verdaderos generadores de números aleatorios a menudo intentan desarrollarlos midiendo los eventos físicos disponibles para el software. Un ejemplo es medir el tiempo entre las pulsaciones de teclas del usuario y luego tomar el bit menos significativo (o dos o tres) del recuento como un dígito aleatorio. Un enfoque similar mide la programación de tareas, los accesos a la red, los tiempos de búsqueda del cabezal de disco y otros eventos internos. Un diseño de Microsoft incluye una lista muy larga de dichos valores internos, una forma de generador de números pseudoaleatorios criptográficamente seguro . Las lámparas de lava también se han utilizado como dispositivos físicos a monitorear, como en el sistema Lavarand .

El método es arriesgado cuando utiliza eventos controlados por computadora porque un atacante inteligente y malintencionado podría predecir una clave criptográfica controlando los eventos externos. También es riesgoso porque el supuesto evento generado por el usuario (por ejemplo, pulsaciones de teclas) puede ser falsificado por un atacante suficientemente ingenioso, lo que permite el control de los "valores aleatorios" utilizados por la criptografía.

Sin embargo, con suficiente cuidado, se puede diseñar un sistema que produzca números aleatorios criptográficamente seguros a partir de las fuentes de aleatoriedad disponibles en una computadora moderna. El diseño básico es mantener una "reserva de entropía" de bits aleatorios que se supone que son desconocidos para un atacante. Se agrega nueva aleatoriedad siempre que esté disponible (por ejemplo, cuando el usuario presiona una tecla) y se mantiene una estimación del número de bits en el grupo que un atacante no puede conocer. Algunas de las estrategias en uso incluyen:

  • Cuando se soliciten bits aleatorios, devuelva esa cantidad de bits derivados del grupo de entropía (por ejemplo, mediante una función hash criptográfica) y disminuya la estimación del número de bits aleatorios que quedan en el grupo. Si no hay suficientes bits desconocidos disponibles, espere hasta que estén disponibles. Este es el diseño de nivel superior del dispositivo " / dev / random " en Linux, escrito por Theodore Ts'o y utilizado en muchos otros sistemas operativos similares a Unix. Proporciona números aleatorios de alta calidad siempre que las estimaciones de la aleatoriedad de entrada sean lo suficientemente cautelosas. El dispositivo "/ dev / urandom" de Linux es una modificación simple que ignora las estimaciones de aleatoriedad de entrada y, por lo tanto, es menos probable que tenga una alta entropía como resultado.
  • Mantenga un cifrado de flujo con una clave y un vector de inicialización (IV) obtenido de un grupo de entropía. Cuando se hayan recopilado suficientes bits de entropía, reemplace tanto la clave como el IV con nuevos valores aleatorios y disminuya la entropía estimada que queda en el grupo. Este es el enfoque adoptado por la biblioteca de milenrama . Proporciona resistencia contra algunos ataques y conserva la entropía difícil de obtener.

Sistemas (des) centralizados

Un verdadero generador de números aleatorios puede ser un servicio (des) centralizado. Un ejemplo de un sistema centralizado en el que se puede adquirir un número aleatorio es el servicio de balizas de aleatoriedad del Instituto Nacional de Estándares y Tecnología ; otro ejemplo es Random.org , un servicio que utiliza ruido atmosférico para generar dígitos binarios (bits) aleatorios .

Como ejemplo de un sistema descentralizado, la plataforma Cardano utiliza a los participantes de su protocolo de prueba de participación descentralizado para generar números aleatorios.

Problemas

Es muy fácil construir mal dispositivos de hardware o software que intentan generar números aleatorios. Además, la mayoría 'rompe' silenciosamente, a menudo produciendo números aleatorios decrecientes a medida que se degradan. Un ejemplo físico podría ser la radiactividad rápidamente decreciente de los detectores de humo mencionados anteriormente, si esta fuente se usara directamente. Los modos de falla en tales dispositivos son abundantes y complicados, lentos y difíciles de detectar. Los métodos que combinan múltiples fuentes de entropía son más robustos.

Debido a que muchas fuentes de entropía a menudo son bastante frágiles y fallan silenciosamente, las pruebas estadísticas de su salida deben realizarse de forma continua. Muchos, pero no todos, estos dispositivos incluyen algunas de estas pruebas en el software que lee el dispositivo.

Ataques

Al igual que con otros componentes de un sistema de criptografía, se debe diseñar un generador de números aleatorios de software para resistir ciertos ataques . La defensa contra estos ataques es difícil sin una fuente de entropía de hardware.

Estimando la entropía

Existen técnicas matemáticas para estimar la entropía de una secuencia de símbolos. Ninguno es tan confiable como para que se pueda confiar plenamente en sus estimaciones; siempre hay suposiciones que pueden ser muy difíciles de confirmar. Estos son útiles para determinar si hay suficiente entropía en un grupo de semillas, por ejemplo, pero no pueden, en general, distinguir entre una fuente aleatoria verdadera y un generador pseudoaleatorio. Este problema se evita mediante el uso conservador de fuentes de entropía de hardware.

Prueba de desempeño

Los generadores de números aleatorios de hardware deben monitorearse constantemente para que funcionen correctamente. RFC 4086, FIPS Pub 140-2 y NIST Special Publication 800-90b incluyen pruebas que se pueden utilizar para esto. Consulte también la documentación de la biblioteca de software criptográfico de Nueva Zelanda cryptlib .

Dado que muchos diseños prácticos se basan en una fuente de hardware como entrada, será útil comprobar al menos que la fuente sigue funcionando. Las pruebas estadísticas a menudo pueden detectar fallas en una fuente de ruido, como una estación de radio que transmite en un canal que se cree que está vacío, por ejemplo. La salida del generador de ruido se debe muestrear para probar antes de pasar a través de un "blanqueador". Algunos diseños de blanqueadores pueden pasar pruebas estadísticas sin entrada aleatoria. Si bien detectar una gran desviación de la perfección sería una señal de que una verdadera fuente de ruido aleatorio se ha degradado, las pequeñas desviaciones son normales y pueden ser una indicación de un funcionamiento correcto. La correlación de la polarización en las entradas al diseño de un generador con otros parámetros (p. Ej., Temperatura interna, voltaje de bus) podría ser adicionalmente útil como verificación adicional. Desafortunadamente, con las pruebas actualmente disponibles (y previstas), aprobar dichas pruebas no es suficiente para asegurarse de que las secuencias de salida sean aleatorias. Es posible que se necesite un diseño cuidadosamente elegido, la verificación de que el dispositivo fabricado implementa ese diseño y la seguridad física continua para asegurar contra la manipulación, además de las pruebas para usos de alto valor.

Ver también

Referencias

Referencias generales

enlaces externos