Obtenir un nombre vraiment aléatoire dans Arduino

Quelle est la meilleure méthode pour obtenir un nombre vraiment (par opposition à un pseudo) aléatoire dans Arduino, ou au moins la meilleure approximation possible? D'après ma compréhension, la fonction randomSeed (analogRead (x)) n'est pas assez aléatoire.

Si possible, la méthode devrait exploiter la configuration de base d'Arduino seule (pas de capteurs supplémentaires). Les solutions avec capteurs externes sont les bienvenues si elles améliorent considérablement le caractère aléatoire par rapport à la configuration de base.

La bibliothèque Entropy utilise:

la gigue naturelle de la minuterie du chien de garde pour produire un flux fiable de vrais nombres aléatoires

J'aime cette solution car elle n'utilise aucune broche de votre microcontrôleur et ne nécessite aucun circuit externe. Cela le rend également moins sujet aux défaillances externes.

En plus d'une bibliothèque, ils fournissent également un croquis qui montre l'utilisation de la même technique utilisée pour générer une graine aléatoire pour le PRNG du microcontrôleur sans la bibliothèque: https://sites.google.com/site/astudyofentropy/project-definition / timer-jitter-entropy-sources / entropy-library / arduino-random-seed

randomSeed(analogRead(x))ne produira que 255 séquences de nombres, ce qui rend trivial d'essayer tous les combos et de produire un oracle qui peut se coupler à votre flux de sortie, prédisant toute la sortie à 100%. Cependant, vous êtes sur la bonne voie, ce n'est qu'un jeu de chiffres et vous en avez besoin de beaucoup plus. Par exemple, prendre 100 lectures analogiques à partir de 4 ADC, les additionner toutes et les alimenter randomSeedserait bien mieux. Pour une sécurité maximale, vous avez besoin à la fois d'une entrée imprévisible et d'un mixage non déterministe.

Je ne suis pas un cryptographe, mais j'ai passé des milliers d'heures à rechercher et à créer des générateurs aléatoires de matériel et de logiciels, alors permettez-moi de partager ce que j'ai appris:

Entrée imprévisible:

• analogRead () (sur broches flottantes)
• GetTemp ()

Entrée potentiellement imprévisible:

• micros () (avec une période d'échantillonnage non déterministe)
• gigue d'horloge (faible bande passante, mais utilisable)
• readVCC () (si non alimenté par batterie)

Entrée externe imprévisible:

• capteurs de température, d'humidité et de pression
• microphones
• Diviseurs de tension LDR
• bruit de transistor à polarisation inverse
• boussole / gigue d'accélération
• esp8266 scan de hotspot wifi (ssid, db, etc.)
• esp8266 timing (les tâches wifi en arrière-plan rendent les micros () récupérés indéterminés)
• esp8266 HWRNG - -extrêmement RANDOM_REG32rapide et imprévisible, un arrêt

collecte La dernière chose que vous voulez faire est de cracher l'entropie au fur et à mesure. Il est plus facile de deviner un lancer de pièce qu'un seau de pièces. La sommation est bonne. unsigned long bank;puis plus tard bank+= thisSample;c'est bien; il se renversera. bank[32]c'est encore mieux, lisez la suite. Vous souhaitez collecter au moins 8 échantillons d'entrée pour chaque bloc de sortie, idéalement beaucoup plus.

Protéger contre l'empoisonnement Si le chauffage de la planche provoque une certaine gigue d'horloge maximale, c'est un vecteur d'attaque. Idem avec le dynamitage RFI vers les entrées analogRead (). Une autre attaque courante consiste simplement à débrancher l'unité et à vider ainsi toute l'entropie accumulée. Vous ne devez pas sortir de chiffres tant que vous ne savez pas que cela est sûr, même au prix de la vitesse.

C'est pourquoi vous voulez conserver une certaine entropie à long terme, en utilisant EEPROM, SD, etc. Regardez dans le Fortuna PRNG , qui utilise 32 banques, chacune mise à jour deux fois moins souvent que la précédente. Il est donc difficile d'attaquer les 32 banques dans un délai raisonnable.

Traitement Une fois que vous avez collecté "l'entropie", vous devez le nettoyer et le séparer de l'entrée d'une manière difficile à inverser. SHA / 1/256 est bon pour cela. Vous pouvez utiliser SHA1 (ou même vraiment MD5) pour la vitesse car vous n'avez pas de vulnérabilité en texte brut. Pour récolter, n'utilisez jamais la banque d'entopie complète et TOUJOURS ajouter TOUJOURS un "sel" à la sortie qui est différent à chaque fois pour empêcher des sorties identiques étant donné aucun changement de banque d'entropie: output = sha1( String(micros()) + String(bank[0]) + [...] );la fonction sha dissimule les entrées et blanchit la sortie, protégeant contre les graines faibles, faible accumulation et autres problèmes courants.

Pour utiliser les entrées de la minuterie, vous devez les rendre indéterministes. C'est aussi simple que delayMicroseconds(lastSample % 255); ce qui fait une pause d'une durée imprévisible, ce qui rend la lecture d'horloge "successive" non uniforme. Faites cela de façon semi-régulière, à if(analogRead(A1)>200){...}condition que A1 soit bruyant ou connecté à une entrée dynamique. Rendre chaque fork de votre flux assez difficile à déterminer empêchera la cryptoanalyse sur la sortie décompilée / déchirée.

La vraie sécurité, c'est quand l'attaquant connaît tout votre système et est toujours impuissant à le surmonter.

Enfin, vérifiez votre travail. Exécutez votre sortie via ENT.EXE (également disponible pour nix / mac) et voyez si c'est bon. Le plus important est la distribution du chi carré, qui devrait généralement se situer entre 33% et 66%. Si vous obtenez 1,43% ou 99,999% ou quelque chose de nerveux comme ça, plus d'un test d'affilée, votre hasard est de la merde. Vous voulez également que les rapports ENT d'entropie soient aussi proches que possible de 8 bits par octet,> 7,9 à coup sûr.

TLDR: La manière la plus simple à toute épreuve est d'utiliser le HWRNG de l'ESP8266. C'est rapide, uniforme et imprévisible. Exécutez quelque chose comme ça sur un ESP8266 exécutant le noyau Ardunio et utilisez la série pour parler à l'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"
}

** Éditer

voici un croquis HWRNG nu que j'ai écrit il y a quelque temps, fonctionnant non seulement comme un collecteur, mais comme un CSPRNG entier sortant du port série. Il est conçu pour un pro-mini mais devrait être facilement adaptable à d'autres cartes. Vous pouvez utiliser uniquement des broches analogiques flottantes, mais il est préférable d'y ajouter des éléments, de préférence des choses différentes. Comme les microphones, les LDR, les thermistances (coupées au maximum réparties autour de la température ambiante) et même les longs fils. Il fonctionne assez bien en ORL si vous avez même un bruit modéré.

L'esquisse intègre plusieurs notions que j'ai mentionnées dans ma réponse et mes commentaires de suivi: accumuler l'entropie, étirer en suréchantillonnant une entropie moins qu'idéale (von neumann a dit que c'était cool) et hacher à l'uniformité. Il renonce à l'estimation de la qualité de l'entropie au profit de "donne-moi quelque chose de potentiellement dynamique" et de mixage à l'aide d'une primitive cryptographique.

// 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()

D'après mon expérience, analogRead()sur une broche flottante a une entropie très faible. Peut-être un ou deux bits de hasard par appel. Vous voulez vraiment quelque chose de mieux. La gigue du temporisateur du chien de garde, comme proposé dans la réponse de per1234, est une bonne alternative. Cependant, il génère une entropie à un rythme assez lent, ce qui peut être un problème si vous en avez besoin au démarrage du programme. dandavis a quelques bonnes suggestions, mais elles nécessitent généralement un ESP8266 ou du matériel externe.

Il existe une source d'entropie intéressante qui n'a pas encore été mentionnée: le contenu de la RAM non initialisée. Lorsque le MCU est mis sous tension, certains de ses bits RAM (ceux qui ont le plus de transistors symétriques) démarrent dans un état aléatoire. Comme discuté dans cet article hackaday , cela peut être utilisé comme source d'entropie. Il n'est disponible que sur un démarrage à froid, vous pouvez donc l'utiliser pour remplir un pool d'entropie initial, que vous réapprovisionnez ensuite périodiquement à partir d'une autre source, potentiellement lente. De cette façon, votre programme peut commencer son travail sans avoir à attendre que la piscine se remplisse lentement.

Voici un exemple de la façon dont cela pourrait être récolté sur un Arduino basé sur AVR. L'extrait de code ci-dessous XORs la RAM entière afin de construire une graine qu'il alimente plus tard srandom(). La partie délicate est que la récolte doit être effectuée avant que le runtime C n'initialise les sections de mémoire .data et .bss, puis la graine doit être sauvegardée à un endroit que le runtime C ne remplacera pas. Cela se fait en utilisant des sections de mémoire spécifiques .

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);
}

Notez que, lors d'une réinitialisation à chaud , la SRAM est préservée, de sorte qu'elle a toujours tout le contenu de votre pool d'entropie. Ce même code peut ensuite être utilisé pour conserver l'entropie collectée lors d'une réinitialisation.

Edit : correction d'un problème dans ma version initiale seed_from_ram()qui fonctionnait sur le global random_seedau lieu d'utiliser un local seed. Cela pourrait conduire à ce que la graine soit XOR avec elle-même, détruisant toute l'entropie récoltée jusqu'à présent.

Si vous n'avez pas vraiment besoin d'entropie et que vous souhaitez simplement obtenir une séquence différente de nombres pseudo-aléatoires à chaque démarrage, vous pouvez utiliser l'EEPROM pour parcourir les graines consécutives. Techniquement, le processus sera complètement déterministe, mais en termes pratiques, il est beaucoup mieux que randomSeed(analogRead(0))sur une broche non connectée, ce qui vous fera souvent commencer avec la même graine de 0 ou 1023. L'enregistrement de la graine suivante dans EEPROM vous garantira que vous commencez avec une autre semer à chaque fois.

#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 vous avez besoin d'une véritable entropie, vous pouvez la collecter soit par dérive d'horloge, soit en amplifiant le bruit externe. Et si vous avez besoin de beaucoup d'entropie, le bruit externe est la seule option viable. La diode Zener est un choix populaire, surtout si vous avez une source de tension supérieure à 5-6V (elle fonctionnera également avec 5V avec une diode Zener appropriée, mais produira moins d'entropie):

( source ).

La sortie de l'amplificateur doit être connectée à une broche analogique, ce qui produira plusieurs bits d'entropie avec chacun analogRead()jusqu'à des dizaines de MHz (plus rapide que Arduino ne peut échantillonner).