random - songs - song name generator
¿Es posible generar números aleatorios usando sensores físicos? (4)
Depende del rango, la frecuencia de muestreo y la sensibilidad del sensor. Puede considerar las mediciones del sensor como bitstrings o como flotadores, realmente no importa. El punto es que los bits más significativos / los decimales iniciales no son muy aleatorios, incluso podrían cambiar apenas. Del mismo modo, los bits menos significativos son fuentes poco confiables de aleatoriedad, ya que pueden mostrar un efecto de paso debido a la sensibilidad limitada del sensor, y dependiendo del sensor pueden estar fuertemente correlacionados en el tiempo (por ejemplo, la temperatura o el voltaje tenderán a cambiar gradualmente ) Sin embargo, los bits / figuras medios podrían ser una fuente de verdaderos valores aleatorios.
Supongamos que tiene un sensor que genera valores en el rango de 0 a 200, con una precisión de 0.01. Digamos que es un medidor de presión, tal vez un medidor de decibeles. Necesitaría probar esto extensivamente y observar la distribución de valores para su sensor y entorno específicos, pero creo que las cifras en las posiciones 10 ^ 0 y 10 ^ -1 podrían distribuirse uniformemente y sin un orden discernible.
Los más adecuados son los sensores que pueden realizar mediciones muy precisas, pero tienen que lidiar con un alto nivel de ruido de todos modos. Esto podría ser un problema ya que la mayoría de los sensores no están diseñados para proporcionar un nivel de precisión innecesario / no confiable. Además, las mediciones que son más o menos las mismas siempre y en todas partes (a excepción del ruido) son preferibles por supuesto. La radiación cósmica de fondo es un buen ejemplo de esto.
He oído hablar de personas que usan sensores de luz, contadores Geiger y otros sensores físicos para generar números aleatorios, pero soy escéptico. ¿Existe realmente una forma de generar números aleatorios a partir de tomar medidas del mundo físico (usando un Arduino o cualquier otro microcontrolador)? Si es así, ¿estos números alguna vez serían realmente aleatorios?
para aclarar: la pregunta es sobre la viabilidad de usar datos recopilados por microcontroladores para generar números aleatorios que podrían aplicarse de forma sólida a la criptografía, una alternativa a confiar en la entropía de un dispositivo.
He estado experimentando con fuentes de hardware para la generación de números aleatorios, y hasta ahora parecen proporcionar una fuente impredecible. Si se utilizan técnicas de blanqueamiento, cualquier sesgo subyacente se reduce / elimina para permitir que produzcan una secuencia uniforme de enteros aleatorios.
Si desea probar y experimentar, he implementado una biblioteca compatible con Arduino que usa la fluctuación de fase asociada con el temporizador de vigilancia para generar números aleatorios. Los resultados preliminares indican que está produciendo resultados adecuados para fines criptográficos.
Se puede encontrar en el repositorio de la biblioteca Code.google
Google: verdadero generador de números aleatorios
Así es como lo haces, creas ruido y lo muestras. No puede crear algo realmente aleatorio a partir de algo que es determinista, como un algoritmo de software.
Tomar mediciones analógicas del "mundo real" generalmente es una buena fuente de entropía (también conocida como datos aleatorios reales). Las fuentes analógicas siempre tienen un ruido impredecible superpuesto que se puede "cosechar". Sin embargo, como se indicó anteriormente, los datos medidos rara vez no están sesgados.
Las mediciones eléctricas analógicas también pueden ser más o menos susceptibles a una influencia incontrolable o incluso a ataques desde el exterior, por ejemplo, causando la saturación de los sensores. EMI también es probable que interfiera con la medición; un teléfono celular normal colocado razonablemente cerca del circuito durante una llamada probablemente causará estragos en cualquier señal analógica.
Parcialidad
Los números de alta entropía no sesgados y uniformemente distribuidos son comúnmente los que uno quiere, porque sus propiedades (no valores ) están algo normalizadas y, por lo tanto, pueden predecirse más confiablemente.
Al medir la entrada analógica con, por ejemplo, resolución de 10 bits, idealmente el rango de números recopilados de la medición cubrirá todos los valores de 0 a 1024 y cada valor ocurrirá con la misma frecuencia (o probabilidad) que cualquier otro valor de ese rango.
En realidad, esos valores a menudo estarán (más o menos) normalmente distribuidos (distribuidos por Gauss) en torno a algún valor medio con alguna desviación estándar característica, por ejemplo alrededor de 500 @ 10 bits por muestra.
Despersonalización
Por lo tanto, para generar valores aleatorios con las propiedades deseadas (ver arriba), se necesita cierta despersonalización: se necesita un extractor de aleatoriedad de algún tipo.
El uso de funciones criptográficas, como las funciones hash (unidireccionales) o los algoritmos de cifrado, generalmente también produce fácilmente el resultado deseado; sin embargo, esto tiene un costo: la "mezcla" de esas funciones es por diseño extremadamente fuerte, lo que hace imposible determinar la calidad (= aleatoriedad) de los datos de origen después de la transformación. Incluso las secuencias de valores deterministas más simples, como {1, 2, 3, 4, 5 ...}, cuando se producen hash datos que muy probablemente pasarán todas y cada una de las pruebas estadísticas de aleatoriedad bastante bien, aunque no es "aleatorio" en todas.
Generando entropía en un μC
Sincronización
En los entornos de microcontroladores, una buena fuente de entropía que rara vez se piensa es el momento de los eventos. Usando un temporizador de alta velocidad, la entropía verdadera se puede recopilar leyendo el valor del temporizador en respuesta a algún evento asincrónico. Tal evento, que no está correlacionado con el temporizador de ejecución, puede ser la pulsación de un botón por parte de un usuario, el inicio de la comunicación iniciada por otro (sub) sistema o CI, o básicamente cualquier otro evento no desencadenado por el μC (o cualquier subsistema síncrono) en sí mismo.
De hecho, la entropía incluso se puede cosechar de solo dos fuentes de reloj independientes ; por ejemplo, cronometrando ciclos de un reloj a través del otro reloj. Esto abre un par de posibilidades muy interesantes en Atmel AVR μCs (que se usan en el Arduino) dependiendo de las capacidades del μC:
La mayoría de los AVR tienen memoria EEPROM interna. Las operaciones de escritura en esta memoria son temporizadas por un temporizador dedicado que es independiente del reloj principal del sistema
(se informa que hay algunos chips (¡no tipos!) Donde las mediciones indicaron que este no es el caso)(editar: tenga en cuenta que en algunos AVR , ATtini25 / 45/85, por ejemplo, la temporización EEPROM se deriva del oscilador RC interno, de modo que no se puede recoger la entropía cuando este oscilador también se selecciona como la fuente de reloj del sistema) ; esto puede depender de la fuente de reloj principal (R / C interno vs. cristal / resonador externo). Por lo tanto, hay algo de fluctuación (verdaderamente aleatoria) que se puede esperar en el tiempo que lleva escribir en la EEPROM con respecto al reloj principal del sistema, que de nuevo puede medirse con un temporizador / contador de alta velocidad.Los AVR más nuevos tienen la capacidad de permitir que el temporizador de vigilancia genere una interrupción de software en lugar de un restablecimiento de hardware. El temporizador de vigilancia está controlado por diseño por su propia fuente de reloj independiente, lo que produce la fluctuación de fase relativa que uno puede medir.
Muchos AVR tienen la capacidad de tener un temporizador / contador dedicado sincronizado desde un cristal externo de 32 kHz para una precisión mejorada de las mediciones en tiempo real. Este cristal externo es otra fuente de eventos no correlacionados con el reloj principal. (De lo contrario, no habría ningún uso en el cristal extra en primer lugar ...)
Este último parece prometedor por su potencial de ancho de banda relativamente alto: cuando cronometra cada ciclo de reloj de 32kHz con un temporizador de sistema corriendo significativamente más rápido (se puede lograr un factor de 600+ en AVRs actuales a 20 MHz!) Y asumiendo de manera conservadora solo 1 bit de entropía por medición, esto genera más de 32000 bits de entropía por segundo , mucho más de lo que un μC consumirá por sí solo.
EDITAR: Mientras tanto, he realizado algunas pruebas simples del enfoque del temporizador de 32 kHz, y los resultados a corto plazo parecen ser de muy baja calidad. El límite superior en la entropía generada por muestra parece ser muy bajo, mientras que ni siquiera he probado las muestras para patrones no obvios que se originan en cambios de fase más o menos regulares. Este resultado puede deberse al hecho de que mi DUT tenía su reloj principal accionado por un cristal externo que se puede esperar que (dentro de la precisión de las mediciones) sea igualmente estable en frecuencia que el cuarzo de 32 kHz cuando se observa en un rango de tiempo limitado. La prolongación del tiempo entre la toma de dos muestras (¿minutos?) Probablemente devolverá una buena entropía, aunque con un ancho de banda muy bajo. (Nb: la fluctuación de fase medida también puede deberse en parte a la latencia de interrupción variable dependiendo de la instrucción de la máquina ejecutada justo en el momento en que se activa la interrupción).
EDIT # 2: Parece que el oscilador RC interno de mi DUT (ATmega1284) produce una fluctuación de frecuencia significativa (varios kHz / s); correr en este oscilador parece producir bastante entropía (kBits / s) cuando el cristal externo de 32kHz lo sincroniza.
En un pequeño experimento, recientemente investigué los dos métodos anteriores. En mi DUT, la temporización EEPROM generalmente sería ventajosa con respecto a la WDT:
La temporización de la escritura EEPROM produjo aproximadamente 4,82 bits de entropía por operación de escritura, mientras que el temporizador de vigilancia parece ser más estable en cuanto a la frecuencia, produciendo aproximadamente 3,92 bits por tiempo de espera del perro guardián. Además, los tiempos de escritura de EEPROM parecen mucho más fluidos distribuidos por Gauss donde la distribución de WDT parece algo asimétrica y con muchas aberraciones.
Nb: La agregación de múltiples eventos "aleatorios" para una sola medición de entropía puede de hecho degradar la entropía obtenida: las fluctuaciones rápidas y aleatorias en la fuente pueden compensarse parcialmente entre sí, produciendo valores de resultado con una desviación menor del valor medio. Entonces, en lugar de cronometrar, por ejemplo, un segundo en tiempo real (32k ciclos del cristal RTC) se puede esperar mucha más entropía al tomar tiempos de 32k (uno para cada ciclo del cristal) durante el mismo tiempo.
RAM no inicializada
Las aplicaciones compiladas de Avr-gcc generalmente tienen toda la RAM en el chip borrada a 0x00 antes de ejecutar el código de usuario, es decir, main() . Al poner el código en una sección .init temprana, se proporciona acceso al contenido de RAM no inicializado en bruto antes de que sea sobrescrito por las rutinas de inicialización de gcc.
Debido a variaciones minúsculas en las celdas de almacenamiento físico de la RAM (bits) y dependiendo de algún ruido térmico aleatorio real (y otros efectos), no todas las celdas se inicializarán en el mismo estado conocido cuando la potencia (re) se aplique al chip. Combinar el contenido de la RAM del chip justo después de encenderlo con alguna función puede generar cantidades significativas de entropía para usar más adelante. - La desventaja de esto es que solo funcionará de manera confiable cuando la energía se haya apagado por algún tiempo y luego se vuelva a encender. Un restablecimiento de chip normal, por hardware, software o señal externa, preservará el contenido previo de la RAM y, por lo tanto, no es (siempre) una buena fuente de entropía. Sin embargo, dado que el estado de todo el sistema (RAM) en el momento del restablecimiento difícilmente puede predecirse en una aplicación razonablemente compleja, puede recopilarse entropía inmediatamente después de un restablecimiento.
Requisitos de ancho de banda
La calidad de una fuente de entropía debe verse en relación con su ancho de banda y el ancho de banda del uso de entropía por parte de la aplicación. Algunos métodos de recopilación de entropía pueden no producir más de un bit de entropía durante algunos segundos mientras que otros (en realidad no en μCs ...) pueden producir 100 kbit / so más.
¡Debe notarse que uno no puede "crear" algorítmicamente nueva entropía a partir de la entropía existente! - Un bit de entropía no puede transformarse computacionalmente en dos bits de entropía.
Por lo tanto, uno no puede (en general) consumir más entropía (real) por unidad de tiempo que la que se obtiene de la (s) fuente (s) de entropía al mismo tiempo.
Propuesta
Cuando se necesitan números aleatorios fuertes, no es raro combinar una o más fuentes de entropía real con un PRNG fuerte, usando la entropía reunida para (re) sembrar el PRNG cada vez que hay nueva entropía disponible.
El PRNG se puede utilizar para generar datos mucho más impredecibles de lo que la fuente de entropía realmente proporcionaría al mismo tiempo.
Como un tipo especial de PRNG, se pueden usar las funciones de cifrado criptográfico, donde la entropía se usa para inicializar y actualizar la clave de cifrado.
Linux /dev/urandom se implementa comúnmente de esta manera.
Conclusión
Como se discutió anteriormente, es bastante factible generar números verdaderamente aleatorios en un microcontrolador común. En cuanto a todas las demás fuentes de entropía, es necesario analizar los números brutos proporcionados por la (s) fuente (s) de entropía para la cantidad de entropía real que contienen y para la cantidad de entropía generada por unidad de tiempo para determinar si la fuente es adecuada para la caso de uso o no.
La combinación de una verdadera fuente de entropía y un fuerte PRNG es el enfoque que comúnmente se implementa y que también se debe utilizar en un microcontrolador.
EDITAR:
El enfoque de PRNG puede no ser la mejor opción para la generación de claves criptográficas. Para eso, solo se deben usar bits verdaderamente aleatorios para producir una clave segura. Reunir esta cantidad de entropía puede llevar algo de tiempo (quizás segundos), pero dado que la generación de claves generalmente no se realiza con mucha frecuencia en un μC, esto puede ser aceptable. (En un servidor muy cargado que tenga cientos o más conexiones SSL (HTTPS) por segundo, este será otro problema ...)
Para producir flujos de bits de alta entropía de calidad adecuados para la generación de claves, se debe emplear un extractor de aleatoriedad como se menciona anteriormente.
(Por otro lado, si la cantidad de entropía en la salida de la fuente puede medirse o estimarse, se puede escalar la longitud de la clave por el factor de (bitlength of key)/(entropy per bit sampled) y luego usar la baja entropía sin procesar datos de la fuente de entropía directamente para generar esta clave más larga, que tendrá la misma entropía general que una clave totalmente aleatoria de la longitud original. Si esto realmente funciona, el truco depende, sin embargo, de cómo el cifrado maneja claves de diferentes longitudes. )