Obteniendo un número verdaderamente aleatorio en Arduino

13

¿Cuál es el mejor método para obtener un número aleatorio verdadero (en lugar de pseudo) en Arduino, o al menos la mejor aproximación posible? Según tengo entendido, la función randomSeed (analogRead (x)) no es lo suficientemente aleatoria.

Si es posible, el método debería aprovechar la configuración básica de Arduino solo (sin sensores adicionales). Las soluciones con sensores externos son bienvenidas si mejoran significativamente la aleatoriedad sobre la configuración básica.

Rexcirus
fuente
¿Cuál es la aplicación? ¿Debe ser criptográficamente seguro? ¿Qué haces con la aleatoriedad entonces? Entonces, sin un chip externo que implemente un TRNG de una fuente de entropía física, no tienes suerte. También podría implementar un RNG determenista como un HMAC DRBG y sembrarlo de algo estático más una fuente de entropía de baja calidad, pero eso aún no será criptográficamente seguro.
Maximilian Gerhardt
Sí, necesito números aleatorios para aplicaciones criptográficamente seguras.
Rexcirus

Respuestas:

10

La biblioteca Entropy usa:

el jitter natural del temporizador de vigilancia para producir un flujo confiable de números aleatorios verdaderos

Me gusta esta solución porque no usa ningún pin de su microcontrolador y no requiere ningún circuito externo. Esto también lo hace menos sujeto a fallas externas.

Además de una biblioteca, también proporcionan un bosquejo que demuestra el uso de la misma técnica utilizada para generar una semilla aleatoria para el PRNG del microcontrolador sin la biblioteca: https://sites.google.com/site/astudyofentropy/project-definition / timer-jitter-entropy-sources / entropy-library / arduino-random-seed

por1234
fuente
8

randomSeed(analogRead(x))solo producirá 255 secuencias de números, lo que hace que sea trivial probar todos los combos y producir un oráculo que se puede acoplar a su flujo de salida, prediciendo toda la salida al 100%. Sin embargo, estás en el camino correcto, es solo un juego de números y necesitas MUCHOS más de ellos. Por ejemplo, tomar 100 lecturas analógicas de 4 ADC, resumirlas todas y alimentarlas randomSeedsería mucho mejor. Para una seguridad máxima, necesita una entrada impredecible y una mezcla no determinista.

No soy un criptógrafo, pero he pasado miles de horas investigando y construyendo generadores aleatorios de hardware y software, así que permítanme compartir algo de lo que he aprendido:

Entrada impredecible:

  • analogRead () (en pines flotantes)
  • GetTemp ()

Entrada potencialmente impredecible:

  • micros () (con un período de muestra no determinista)
  • jitter de reloj (bajo ancho de banda, pero utilizable)
  • readVCC () (si no funciona con batería)

Entrada externa impredecible:

  • sensores de temperatura, humedad y presión
  • micrófonos
  • Divisores de voltaje LDR
  • ruido de transistor de polarización inversa
  • brújula / fluctuación de aceleración
  • exploración de punto de acceso wifi esp8266 (ssid, db, etc.)
  • sincronización esp8266 (las tareas wifi en segundo plano hacen que los micros programados () recuperen indeterminado)
  • esp8266 HWRNG - extremadamente RANDOM_REG32rápido e impredecible, una parada

recolectar Lo último que quieres hacer es escupir entropía tal como viene. Es más fácil adivinar un lanzamiento de moneda que un cubo de monedas. Sumar es bueno. unsigned long bank;entonces más tarde bank+= thisSample;es bueno; se volcará. bank[32]es aún mejor, sigue leyendo. Desea recopilar al menos 8 muestras de entrada para cada porción de salida, idealmente mucho más.

Protección contra el envenenamiento Si calentar el tablero causa una cierta fluctuación máxima de reloj, es un vector de ataque. Lo mismo con la voladura de RFI hacia las entradas analogRead (). Otro ataque común simplemente desconecta la unidad y por lo tanto descarga toda la entropía acumulada. No debe generar números hasta que sepa que es seguro hacerlo, incluso a costa de la velocidad.

Es por eso que desea mantener algo de entropía a largo plazo, utilizando EEPROM, SD, etc. Busque en el PRNG de Fortuna , que usa 32 bancos, cada uno actualizado la mitad de veces que el anterior. Eso hace que sea difícil atacar a los 32 bancos en un tiempo razonable.

Procesamiento Una vez que recolecta "entropía", debe limpiarla y separarla de la entrada de una manera difícil de revertir. SHA / 1/256 es bueno para esto. Puede usar SHA1 (o incluso MD5 realmente) para la velocidad ya que no tiene una vulnerabilidad de texto sin formato. Para cosechar, nunca use el banco de entopy completo, y SIEMPRE SIEMPRE agregue una "sal" a la salida que es diferente cada vez para evitar salidas idénticas sin cambios en el banco de entropía: output = sha1( String(micros()) + String(bank[0]) + [...] );la función sha oculta las entradas y blanquea la salida, protegiendo contra semillas débiles, bajo acumulado ent, y otros problemas comunes.

Para usar entradas de temporizador, debe hacerlas indeterministas. Este es un simple como delayMicroseconds(lastSample % 255); que pausa una cantidad de tiempo impredecible, haciendo que las lecturas de reloj "sucesivas" no sean uniformes en la diferencia. Haga eso de forma regular, como if(analogRead(A1)>200){...}, siempre que A1 sea ruidoso o esté conectado a una entrada dinámica. Hacer que cada bifurcación de su flujo sea bastante difícil de determinar evitará el criptoanálisis en la salida descompilada / extraída.

La verdadera seguridad es cuando el atacante conoce todo su sistema y aún no puede vencerlo.

Por último, revisa tu trabajo. Ejecute su salida a través de ENT.EXE (también disponible para nix / mac) y vea si es bueno. Lo más importante es la distribución de chi cuadrado, que generalmente debe estar entre 33% y 66%. Si obtienes 1.43% o 99.999% o algo así de nervioso, más de una prueba en una fila, tu azar es una mierda. También desea que los informes ENT de entropía estén lo más cerca posible de 8 bits por byte,> 7.9 con seguridad.

TLDR: La forma más simple de prueba de tontos es con el HWRNG de ESP8266. Es rápido, uniforme e impredecible. Ejecute algo como esto en un ESP8266 que ejecute el núcleo Ardunio, y use serial para hablar con el AVR:

// ESP8266 Arduino core code:
void setup(){
 Serial.begin(9600); // or whatever
}

void loop() {
  // Serial.write((char)(RANDOM_REG32 % 256)); // "bin"
  Serial.print( String(RANDOM_REG32, HEX).substring(1)); // "hex"
}

** editar

Aquí hay un boceto de HWRNG sin formato que escribí hace un tiempo, operando no solo como un colector, sino como un CSPRNG completo escupiendo desde el puerto serie. Está diseñado para un pro-mini, pero debe ser fácilmente adaptable a otras placas. Puede usar solo pines analógicos flotantes, pero es mejor agregarles cosas, preferiblemente cosas diferentes. Al igual que los micrófonos, los LDR, los termistores (recortados a la máxima dispersión alrededor de la temperatura ambiente) e incluso cables largos. Funciona bastante bien en ENT si tienes incluso un ruido moderado.

El boceto integra varias nociones que he mencionado en mi respuesta y comentarios de seguimiento: acumulación de entropía, estiramiento sobremuestreando una entropía menos que ideal (von Neumann dijo que es genial), y un hash a la uniformidad. Se renuncia a la estimación de la calidad de la entropía a favor de "dar algo posiblemente dinámico" y mezclar usando una primitiva criptográfica.

// AVR (ardunio) HWRNG by dandavis. released to public domain by author.
#include <Hash.h> 

unsigned long read[8] = {0, 0, 0, 0, 0, 0, 0, 0};
const int pincount = 9; // adjust down for non pro-mini boards
int pins[9] = {A0, A1, A2, A3, A4, A5, A6, A7, A0}; // adjust for board, name analog inputs to be sampled
unsigned int ticks = 0;
String buff = ""; // holds one round of derivation tokens to be hashed.
String cache; // the last read hash



void harvest() { // String() slows down the processing, making micros() calls harder to recreate
  unsigned long tot = 0; // the total of all analog reads
  buff = String(random(2147483647)) + String(millis() % 999);
  int seed =  random(256) + (micros() % 32);
  int offset =  random(2147483647) % 256;

  for (int i = 0; i < 8; i++) {
    buff += String( seed + read[i] + i + (ticks % 65), HEX );
    buff += String(random(2147483647), HEX);
    tot += read[i];
  }//next i

  buff += String( (micros() + ticks + offset) % 99999, HEX);
  if (random(10) < 3) randomSeed(tot + random(2147483647) + micros()); 
  buff = sha1( String(random(2147483647)) + buff + (micros()%64) + cache); // used hash to uniform output and waste time
  Serial.print( buff ); // output the hash
  cache = buff;
  spin();
}//end harvest()


void spin() { // add entropy and mix
  ticks++;
  int sample = 128;
  for (int i = 0; i < 8; i++) { // update ~6/8 banks 8 times
    read[ read[i] % 8] += (micros() % 128);
    sample = analogRead(  pins[i] ); // a read from each analog pin
    read[ micros() % 8] += ( read[i] % 64 ); // mix timing and 6LSBs from read
    read[i] += sample; // mix whole raw sample
    read[(i + 1) % 8] += random(2147483647) % 1024; // mix prng
    read[ticks % 8] += sample % 16; // mix the best nibble of the read
    read[sample % 8] += read[ticks % 8] % 2147483647; // intra-mix banks
  }

}//end spin()



void setup() {
  Serial.begin(9600);
  delay(222);
  int mx = 2028 + ((analogRead(A0)  + analogRead(A1) + analogRead(A2)  + analogRead(A3)) % 256);  
  while (ticks < mx) {
    spin();
    delay(1);
    randomSeed(read[2] + read[1] + read[0] + micros() + random(4096) + ticks);
  }// wend
}// end setup()



void loop() {
  spin();
  delayMicroseconds((read[ micros() % 8] %  2048) + 333  );
  delay(random(10));
  //if (millis() < 500) return;
  if ((ticks % 16) == (millis() % 16) ) harvest();
}// end loop()
dandavis
fuente
(Me faltan caracteres aquí, lo siento). ¡Buena descripción! Sugeriría usar un contador para la sal; micros () es un desperdicio de bits porque puede saltar varios pasos entre llamadas. Evite los bits altos en las entradas analógicas, restrinja a uno o dos bits más bajos. Incluso con un ataque dirigido esos son difíciles de precisar (a menos que pueda poner un cable en la Entrada). La "mezcla no determinista" no es algo que pueda hacer en el software. La mezcla SHA-1 está estandarizada: crypto.stackexchange.com/a/6232 . El indet. el temporizador que propone es tan aleatorio como la fuente que ya tiene. No hay mucha ganancia aquí.
Jonas Schäfer
sha simplifica y protege, para que no tenga que preocuparse por cuántos bits tomar de una entrada analógica, por ejemplo. unas pocas pulgadas de cable conectado a un análogo (o una traza de serpentina pcb) lo balancearán más que unos pocos bits. la mezcla no es determinista en virtud de la sal no guardada y desconocida alimentada al hash con una submuestra de valores acumulados. micros () es más difícil de reproducir que un contador, especialmente cuando se dispara a intervalos no deterministas.
dandavis
1
Tengo una pregunta. Dijiste que tomar 100 medidas es mejor. Pero, ¿tomar muchas medidas no es una especie de "promedio" que limita la efectividad de tomar estos datos "aleatorios"? Es decir, por lo general se promedia para obtener menos ruidoso (por lo menos "al azar") mediciones ...
frarugi87
bueno, recomiendo un muestreo constante, solo decía que 100 es mejor que 1 ya que ofrece más combinaciones. Un modelo de acumulación como Yarrow / Fortuna sigue siendo mucho mejor. Considere concatenar (no sumar) esas 100 muestras analógicas antes del hash; más fuerte porque hace que el orden de la muestra sea importante, y el hecho de ser un char off produce un hash completamente diferente Entonces, aunque uno podría promediar las muestras para obtener menos ruido, un atacante tendría que recitar textualmente todos los valores o ninguna coincidencia ... Mi punto principal es "acumular, mezclar y verificar" más que defender una fuente de ruido específica.
dandavis
4

Desde mi experiencia, analogRead()en un pin flotante tiene muy baja entropía. Tal vez uno o dos bits de aleatoriedad por llamada. Definitivamente quieres algo mejor. La inquietud del temporizador de vigilancia, como se propone en la respuesta de per1234, es una buena alternativa. Sin embargo, genera entropía a una velocidad bastante lenta, lo que puede ser un problema si lo necesita justo cuando se inicia el programa. Dandavis tiene bastantes buenas sugerencias, pero generalmente requieren un ESP8266 o hardware externo.

Hay una fuente de entropía interesante que aún no se ha mencionado: el contenido de la RAM no inicializada. Cuando la MCU se enciende, algunos de sus bits de RAM (los que tienen los transistores más simétricos) se inician en un estado aleatorio. Como se discutió en este artículo de hackaday , esto puede usarse como una fuente de entropía. Solo está disponible en un arranque en frío, por lo que puede usarlo para llenar un grupo de entropía inicial, que luego repondría periódicamente de otra fuente potencialmente lenta. De esta manera, su programa puede comenzar su trabajo sin tener que esperar a que el grupo se llene lentamente.

Aquí hay un ejemplo de cómo esto podría cosecharse en un Arduino basado en AVR. El fragmento de código debajo de XOR carga toda la RAM para construir una semilla que luego alimenta srandom(). La parte difícil es que la recolección debe realizarse antes de que el tiempo de ejecución C inicialice las secciones de memoria .data y .bss, y luego la semilla debe guardarse en un lugar donde el tiempo de ejecución C no se sobrescriba. Esto se hace mediante el uso de secciones de memoria específicas .

uint32_t __attribute__((section(".noinit"))) random_seed;

void __attribute__((naked, section(".init3"))) seed_from_ram()
{
    const uint32_t * const ramstart = (uint32_t *) RAMSTART;
    const uint32_t * const ramend   = (uint32_t *) RAMEND;
    uint32_t seed = 0;
    for (const uint32_t *p = ramstart; p <= ramend; p++)
        seed ^= *p;
    random_seed = seed;
}

void setup()
{
    srandom(random_seed);
}

Tenga en cuenta que, en un reinicio en caliente , la SRAM se conserva, por lo que todavía tiene todo el contenido de su grupo de entropía. Este mismo código se puede usar para preservar la entropía recopilada a través de un reinicio.

Editar : solucionó un problema en mi versión inicial de seed_from_ram()que funcionaba en el global en random_seedlugar de usar un local seed. Esto podría llevar a que la semilla sea XOR consigo misma, destruyendo toda la entropía cosechada hasta ahora.

Edgar Bonet
fuente
¡Buen trabajo! puedo robar? re: pines: uno o dos bits de desconocido es suficiente si se utiliza correctamente; eso solo limitaría la velocidad de salida del secreto perfecto (asco), pero no el secreto computacional que necesitamos ...
dandavis
1
@dandavis: Sí, puedes reutilizar, claro. Tiene razón acerca de analogRead()ser utilizable si sabe lo que está haciendo. Solo debe tener cuidado de no sobreestimar su aleatoriedad al actualizar una estimación de la entropía de su grupo. Mi punto sobre el analogRead()que se entiende principalmente como una crítica a un pobre sin embargo, a menudo repetida “receta” : randomSeed(analogRead(0)) sólo una vez en setup()y asumir que es suficiente.
Edgar Bonet
Si analogRead(0)tiene 1 bit de entropía por llamada, llamarlo repetidamente producirá 10000/8 = 1.25 KBytes / seg de entropía, 150 veces más que la biblioteca de Entropía.
Dmitry Grigoryev
0

Si realmente no necesita entropía y simplemente desea obtener una secuencia diferente de números pseudoaleatorios en cada inicio, puede usar EEPROM para iterar a través de semillas consecutivas. Técnicamente, el proceso será completamente determinista, pero en términos prácticos es mucho mejor que randomSeed(analogRead(0))en un pin no conectado, lo que a menudo lo hará comenzar con la misma semilla de 0 o 1023. Guardar la próxima semilla en EEPROM garantizará que comience con un diferente semilla cada vez.

#include <EEPROM.h>

const int seed_addr = 0;
unsigned long seed;

void setup() {
    seed = EEPROM.read(seed_addr);
    EEPROM.write(seed_addr, seed+1);
    randomSeed(seed);
}

Si necesita una entropía real, puede recolectarla a partir de la deriva del reloj o amplificando el ruido externo. Y si necesita mucha entropía, el ruido externo es la única opción viable. El diodo Zener es una opción popular, especialmente si tiene una fuente de voltaje por encima de 5-6V (también funcionará con 5V con un diodo Zener apropiado, pero producirá menos entropía):

ingrese la descripción de la imagen aquí

( fuente )

La salida del amplificador debe conectarse a un pin analógico, que producirá varios bits de entropía con cada uno analogRead()hasta decenas de MHz (más rápido de lo que Arduino puede muestrear).

Dmitry Grigoryev
fuente