Générateur de nombres aléatoires AVR

12

J'ai lu une note de TI ( slaa338 ) qui décrit une technique pour générer des nombres aléatoires "pour de vrai" (par opposition à "pseudo"). Il exploite le sous-système d'horloge quelque peu exotique du MSP430 pour atteindre cet objectif. Est-ce que quelqu'un connaît une technique qui peut être implémentée sur un AVR (je suis intéressé par les XMega en particulier) pour générer des nombres aléatoires "pour de vrai"?

vicatcu
la source
1
psuedo aléatoire fonctionne pour les jeux de dés. Je pense qu'il veut une sécurité cryptographique.
Kortuk
2
Pouvez-vous donner un indice sur l'application et / ou le degré de hasard dont vous avez besoin? Si c'est pour la cryptographie, il y a des considérations supplémentaires en plus de la qualité des semences. Certaines des suggestions déjà faites - comme l'échantillonnage des intrants environnementaux de divers types peuvent ou peuvent ne pas être appropriées en fonction de vos besoins.
Windell Oskay

Réponses:

6

Dans quelle mesure utilisez-vous le XMega? Si la génération de crypto et de nombres aléatoires est une grande partie de votre projet, la série SecureAVR d'Atmel a un nombre aléatoire matériel intégré et est conçue pour les applications cryptographiques.

Quoi qu'il en soit, je doute que vous trouverez une source de graines aléatoire qui a une bonne distribution. Vous voudrez l'exécuter plusieurs fois à travers un générateur de nombres pseudo-aléatoires Tant que vous commencez avec une graine différente à chaque fois, cela vous donnera un bel ensemble de nombres aléatoires. Un LGC est un générateur pseudo aléatoire rapide et facile:

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
la source
1
C'est génial, je ne savais pas que la ligne SecureAVR existait, merci pour le pointeur!
vicatcu
BTW: Si vous avez VRAIMENT besoin de sécurité, la méthode LCG simple, efficace et rapide que j'ai présentée n'est pas ce que vous voulez: de nombreux LCG peuvent être cassés; obtenez simplement 2-3 valeurs d'affilée et branchez-les dans un générateur LCG avec un ensemble de constantes connues - cela inclurait tout sur la page Wikipedia. Un schéma correspondant permettra à l'attaquant de prédire quel sera le prochain numéro. Il est également possible (mais plus difficile) de comprendre quelles sont les constantes à partir de rien.
Kevin Vermeer
1
@reemrevnivek FYI, Atmel vend sa gamme SecureAVR ... ils recommandent leurs processeurs 32 bits basés sur ARM si vous voulez des trucs cryptographiques qui sont un jeu de balle complètement différent en termes d'environnement de développement d'AVR. Cependant, ils ont un couple avec True RNGs, peut-être que je jouerai avec eux un jour.
vicatcu
7

Connectez l'ADC à une source de bruit matériel et utilisez un logiciel pour "blanchir" les nombres aléatoires si nécessaire.

Voici un projet basé sur AVR qui fait cela: Mini générateur portable de nombres aléatoires de Leon (mPRNG)

Selon le niveau de sécurité cryptographique qu'il faut, vous pouvez utiliser le bruit d'une entrée analogique mise à la terre ou du " capteur de température interne " comme source d'aléatoire au lieu d'un matériel externe.

Mise à jour : j'ai écrit plus tard un programme pour Arduino qui utilise les minuteries de la puce comme source d'entropie (l'ADC s'est avéré inutile parce que les bits bruyants sont tronqués), et cela a inspiré la création de la bibliothèque Entropy .

Dans les deux cas, le caractère aléatoire ne provient pas, par exemple, de la valeur de température elle-même, qui ne change que lentement, mais des bits les moins significatifs , qui varient de manière aléatoire d'une lecture à l'autre. J'ai lu la valeur plusieurs fois, une fois pour chaque bit de sortie, décalage de bits et XORing avec la lecture précédente. XOR un bit vraiment aléatoire avec un bit non corrélé préserve le caractère aléatoire , de sorte que le caractère aléatoire se propage à tous les bits et il devient un vrai bruit blanc. Cependant, votre débit binaire ne sera pas très élevé, car vous n'obtenez qu'un seul bit de sortie par temps d'acquisition ou cycle de minuterie. Avec la méthode de la minuterie, j'obtenais environ 64 bits / s.

endolith
la source
5
Nommer un RNG (plus ou moins vrai), "-PRNG" est regrettable.
Nick T
+1 pour ADC, je pense que vous recherchez probablement quelque chose qui change à une fréquence plus élevée qu'un capteur de température.
Octopus
1
@Octopus Eh bien, vous n'utilisez pas la température comme source d'entropie, vous utilisez les bits les moins significatifs bruyants, qui changeront aléatoirement chaque fois que vous lirez l'ADC même si la température est constante. Quand j'ai testé sur Arduino, cependant, ces bits étaient toujours à 0, donc ce n'était pas faisable et j'ai dû utiliser la variation de la minuterie à la place. Sur un autre MCU sur lequel j'ai utilisé cette méthode, les LSB de l'ADC étaient bruyants et utilisables.
endolith
3

Une autre astuce pour générer une graine aléatoire est de compter le nombre de cycles d'horloge jusqu'à un événement externe. Par exemple, s'il s'agit d'un appareil à utiliser par une personne, comptez le nombre de cycles d'horloge jusqu'à ce qu'il appuie sur le bouton «Aller» et utilisez-le comme graine aléatoire.

davr
la source
4
Cela peut ne pas être très sécurisé contre les attaques par canal latéral car elles peuvent s'introduire en sécurisant le contrôle d'un appareil, mais comme pour toute cryptographie, l'application détermine la faisabilité.
Kortuk
3

Pour être sûr de ne pas redémarrer avec la même séquence, j'utilise somme octet dans l'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());
        [...]
 }

Cela donne un assez bon aléatoire et ne coûte pas cher en programme / mémoire.

jojo l'abricot
la source
2
Cela lit l'octet 0 à chaque fois. Quelle preuve avez-vous que cet octet est aléatoire? Si c'est le cas, c'est une excellente technique!
Kevin Vermeer
Ce mot (octets 0 et 1 en fait) sera aléatoire, car à chaque démarrage j'initialise le générateur aléatoire avec son contenu. PUIS je le télécharge avec un nouveau rand (). Donc, le prochain init sera aléatoire par rapport au courant ... et ainsi de suite ... Mais si je réinitialise randinit à ffff (ou 0000?), J'aurai la même séquence randinit! Ce n'est donc pas parfait. J'ai oublié un avertissement concernant le fusible qui efface l'eeprom lors du téléchargement du * .hex;)
jojo l'abricot
3

J'ai créé une bibliothèque qui, bien qu'originale conçue pour l'Arduino, fonctionne bien en tant que classe dans une implémentation C ++ utilisant g ++ sur l'avr, en effet, elle a récemment été portée également sur l'architecture ARM.

Il utilise la gigue entre le minuteur de surveillance et l'horloge système et a été testé sur un certain nombre de puces différentes (documentées sur la page wiki)

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

Walter Anderson
la source
2

Avez-vous envisagé d'utiliser quelque chose comme randomSeed () ? - utilisé dans l'IDE Arduino

Vous pouvez utiliser cette fonction pour échantillonner une broche analogique flottante (gratuite) sur l'AVR atmel, elle utilise ensuite la valeur pour créer un point de départ arbitraire pour la pseudo fonction de nombre aléatoire - random ().

La valeur créée par random () peut être un nombre pseudo aléatoire - mais le point de départ arbitraire créé par randomSeed () doit être un nombre / valeur aléatoire aussi réel que possible.

Jim
la source
2
L'échantillonnage de choses comme les broches analogiques est presque aléatoire, mais n'aura pas une distribution uniforme. Exécutez la graine au hasard plusieurs fois, cependant, et ce sera le cas.
Kevin Vermeer
.... grâce à un générateur de nombres pseudo aléatoires un couple ... <- Comment cela a-t-il disparu? NTS: Engagez d'abord le cerveau, puis les doigts.
Kevin Vermeer
Exactement - Ce n'est pas non plus le plus sûr si vous l'utilisez pour le cryptage / protection, etc., mais il vous donnera un bon nombre aléatoire pour quelque chose comme la musique générative ou les jeux de dés. Il est bon et facile à mettre en œuvre aussi :)
Jim
1

Il y a un papier sur la façon d'y parvenir avec le matériel AVR. Cela implique de s'appuyer sur la gigue d'horloge. Fondamentalement, vous utilisez une interruption de minuterie basée sur une source d'horloge pour échantillonner les bits inférieurs d'une minuterie distincte qui est cadencée sur une source d'horloge indépendante distincte. Les deux horloges seront associées à une gigue aléatoire et l'échantillonnage ne sera pas parfaitement périodique.

J'ai fait une petite preuve de concept de cela sur un microcontrôleur STM32, le code est sur github ici . Il a obtenu de bons résultats basés sur un ensemble de suites de tests de randomisation.

À mon avis, je pense que c'est mieux que d'échantillonner une broche flottante avec un ADC qui est extrêmement facile à attaquer (attachez la broche à la terre et votre numéro n'est plus si aléatoire!). Je suis sûr qu'il existe un moyen de manipuler un RNG basé sur la gigue d'horloge, mais cela me fait un peu mieux de pouvoir le faire uniquement à partir de sources d'horloge interne sur puce.

Jon L
la source