Generador de números aleatorios AVR

12

He leído una nota de aplicación de TI ( slaa338 ) que describe una técnica para generar números aleatorios "reales" (en lugar de "pseudo"). Explota el subsistema de reloj algo exótico del MSP430 para lograr este objetivo. ¿Alguien sabe de una técnica que se pueda implementar en un AVR (estoy interesado en los XMega en particular) para generar números aleatorios "reales"?

vicatcu
fuente
1
psuedo funciona al azar para juegos de dados. Creo que quiere seguridad criptográfica.
Kortuk
2
¿Puede dar una pista sobre la aplicación y / o el grado de aleatoriedad que necesita? Si se trata de criptografía, existen consideraciones adicionales además de la calidad de la semilla. Algunas de las sugerencias ya hechas, como el muestreo de insumos ambientales de varios tipos, pueden o no ser apropiados según sus requisitos.
Windell Oskay

Respuestas:

6

¿Qué tan malo es usar el XMega? Si la generación de números criptográficos y aleatorios es una gran parte de su proyecto, la serie SecureAVR de Atmel tiene incorporado un número aleatorio de hardware y está diseñado para aplicaciones criptográficas.

De todos modos, dudo que encuentre una fuente de semilla aleatoria que tenga una buena distribución. Querrá ejecutarlo a través de un generador de números pseudoaleatorios varias veces Siempre que comience con una semilla diferente cada vez, esto le dará un buen conjunto de números aleatorios. Un LGC es un generador pseudoaleatorio rápido y fácil:

static unsigned long Seed; 

/* Call before first use of NextVal */
unsigned long InitSeed()
{
   //Your code for random seed here

   // Correct distribution errors in seed
   NextVal();
   NextVal();
   NextVal();
   return NextVal();
}

 /* Linear Congruential Generator 
  * Constants from  
  * "Numerical Recipes in C" 
  * by way of 
   * <http://en.wikipedia.org/wiki/Linear_congruential_generator#LCGs_in_common_use>
   * Note: Secure implementations may want to get uncommon/new LCG values
  */
unsigned long NextVal()
{
  Seed=Seed*1664525L+1013904223L;
  return Seed;
} 
Kevin Vermeer
fuente
1
Eso es increíble, no me di cuenta de que existía la línea SecureAVR, ¡gracias por el puntero!
vicatcu
Por cierto: si REALMENTE necesita seguridad, el método LCG simple, efectivo y rápido que presenté no es lo que desea: muchos LCG pueden romperse; solo obtenga 2-3 valores seguidos y conéctelos a un generador LCG con un conjunto de constantes conocidas; esto incluiría todo en la página de Wikipedia. Un patrón coincidente permitirá al atacante predecir cuál será el próximo número. También es posible (pero más difícil) descubrir cuáles son las constantes de la nada.
Kevin Vermeer
1
@reemrevnivek Para su información, Atmel está vendiendo su línea SecureAVR ... recomiendan sus procesadores de 32 bits basados ​​en ARM si desea cosas criptográficas que son un juego de pelota completamente diferente en términos de entorno de desarrollo de AVR. Sin embargo, tienen una pareja con True RNG, tal vez jugaré con ellos algún día.
vicatcu
7

Conecte el ADC a una fuente de ruido de hardware y use software para "blanquear" los números aleatorios si es necesario.

Aquí hay un proyecto basado en AVR que hace esto: Mini generador portátil de números aleatorios de Leon (mPRNG)

Dependiendo de cuán criptográficamente seguro deba ser, puede usar el ruido de una entrada analógica con conexión a tierra o el " sensor de temperatura interno " como semilla de aleatoriedad en lugar de hardware externo.

Actualización : más tarde escribí un programa para Arduino que usa los temporizadores del chip como fuente de entropía (el ADC resultó inútil porque los bits ruidosos se truncan), y esto inspiró la creación de la biblioteca Entropy .

En ambos casos, la aleatoriedad no proviene, por ejemplo, del valor de la temperatura en sí, que solo cambia lentamente, sino de los bits menos significativos , que varían aleatoriamente de una lectura a la siguiente. Leí el valor varias veces, una vez por cada bit de salida, desplazamiento de bits y XORing con la lectura anterior. XORing un bit verdaderamente aleatorio con un bit no correlacionado conserva la aleatoriedad , por lo que la aleatoriedad se extiende a todos los bits y se convierte en un verdadero ruido blanco. Sin embargo, su velocidad de bits no será muy alta, ya que solo obtiene un bit de salida por tiempo de adquisición o ciclo de temporizador. Con el método del temporizador, estaba obteniendo aproximadamente 64 bit / s.

endolito
fuente
55
Al nombrar un RNG (más o menos cierto), "-PRNG" es lamentable.
Nick T
+1 para ADC, creo que probablemente estés buscando algo que cambie a una frecuencia más alta que un sensor de temperatura.
Pulpo
1
@Octopus Bueno, no estás usando la temperatura como fuente de entropía, estás usando los bits menos significativos y ruidosos, que cambiarán aleatoriamente cada vez que leas el ADC, incluso si la temperatura es constante. Sin embargo, cuando probé en Arduino, estos bits siempre fueron 0, por lo que no era factible y tuve que usar la variación del temporizador. En otro MCU en el que utilicé ese método, los LSB del ADC eran ruidosos y utilizables.
endolito
3

Otro truco para generar una semilla aleatoria es contar el número de ciclos de reloj hasta un evento externo. Por ejemplo, si este es un dispositivo para ser usado por una persona, cuente la cantidad de ciclos de reloj hasta que presione el botón 'ir' y úselo como semilla aleatoria.

davr
fuente
44
Esto puede no ser muy seguro contra ataques de canal lateral, ya que pueden entrar al control de un dispositivo, pero como sucede con todas las criptografías, la aplicación determina la viabilidad.
Kortuk
3

Para asegurarme de no reiniciar con la misma secuencia, uso el byte somme en el eeprom:

#include <avr/eeprom.h>
#include <stdlib.h> // rand

u16  EEMEM randinit; 

int main(void) {
        srand(eeprom_read_word(&randinit));
        eeprom_write_word(&randinit,rand());
        [...]
 }

Esto da bastante buena al azar, y no cuesta mucho en programa / memoria.

jojo l'abricot
fuente
2
Esto lee el byte 0 cada vez. ¿Qué evidencia tiene de que este byte es aleatorio? Si es así, esta es una gran técnica!
Kevin Vermeer
Esta palabra (byte 0 y 1, de hecho) será aleatoria, porque en cada inicio inicializo el generador aleatorio con su contenido. ENTONCES lo subo con un nuevo rand (). Entonces, el próximo init se verá aleatorio del actual ... y así sucesivamente ... ¡Pero si restablezco randinit a ffff (o 0000?), Tendré la misma secuencia de randinit! Entonces no es perfecto. Olvidé una advertencia sobre el fusible que borra el eeprom al cargar el * .hex;)
jojo l'abricot
3

He creado una biblioteca que, si bien el diseño original para Arduino funciona bien como clase en una implementación de C ++ usando g ++ en avr, de hecho, también se ha portado recientemente a la arquitectura ARM.

Utiliza la fluctuación de fase entre el temporizador de vigilancia y el reloj del sistema y se ha probado en varios chips diferentes (documentado en la página wiki)

http://code.google.com/p/avr-hardware-random-number-generation/wiki/WikiAVRentropy

Walter Anderson
fuente
2

¿Has visto usar algo como randomSeed () ? - utilizado en el IDE Arduino

Puede utilizar esta función para probar una (libre) pin analógico flotando en el Atmel AVR, entonces se utiliza el valor de crear un punto de partida arbitrario para el seudo función de números aleatorios - aleatorio ().

El valor creado por random () puede ser un número pseudoaleatorio, pero el punto de partida arbitrario creado por randomSeed () debe ser un valor / número aleatorio tan real como sea posible.

Jim
fuente
2
Muestrear cosas como los pines analógicos es casi aleatorio, pero no tendrá una distribución uniforme. Sin embargo, ejecute la semilla al azar un par de veces, y lo hará.
Kevin Vermeer
.... a través de un generador de números pseudoaleatorios un par ... <- ¿Cómo desapareció eso? NTS: Involucre primero el cerebro, luego los dedos.
Kevin Vermeer
Exactamente: tampoco es el más seguro si lo usa para cifrado / protección, etc., pero le dará un buen número aleatorio para algo como música generativa o juegos de dados. Es bueno y fácil de implementar también :)
Jim
1

Hay un documento sobre cómo lograr esto con el hardware AVR. Implica confiar en la fluctuación del reloj. Básicamente, utiliza una interrupción de temporizador basada en una fuente de reloj para muestrear los bits más bajos de un temporizador separado que se sincroniza con una fuente de reloj independiente. Los dos relojes tendrán alguna fluctuación aleatoria asociada a ellos y el muestreo no será perfectamente periódico.

Hice una pequeña prueba de concepto de esto en un microcontrolador STM32, el código está en github aquí . Obtuvo algunos buenos resultados basados ​​en un conjunto de conjuntos de pruebas de aleatorización.

En mi opinión, creo que esto es mejor que probar un pin flotante con un ADC que es extremadamente fácil de atacar (¡ata el pin al suelo y tu número ya no es tan aleatorio!). Estoy seguro de que hay una manera de manipular un RNG basado en fluctuación de reloj, pero me hace sentir un poco mejor que puedo hacer esto puramente basado en fuentes de reloj internas en chip.

Jon L
fuente