AVR Zufallszahlengenerator

12

Ich habe eine Appnote von TI ( slaa338 ) gelesen , die eine Technik zur Erzeugung von Zufallszahlen "für echte" (im Gegensatz zu "Pseudo") beschreibt. Es nutzt das etwas exotische Clock-Subsystem des MSP430, um dieses Ziel zu erreichen. Kennt jemand eine Technik, die auf einem AVR implementiert werden kann (ich interessiere mich insbesondere für den XMega), um "für echte" Zufallszahlen zu generieren?

vicatcu
quelle
1
Pseudozufall funktioniert für Würfelspiele. Ich denke, er will kryptografisch sicher sein.
Kortuk
2
Können Sie einen Hinweis auf die Anwendung und / oder den Grad der Zufälligkeit geben, die Sie benötigen? Wenn es sich um Kryptographie handelt, gibt es neben der Qualität des Seeds noch weitere Überlegungen. Einige der bereits gemachten Vorschläge, wie die Probenahme von Umwelteinträgen verschiedener Art, können je nach Ihren Anforderungen angemessen sein oder auch nicht.
Windell Oskay

Antworten:

6

Wie schlecht kannst du den XMega benutzen? Wenn die Erzeugung von Krypto- und Zufallszahlen einen großen Teil Ihres Projekts ausmacht, dann ist Atmel's Krypto- bietet Atmels SecureAVR , verfügt Serie von über eine integrierte Hardware-Zufallszahl und wurde für kryptografische Anwendungen entwickelt.

Ungeachtet dessen bezweifle ich, dass Sie eine zufällige Samenquelle finden, die eine gute Verteilung aufweist. Sie werden es ein paar Mal durch einen Pseudozufallszahlengenerator laufen lassen wollen. Solange Sie jedes Mal mit einem anderen Startwert beginnen, erhalten Sie einen schönen Satz von Zufallszahlen. Ein LGC ist ein schneller und einfacher Pseudozufallsgenerator:

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
quelle
1
Das ist großartig, ich habe nicht bemerkt, dass die SecureAVR-Leitung existiert, danke für den Zeiger!
Vicatcu
Übrigens: Wenn Sie WIRKLICH Sicherheit brauchen, ist die einfache, effektive und schnelle LCG-Methode, die ich vorgestellt habe, nicht das, was Sie wollen: Viele LCGs können defekt sein. Holen Sie sich einfach 2-3 Werte hintereinander und stecken Sie sie in einen LCG-Generator mit einer Reihe bekannter Konstanten - dies würde alles auf der Wikipedia-Seite einschließen. Ein übereinstimmendes Muster lässt den Angreifer die nächste Zahl vorhersagen. Es ist möglich (aber schwieriger), die Konstanten auch aus dem Nichts herauszufinden.
Kevin Vermeer
1
@reemrevnivek FYI, Atmel verkauft seine SecureAVR-Linie ... sie empfehlen ihre ARM-basierten 32-Bit-Prozessoren, wenn Sie kryptografisches Material benötigen, das in Bezug auf die Entwicklungsumgebung ein völlig anderes Spiel darstellt als AVR. Sie haben ein Paar mit True RNGs, vielleicht spiele ich eines Tages mit ihnen.
Vicatcu
7

Schließen Sie den ADC an eine Hardware-Rauschquelle an und verwenden Sie Software, um die Zufallszahlen bei Bedarf "aufzuhellen".

Hier ist ein AVR-basiertes Projekt, das dies tut: Leons Mini Portable Random Number Generator (mPRNG)

Abhängig davon, wie kryptografisch sicher es sein muss, können Sie das Rauschen eines geerdeten Analogeingangs oder die " internen Temperatursensor" verwenden " als Zufallsgenerator anstelle externer Hardware verwenden.

Update : Ich habe später ein Programm für Arduino geschrieben, das die Timer des Chips als Entropiequelle verwendet (der ADC erwies sich als nutzlos, da die verrauschten Bits abgeschnitten sind), und dies hat die Erstellung der Entropy-Bibliothek inspiriert .

In beiden Fällen ergibt sich die Zufälligkeit nicht beispielsweise aus dem Temperaturwert selbst, der sich nur langsam ändert, sondern aus den niedrigstwertigen Bits , die sich zufällig von einem Lesevorgang zum nächsten ändern. Ich habe den Wert mehrmals gelesen, einmal für jedes Bit der Ausgabe, Bitverschiebung und XOR-Verknüpfung mit dem vorherigen Lesevorgang. Durch XOR-Verknüpfung eines wirklich zufälligen Bits mit einem nicht korrelierten Bit bleibt die Zufälligkeit erhalten , sodass sich die Zufälligkeit auf alle Bits verteilt und zu echtem weißem Rauschen wird. Ihre Bitrate wird jedoch nicht sehr hoch sein, da Sie nur ein Bit der Ausgabe pro Erfassungszeit oder Zeitgeberzyklus erhalten. Mit der Timer-Methode erhielt ich ungefähr 64 Bit / s.

Endolith
quelle
5
Das Benennen eines (mehr oder weniger zutreffenden) RNG "-PRNG" ist unglücklich.
Nick T
+1 für ADC, ich würde denken, dass Sie wahrscheinlich nach etwas suchen, das sich mit einer höheren Frequenz ändert als ein Temperatursensor.
Octopus
1
@Octopus Nun, Sie verwenden nicht die Temperatur als Entropiequelle, sondern die verrauschten niedrigstwertigen Bits, die sich bei jedem Lesen des ADC zufällig ändern, selbst wenn die Temperatur konstant ist. Als ich auf Arduino getestet habe, waren diese Bits immer 0, also war es nicht machbar und ich musste stattdessen eine Timer-Variation verwenden. Auf einer anderen MCU, auf der ich diese Methode angewendet habe, waren die LSBs des ADC verrauscht und verwendbar.
Endolith
3

Ein weiterer Trick zum Erzeugen eines zufälligen Startwerts besteht darin, die Anzahl der Taktzyklen bis zu einem externen Ereignis zu zählen. Wenn es sich beispielsweise um ein Gerät handelt, das von einer Person verwendet werden soll, zählen Sie die Anzahl der Taktzyklen, bis diese Person den Startknopf drückt, und verwenden Sie diesen als zufälligen Startwert.

davr
quelle
4
Dies ist möglicherweise nicht sehr sicher gegen Seitenkanalangriffe, da diese durch die Steuerung eines Geräts eindringen können. Wie bei allen Kryptografien entscheidet die Anwendung jedoch über die Durchführbarkeit.
Kortuk
3

Um nicht mit derselben Sequenz neu zu starten, verwende ich somme byte im 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());
        [...]
 }

Dies gibt ziemlich gute Zufallszahlen und kostet nicht viel im Programm / Speicher.

jojo l'abricot
quelle
2
Dies liest jedes Mal Byte 0. Welchen Beweis haben Sie, dass dieses Byte zufällig ist? Wenn ja, ist dies eine großartige Technik!
Kevin Vermeer
Dieses Wort (Byte 0 & 1) wird zufällig sein, da ich bei jedem Start den Zufallsgenerator mit seinem Inhalt initialisiere. DANN lade ich es mit einem neuen Rand hoch (). Der nächste Init sieht also zufällig aus ... und so weiter ... Aber wenn ich randinit auf ffff (oder 0000?) Zurücksetze, habe ich dieselbe randinit-Sequenz! Es ist also nicht perfekt. Ich habe eine Warnung über die Sicherung vergessen, die das EEPROM löscht, wenn das * .hex hochgeladen wird;)
jojo l'abricot
3

Ich habe eine Bibliothek erstellt, die zwar ursprünglich für das Arduino entwickelt wurde, aber als Klasse in einer C ++ - Implementierung mit g ++ auf dem avr gut funktioniert, in der Tat wurde sie kürzlich auch auf die ARM-Architektur portiert.

Es nutzt den Jitter zwischen Watchdog-Timer und Systemuhr und wurde auf verschiedenen Chips getestet (auf der Wiki-Seite dokumentiert).

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

Walter Anderson
quelle
2

Hast du dir mal so etwas angeschaut randomSeed () beschäftigt ? - In der Arduino IDE verwendet

Mit dieser Funktion können Sie einen schwebenden (freien) analogen Pin am atmel AVR abtasten. Anschließend wird anhand des Werts ein beliebiger Startpunkt für das Pseudo erstellt - random () - erstellt.

Der mit random () erzeugte Wert kann eine Pseudozufallszahl sein - der mit randomSeed () erzeugte willkürliche Startpunkt sollte jedoch so real wie möglich sein.

Jim
quelle
2
Das Abtasten von Dingen wie den analogen Pins ist nahezu zufällig, weist jedoch keine gleichmäßige Verteilung auf. Lasse den Samen jedoch ein paar Mal zufällig durchlaufen, und das wird es auch.
Kevin Vermeer
.... durch einen Pseudo-Zufallszahlengenerator ein paar ... <- Wie ist das verschwunden? NTS: Zuerst das Gehirn einschalten, dann die Finger.
Kevin Vermeer
Genau - Es ist auch nicht das Sicherste, wenn es für Verschlüsselung / Schutz usw. verwendet wird, aber es gibt Ihnen eine nette Zufallszahl für etwas wie generative Musik oder Würfelspiele. Es ist gut und einfach zu implementieren :)
Jim
1

Es gibt ein Papier darüber, wie dies mit AVR-Hardware erreicht werden kann. Dabei wird auf Clock Jitter zurückgegriffen. Grundsätzlich verwenden Sie einen Timer-Interrupt, der auf einer Taktquelle basiert, um die unteren Bits eines separaten Timers abzutasten, der von einer separaten unabhängigen Taktquelle getaktet wird. Mit den beiden Takten ist ein zufälliger Jitter verbunden, und die Abtastung ist nicht perfekt periodisch.

Ich habe auf einem STM32-Mikrocontroller einen kleinen Proof of Concept gemacht, Code ist hier auf Github . Basierend auf einer Reihe von Randomisierungstestsuiten wurden einige gute Ergebnisse erzielt.

Meiner Meinung nach ist dies besser, als einen schwebenden Pin mit einem ADC abzutasten, der extrem leicht anzugreifen ist (binde den Pin an den Boden und deine Zahl ist nicht mehr so ​​zufällig!). Ich bin mir sicher, dass es eine Möglichkeit gibt, ein auf Clock-Jitter basierendes RNG zu manipulieren, aber ich fühle mich ein bisschen besser, wenn ich dies rein auf der Basis von internen Clock-Quellen auf dem Chip tun kann.

Jon L
quelle