HardRNG

In den frühen Jahren der Firma Intel - genauer im Jahr 1976 - gab es ein Problem mit 15K-CCD-Speicherchips. Bei diesen traten, aus Gründen die niemand erklären konnte, zufällige Bitfehler auf. Intel brauchte ein Jahr, um herauszufinden, dass es nicht an kosmischer Strahlung oder durch die Miniaturisierung hervorgerufenen Effekten im Halbleiter lag. Es war die minimale Radioaktivität der in dieser Zeit eingeführten schwarzen Keramikgehäuse. Die durch den radioaktiven Zerfall der Keramik ausgesandten Alphateilchen störten die Schaltkreise des Chips und führten zu Bitfehlern. Da der Alphazerfall ein quantenmechanisches Phänomen ist, traten die Fehler natürlich zufällig und über den gesamten Chip verteilt auf. Damals war dieser Effekt natürlich ein Ärgernis und Intel musste zusammen mit seinem Zulieferer die Rezeptur der Keramik anpassen, damit diese keine Alphateilchen mehr aussandte. 1 Heute sind Computer sehr zuverlässig und die Fehlerraten der Hardware sind derart gering, dass ein moderner Rechner mehrfach durch einen Softwarefehler abgestürzt ist, bevor überhaupt ein einzelnes Bit im Arbeitsspeicher umkippen kann. Hierdurch entsteht allerdings ein neues Problem: Für einige Anwendungsfälle ist es notwendig, guten Zufall zu erzeugen. Doch in einem Computer, welcher deterministisch sein Programm abarbeitet, ist dies ausgesprochen schwierig. Bei der Verschlüsselung im Internet, beim Erzeugen von elektronischen Zertifikaten, zur Generierung von Kennwörtern, für die Simulation von physikalischen Prozessen oder bei der Auswahl von repräsentativen Stichproben aus Datenmaterial, überall kommen Zufallszahlen zum Einsatz. Aber woher bekommt man nun gute Zufallszahlen? Pseudozufallsgeneratoren (PRNG) erzeugen Zahlenwerte, deren Abfolge einem außenstehenden Betrachter zufällig erscheint. In Wirklichkeit handelt es sich jedoch um die Ergebnisse eines Algorithmus, dessen nächster Ausgabewert sich, bei Kenntnis aller Variablen, durchaus vorhersagen lässt. Sie sind also nur so lange sicher, wie ein Außenstehender nicht alle internen Variablen des PRNG kennt und die Berechnung dieser Variablen, aus den für ihn sichtbaren Zufallszahlen, nur mit immensem Rechenaufwand und viel Zeit erledigt werden kann. Auch die Nutzung dieser Zufallszahlen für Simulationen ist nicht völlig unkritisch. Es kann nie ganz ausgeschlossen werden, dass Eigenschaften (z. B. Muster) des verwendeten Algorithmus unvorhergesehene Auswirkungen auf das Simulationsergebnis haben. Dass das Design eines kryptografisch sicheren PRNG ein anspruchsvolles Problem darstellt, zeigt die Schwäche im Zufallsgenerator Dual EC DRBG. 2006 wurden erste Zweifel daran laut, dass dieser Generator die Anforderungen an kryptografisch sichere Zufallszahlen erfüllt. Die Situation spitzte sich zu, bis der Algorithmus schließlich im April 2014 - 8 Jahre später - vom NIST zurückgezogen wurde. Pseudozufallsgeneratoren bergen immer das Risiko, das im verwendeten Algorithmus Schwachstellen gefunden werden, welche eine Vorhersage der Zufallszahlen erlauben. Da liegt es nahe, Zufallszahlen aus physikalischen Prozessen zu gewinnen, welche sich von Natur aus nicht vorausberechnen lassen. Quantenphänomene sind, da sie per Definition zufällig sind, natürlich die erste Wahl. Es gibt jedoch auch andere physikalische Effekte, die sich aufgrund ihrer Komplexität einer - über die statistische Erfassung hinausgehenden - Vorhersage entziehen. Diese als Quelle für Zufallszahlen zu verwenden, beseitigt das mit den Algorithmen von Pseudozufallsgeneratoren verbundene Risiko. Allerdings hat auch das Design eines funktionierenden Hardwarezufallsgenerators seine Tücken. Im Folgenden sind die Überlegungen und Berechnungen für die Konstruktion des Zufallsgenerators HardRNG dargestellt, sodass diese geprüft und nachvollzogen werden können. Hätte Intel 1976 gewusst, welche Rolle Zufallsgeneratoren einmal in der IT spielen, sie hätten ihre radioaktiven Chips bestimmt anders vermarktet.

Warum ein Zufallsgenerator?

Seit mehreren Jahren beschäftige ich mich beruflich mit der praktischen Seite der Kryptographie. Natürlich gehört die Erzeugung kryptografisch sicherer Zufallszahlen hier zu einer der Standardaufgaben. Normalerweise werden hierfür Smartcards oder HSM 2 eingesetzt. Für den privaten Einsatz und um damit herum zu experimentieren sind HSM natürlich zu teuer. Smartcards sind zwar leicht zu beschaffen und preiswert, jedoch halten sich die Möglichkeiten für den Zugriff auf den Zufallsgenerator in engen Grenzen. Außerdem ist die Dokumentation für die zur Erzeugung der Zufallszahlen verwendeten Verfahren meist nicht zugänglich. Von Änderungen an Hardware oder Firmware ganz zu schweigen.

Warum noch ein Zufallsgenerator?

Im Internet gibt es viele Schaltungsvorschläge für Rauschgeneratoren und einige sind sogar zu Zufallsgeneratoren erweitert worden. Viele der Schaltungen nutzen ebenfalls einen Rauschgenerator als Zufallsquelle. Allerdings wird dessen Signal meistens über einen Analog-Digital-Wandler konvertiert und anschließend weiterverarbeitet. Das Problem dieser Schaltung ist, dass sie keine guten Zufallsgeneratoren darstellen. Das digitale Sampling des Rauschsignals ist fehleranfällig:

  • Durch das regelmäßige Sampling können hochfrequente Störungen auf den erzeugten Zufallsdatenstrom durchschlagen. Der Analog-Digital-Wandler wirkt in diesem Fall wie ein Synchrondemodulator.
  • Gerade wenn vom gewandelten Signal nur die niederwertigsten Bits genutzt werden kann der Quantisierungsfehler des Analog-Digital-Wandlers für eine Verschiebung in der Verteilung der Werte sorgen.
  • Zwischen den einzelnen Samples muss ausreichend Zeit vergehen, damit die einzelnen Werte nicht korreliert sind. Wird zu schnell abgetastet, sind die einzelnen Werte voneinander abhängig, da das Signal sich nicht sprunghaft ändern kann. Begrenzender Faktor ist hierbei die Bandbreite des analogen Teils der Schaltung.
  • Wird das Rauschsignal vor der Anlog-Digital-Wandlung verstärkt, muss die Kennlinie des Verstärkers berücksichtigt werden. Ist diese nicht linear wird das Signal verzerrt. Dies verschiebt ebenfalls die Häufigkeitsverteilung der Werte, was zu Artefakten in der digitalen Zufallsfolge führt.

Zusammenfassend war der Grund für das Design des HardRNG die Neugierde, ob sich ein zuverlässiger Zufallsgenerator mit leicht zu beschaffenden, kostengünstigen Bauteilen realisieren lässt. Das verwendete Verfahren soll die oben genannten Schwächen nicht besitzen und trotzdem leicht nachvollziehbar sein. Die Komponenten des Generators sind als Open Hardware bzw. Open Source Software verfügbar. Jeder kann das System nachbauen und selbst Messungen oder Modifikationen daran vornehmen.

Grundbegriffe

Wahrscheinlichkeit

Die Wahrscheinlichkeit gibt die relative Häufigkeit eines Ereignisses in einer unendlichen Anzahl an Versuchen an. Wirft man eine perfekte Münze 500-mal, sollte diese ebenso oft auf Kopf, wie auf Zahl fallen. Auch bei 1.000, 10.000 oder 100.000 Würfen müssen beide Ergebnisse gleich häufig auftreten. Die Wahrscheinlichkeit für Kopf liegt also, ebenso wie die für Zahl, bei 50 %. Das Rechnen mit Prozentwerten wird etwas sperrig, wenn komplexere Ergebnisse ins Spiel kommen. Bei einem Würfel beträgt die Wahrscheinlichkeit für jedes der sechs Ergebnisse $16 2/3\%$. Doch wie wahrscheinlich ist es, eine Eins oder eine Sechs zu würfeln? Natürlich kann man die Wahrscheinlichkeit für eine Eins mit der für eine Sechs addieren. Einfacher ist jedoch folgende Überlegung: Die Wahrscheinlichkeit von zwei bestimmten Ergebnissen innerhalb von sechs Möglichkeiten liegt bei 2 von 6 oder $2/6$. Die Wahrscheinlichkeit eines anderen Ergebnisses liegt demnach bei 4 von 6 oder $4/6$.

Entropie

Die Entropie ist ein Begriff aus der Informationstheorie. Sie gibt den Informationsgehalt eines Datenstroms an. Je weniger sich das nächste Bit in einem Datenstrom vorhersagen lässt, desto größer ist die Entropie. Die Folge 01010101 hat also eine Entropie nahe 0, da das nächste Bit leicht vorhersagbar ist. Eine reine Zufallsfolge hat eine Entropie von 1, da das nächste Bit nicht vorhergesagt werden kann. Datenkompressionsalgorithmen führen eine Redundanzreduktion durch. Informationen, welche sich aus anderen Daten ableiten lassen, werden aus dem Datenstrom entfernt. Die Informationsdichte (und damit die Entropie) des komprimierten Datenstromes ist größer als die der Ausgangsdaten. Liegt die Entropie eines Datenstromes jedoch schon nahe 1, kann diese durch Datenkompression nicht weiter gesteigert werden. Es gibt keine überflüssigen Informationen, welche weggelassen werden können. Eine perfekte Zufallsfolge ist daher nicht komprimierbar.

Artefakt

Bei einem Zufallsgenerator bezeichnet ein “Artefakt” einen Signalanteil, welcher nicht vom Zufallsprozess erzeugt wird, sondern durch die Verarbeitung oder äußere Beeinflussung entsteht. Artefakte sind normalerweise nicht zufällig und verringern die Entropie des erzeugten Datenstroms. Schlimmstenfalls überlagert ein Artefakt das Signal des Zufallsprozesses derart, dass nur noch der vorhersagbare Anteil des Artefakts in die Zufallserzeugung einfließt. In diesem Fall können keine brauchbaren Zufallenzahlen mehr erzeugt werden.

Zufall in Hardware

Es gibt einen deutlichen Unterschied zwischen erratischem Verhalten und Zufall. So sind beispielsweise Schwingungsgeneratoren welche ein chaotisches Verhalten zeigen, nicht geeignet kryptografisch nutzbaren Zufall zu erzeugen. Zwar sind die, durch diese Schaltungen generierten, Signale komplex und ergeben auf dem Oszilloskopbildschirm schöne Muster, die erzeugten Schwingungen sind allerdings kontinuierlich. Somit kann von einer Koordinate auf die ungefähre Position der nächsten geschlossen werden. Die einzelnen Werte sind zu sehr voneinander abhängig (korreliert) als dass sich aus diesen Zufallszahlen ableiten ließen.

Diodenkennlinie Eine schon seit Jahrzenten in Rauschgeneratoren verwendete und sehr robuste Methode zur Erzeugung zufälliger Muster ist die Nutzung einer Diode in Sperrrichtung: Halbleiterdioden bestehen in der Regel aus einem pn-Übergang 3. In dem Bereich, in welchem die p-dotierte Halbleiterschicht mit der n-dotierten in Berührung kommt, entsteht eine Sperrschicht. Der Elektronenüberschuss im n-Halbleiter und die fehlenden Elektronen im p-Halbleiter (Löcher) rekombinieren, wodurch ein Mangel an frei beweglichen Ladungsträgern (Elektronen oder Löchern) entsteht. Legt man nun eine positive Spannung an den n-Halbleiter und eine negative an den p-Halbleiter, verstärkt sich das elektrische Feld im Halbleiter. Noch mehr Elektronen rekombinieren mit den Löchern, die Sperrschicht wächst und es stehen noch weniger freie Ladungsträger zur Verfügung: Die Diode sperrt. Erhöht man die Spannung weiter, nimmt auch die Stärke des elektrischen Feldes in der Sperrschicht zu. Damit steigt die kinetische Energie der Elektronen im Halbleiterkristall. Ist diese groß genug, können die, durch das elektrische Feld beschleunigten, Elektronen andere Elektronen aus den Atomen des Halbleiters herausschlagen. Diese stehen dann als freie Ladungsträger zur Verfügung und werden ihrerseits durch das elektrische Feld beschleunigt. Weitere Stöße lösen immer mehr Elektronen von ihren Atomen. Die Diode wird in Sperrrichtung leitend. Diesen Effekt nennt man Lawinendurchbruch. Die Spannung, bei welcher der Stromfluss in Sperrrichtung einsetzt, wird durch die Durchbruchspannung (UBR ) beschrieben. Solange während des Durchbruchs die Wärmeentwicklung durch die Verlustleistung unter dem zulässigen Wert (Ptot ) bleibt, ist der Vorgang ohne weitere Schäden reversibel. Wann die Elektronen die notwendige Geschwindigkeit erreichen und wann sie weitere Elektronen aus ihrer Umlaufbahn um den Atomkern schlagen, ist von vielen Faktoren abhängig. Statistisch gesehen bestimmen Umgebungstemperatur, der physikalische Aufbau des Halbleiters sowie Fertigungstoleranzen den Zeitpunkt des Lawinendurchbruchs. Der exakte Zeitpunkt eines bestimmten Durchbruchsereignisses ist auf atomarer Ebene zufällig und nicht vorherzusagen. Kennline der B-E-Strecke eines BC548C Dioden sind darauf optimiert, eine hohe Rückwärtsspannung ohne Durchbruch zu verkraften. Zehnerdioden, welche zur Spannungsstabilisierung verwendet werden, sind zwar mit Durchbruchspannungen unter 5 V erhältlich, jedoch ist aufgrund des, unter 5 V bei Zehnerdioden zum Tragen kommenden Tunneleffektes, die Fluktuation (der Rauschanteil) im Durchbruchstrom gering. Im Prinzip muss die schlechteste erhältliche Diode gefunden werden. Transistoren bieten sich hier an. Sie bestehen aus zwei pn-Übergängen, von denen einer als Diode verwendet werden kann. Da dieser pn-Übergang bei Kleinsignaltransistoren nicht auf eine hohe Durchbruchspannung optimiert ist, eignen sie sich gut als Rauschgeneratoren. Die obige Grafik zeigt die gemessene Spannungs/Strom-Kennlinie für die Basis-Emitter-Strecke eines BC548C Transistors. Diese wurde mit einem Vorwiderstand von 68 kΩ an einer Spannung zwischen 2 V und -9 V aufgenommen. Der breite Mittelteil wird durch die hohe Verstärkung bei der Strommessung erzeugt. Die Grafik zeigt deutlich, dass in Sperrrichtung erst bei 8 V 4 ein Durchbruchstrom zu fließen beginnt. Damit ist klar, dass die am USB verfügbare Spannung von 5 V trotz der Verwendung eines Transistors nicht ausreicht, um einen Lawinendurchbruch auszulösen.

HardRNG

Designziele

Während des Entwurfs des Zufallsgenerators HardRNG mussten etliche Designentscheidungen getroffen werden. Um dies zu vereinfachen, wurden die folgenden Designziele festgelegt:

Hardware

  • Ausführung als USB-Stick zum direkten Anstecken an das Zielsystem.
  • Ausschließliche Nutzung von, über gängige Distributoren erhältlichen, Standardbauteilen.
  • Bestückung in SMD-Technik, jedoch mit Bauteilen, welche sich noch von Hand löten lassen (mindestens Baugröße 0805, besser 1206).
  • Alle wichtigen Signale müssen mit gängigen Messinstrumenten überprüft werden können.
  • Es dürfen keine manuellen Einstellarbeiten erforderlich sein.
  • Unempfindlich gegen Störungen und Bauteiletoleranzen.

Software

  • USB-Schnittstelle mit CDC Geräteklasse, sodass diese unter Linux ohne weitere Treiber unterstützt wird.
  • Ausschließliche Nutzung quellenoffener Bibliotheken.
  • Einfache, leicht nachvollziehbare Aufbereitung der Zufallswerte.

Blockdiagramm

Blockdiagramm Das Blockdiagramm zeigt die einzelnen Bestandteile des HardRNG Zufallsgenerators. Die gelben Funktionsblöcke sind diskret auf der Platine aufgebaut. Orange sind die Blöcke hervorgehoben, welche in der Hardware des verwendeten Mikrocontrollers integriert sind. In Software implementierte Funktionsblöcke sind blau dargestellt. In den nächsten Kapiteln werden nun die einzelnen Funktionsblöcke beschrieben.

Funktionsbeschreibung

Schaltplan Der Schaltplan und das Blockschaltbild werden noch häufiger referenziert. Es ist hilfreich, diese beim Lesen neben den Text zu legen, um die Funktion der Schaltung besser nachvollziehen zu können.

USB-Schnittstelle

Die meisten Open-Hardware-Zufallsgeneratoren verwenden eine Serielle-Schnittstelle zur Übergabe der Daten an das Zielsystem. Heutzutage ist ein RS232-Anschluss an den meisten Systemen nicht mehr zu finden. Insofern muss ein moderner Zufallsgenerator eine USB-Schnittstelle besitzen. Um die Kompatibilität mit bestehender Software zu erhalten, soll natürlich auf Betriebssystemebene wieder eine serielle Schnittstelle zur Verfügung stehen. USB-Geräte, welche die Geräteklasse CDC (Communication Device Class) implementieren, erfüllen diese Anforderung, da das Betriebssystem für diese Geräte eine serielle Schnittstelle emuliert. So kann bestehende, auf seriell angebundene Zufallsgeneratoren ausgelegte, Software ohne Änderungen weiterverwendet werden. Für die Implementierung wird ein Mikrocontroller mit integrierter USB-Schnittstelle verwendet. Diese Entscheidung hat mehrere Gründe:

  • Die Geräteklasse CDC steht lt. USB-Spezifikation nur für Geräte zur Verfügung, welche mindestens die Schnittstellengeschwindigkeit FullSpeed bereitstellen. Dies ist mit einem Software-USB-Stack nicht möglich.
  • Die meisten Software-USB Implementierungen verletzen Teile der USB-Spezifikation, was zu Kompatibilitätsproblemen führen kann.
  • Ohne spezialisierte Hardware ist viel Rechenleistung für die USB-Kommunikation notwendig.

Das USB-Framework LUFA bietet für AVR Mikrocontroller eine umfassende und ausgereifte USB-Bibliothek, welche die Implementierung der CDC-Geräteklasse stark vereinfacht. LUFA steht unter der MIT-Lizenz und kann somit für quellenoffene und geschlossene, kommerzielle Projekte verwendet werden. Für den HardRNG wird nur ein Bruchteil der vorhandenen Funktionen genutzt. Ausführliche Informationen und Codebeispiele finden sich auf der Webseite “http://www.fourwalledcubicle.com/". Bei der Hardware der USB-Schnittstelle gibt es keine Besonderheiten. Die Abschlusswiderstände R1 und R2 entsprechen den Werten aus dem Datenblatt. Es wird die Standardtopologie für busgespeiste USB-Geräte verwendet. Leider legt die USB-Spezifikation die Verbindung zwischen Abschirmung des USB-Anschlusses und der Gerätemasse nicht eindeutig fest. Die beiden Punkte auf Geräteseite direkt miteinander zu verbinden kann zu einer Masseschleife führen, da die meisten USB-Hosts bereits Abschirmung und Masse koppeln. Je nach Quelle im Internet und Hersteller werden verschiedene Optionen empfohlen. Atmel spricht sich in der Application-Note AVR1017 für eine Kombination aus 1 MΩ Widerstand und 4,7 nF Kondensator aus. Obwohl die Empfehlung für die Mikrocontroller der XMega-Serie gedacht ist, habe ich mich in der Schaltung für diese Kombination entschieden. Test mit unterschiedlichen USB-Hosts und Kabellängen haben gezeigt, dass damit eine stabile Übertragung gewährleistet ist.

Spannungsversorgung

Die USB-Betriebsspannung von 5 V wird über zwei L-C-Filter in die beiden internen Versorgungsspannungen VCC und VAA aufgeteilt. Die Filter bestehen aus einer Induktivität von 100 µH und einem Low-ESR-Kondensator mit 2,2 µF Kapazität. Damit ergibt sich eine Grenzfrequenz von 10 kHz, welche ausreichend klein ist, um Störungen durch die Signale auf dem USB zu unterdrücken. Die Aufteilung der Versorgungsspannung in zwei getrennt gefilterte Spannungen für den analogen (VAA) und den digitalen (VCC) Schaltungsteil stellt darüber hinaus sicher, dass die Schaltflanken aus dem Digitalteil nicht in den Analogteil übersprechen. Für die Filter- und Abblockkondensatoren in der Schaltung muss beachtet werden, dass die USB-Spezifikation in Kapitel 7.2.4.1 (Inrush Current Limiting) eine Obergrenze von 10 µF für alle Kapazitäten definiert, welche direkt mit der Spannungsversorgung des USB verbunden sind. Alle mit VBUS verbundenen Kapazitäten addieren sich zu 3,2 µF. Alle weiteren Kapazitäten sind über L-C-Filter mit VBUS verbunden. Diese reduzieren durch ihre Induktivität den Einschaltstromstoß. Auch C15 und C16 werden im Moment des Einsteckens über D3 und D4 auf etwa 3,8 V geladen. Auch hier verhindert das L-C-Filter am Eingang, dass der Stromstoß das Maximum der USB-Spezifikation von 500 mA übersteigt. Rechnerisch beträgt der Stromstoß, welcher durch die Spulen und die Induktivität des USB-Kabels bis nach dem Laden der direkt verbundenen Eingangskapazitäten verzögert wird, 500 mA für 250 µs. Die Anstiegszeit liegt bei etwa 8 mA/µs, was weit unter der Vorgabe aus Kapitel 7.2.3 (Power Control During Suspend/Resume) von maximal 100 mA/µs liegt.

Ladungspumpe, Puffer und Spannungsreferenz

Die USB-Spannung von 5 V reicht nicht aus, um bei gängigen Transistortypen einen Lawinendurchbruch für die Erzeugung von Zufallszahlen auszulösen. Der verwendete Transistor vom Typ BC848C hat laut Datenblatt eine Durchbruchspannung der Basis-Emitter-Diode von 6 V. Diese kann allerdings aufgrund von Exemplarstreuungen auch bei bis zu 10 V liegen. Aus diesem Grund ist eine Spannungsvervielfacherschaltung notwendig. Der Stromfluss durch T1 und den Spannungsteiler für die Überwachung von VBrkDwn ist so gering, dass problemlos auf eine Ladungspumpenschaltung zurückgegriffen werden kann. Die Dioden D3 und D4 bilden zusammen mit C10, C11, C15 und C16 eine Dickson-Ladungspumpe. Die Widerstände R5 und R6 schützen die Ports des Mikrocontrollers vor Überlastung. An den Doppel-Schottky-Dioden vom Typ BAT54S tritt anfänglich ein Spannungsfall von 0,6 V auf. Je weiter sich die Spannung an C15 und C16 der Schlussspannung nähert, desto geringer wird der Stromfluss durch die Dioden. Hierdurch reduziert sich auch der Spannungsfall auf etwa 0,3 V, sodass die Spitzenspannung bei etwa 14,1 V liegt. Um auch bei ungünstiger Exemplarstreuung der Dioden das Ende des Ladevorgangs sicher erkennen zu können, wird die Schlussspannung auf 13,3 V festgelegt. Signalform der Ladungspumpe, Kanal 1 zeigt PP1. Kanal 2 zeigt PP2. Für die Funktion der Ladungspumpe sind zwei um 180° phasenverschobene Taktsignale notwendig. Diese werden durch Timer/Counter 4 des Mikrocontrollers mit einer Frequenz von 250 kHz erzeugt. Der integrierte Totzeitgenerator sorgt für eine kurze Totzeit zwischen der fallenden Flanke von PP2 und der steigenden Flanke von PP1 . Diese Totzeit erlaubt es C11 sich vor der steigenden Flanke an PP1 auf etwa 4,2V aufzuladen, so dass diese Ladung nicht durch C10 aufgebracht werden muss. Dies verbessert den Wirkungsgrad der Ladungspumpe etwas. Tests haben ergeben, dass eine zweite Totzeit nach der fallenden Flanke von PP1 keine Verbesserung der Leistung der Ladungspumpe ergibt. Die Spannung VBrkDwn muss überwacht werden, um die Funktion der Rauschquelle sicherzustellen:

  • Während der Ladephase kann ab 13,3 V zur Zufallsextraktion gewechselt werden.
  • Die Zufallsextraktion muss ab 11 V unterbrochen werden, da ansonsten keine ausreichende Zahl von Zufallsereignissen mehr eintritt.

Für die Überwachung von VBrkDwn wird der umschaltbare Spannungsteiler aus R4, R9 und R12 zusammen mit dem integrierten Komparator und der Spannungsreferenz des ATMega16U4 verwendet. Die integrierte Spannungsreferenz stellt stabile 1,1 V am positiven Eingang des Komparators bereit. Der negative Eingang wird intern mit dem Pin PF7 (ADC7) verbunden, an welchem die durch den Spannungsteiler erzeugte Messspannung VSense anliegt. In der Ladephase ist PF0 des Mikrocontrollers auf Masse gelegt, sodass R4 und R12 parallel geschaltet sind. Für den Widerstand R4 || R12 ergibt sich hierdurch ein Wert von 9,009 kΩ. Bei einer Referenzspannung von 1,1 V kann über die Gleichung für einen unbelasteten Spannungsteiler5 der Umschaltpunkt ermittelt werden:

Spannungsteiler

$$U=U_2 {R_1 + R_2}/{R_2}$$
$$U=1,1\,\V {100\,\k + 9\,\k}/{9\,\k} = 1,1V {109\,\k}/{9\,\k} = 1,1\,\V · 12,1 = 13,32\,\V$$

Der Komparator beendet den Ladevorgang also bei einer Spannung von 13,3 V. Da der verwendete Mikrocontroller mit nur einem Komparator ausgestattet ist, muss dieser von der Überwachung der Durchbruchspannung (VBrkDwn ) und der Rauscherfassung gemeinsam genutzt werden. Dies geschieht, indem zyklisch zwischen den beiden Betriebsmodi “Zufallsextraktion” und “Spannungsüberwachung” gewechselt wird. Während der Erzeugung der Zufallszahlen wird der Komparator für den Extraktionsprozess verwendet. Nach 249 Zufallsereignissen (spätestens nach 2 ms) wird der Komparator wieder auf Spannungsmessung umgeschaltet und die Höhe von VBrkDwn überprüft. Bei dieser Prüfung ist Pin PF0 hochohmig geschaltet, sodass R12 keinen Einfluss auf den Spannungsteiler hat. Die untere Schwelle lässt sich daher folgendermaßen berechnen:

$$U=1,1\,\V {100\,\k + 10\,\k}/{10\,\k} = 1,1V {110\,\k}/{10\,\k} = 1,1\,\V · 11,1 = 12,21\,\V$$

Der untere Schwellenwert liegt bei 12,21 V. In der Realität wird die Spannung meist etwas unterschritten, da die Messung immer am Ende eines Extraktionszyklus erfolgt. Die Schaltschwelle von 12,21 V bietet einen ausreichenden Puffer gegenüber der Minimalspannung von 11 V, um sicherzustellen, dass VBrkDwn während eines Extraktionszyklus die 11-V-Marke nicht unterschreitet. Verlauf V<sub>BrkDwn</sub>
 an C15 Der Oszilloskopscreenshot zeigt, dass die Spannung VBrkDwn durch die beiden Schwellenwerte ausreichend genau innerhalb der berechneten Werte stabilisiert wird.

Rauschquelle und Verstärker

Verlauf der Spannung an der Basis von T1 VBrkDwn liegt an der Basis-Emitter-Diode von T1 an. Wie bereits vorausgehend beschrieben, führt der Durchbruch der BE-Diode dazu, dass der Stromfluss sprunghaft ansteigt. Aufgrund des hohen Vorwiderstandes von 220 kΩ bricht die Spannung sofort zusammen und der Lawinendurchbruch kommt zum Erliegen. Dieser Spannungseinbruch am Punkt RawNoise wird über C14 auf die Basis von T2 eingekoppelt, welcher in Emitterschaltung betrieben wird und das Signal verstärkt. Eine Eigenschaft der Emitterschaltung ist hierbei, dass das Eingangssignal invertiert wird. Jeder Spannungseinbruch am Eingang führt zu einer Spannungsspitze am Ausgang. Die einzelnen Durchbruchsereignisse werden somit in Spannungsspitzen am Punkt Noise der Schaltung umgewandelt. Die Verstärkung des Rauschsignals durch T2 direkt an der Quelle vermeidet, dass Einstreuungen auf dem Weg zum Mikrocontroller das Signal messbar verfälschen können. Außerdem werden durch die Treiberleistung des Verstärkers Rückwirkungen des Tiefpasses (siehe Kapitel 3.3.5) auf die Signalerzeugung ausgeschlossen. Für den Verstärker stellt R8 die Basisvorspannung bereit. Der Emitterwiderstand R15 stabilisiert den Arbeitspunkt, sodass der Transistor im linearen Bereich arbeitet. Die Verstärkerstufe wird durch das R-C-Filter aus R14 und C17 von der analogen Betriebsspannung (VAA) entkoppelt. Die Grenzfrequenz des Filters ist mit 2,34 kHz im Vergleich zu den L-C-Eingangsfiltern nochmals niedriger angesetzt, um ein Übersprechen anderer Schaltungsteile auf den analogen Verstärker auszuschließen. Erst das verstärkte Signal verlässt das Abschirmgehäuse.

Tiefpass und Komparator

Verlauf der Spannung nach der Verstärkung durch T2 Der im Mikrocontroller integrierte Komparator vergleicht das Ausgangssignal am Kollektor von T2 mit dem Referenzpegel, welchen der Tiefpass aus R13 und C12 bereitstellt. Hierdurch wird auch bei abnehmender Spannung VBrkDwn eine sichere Erkennung der einzelnen Impulse gewährleistet. Die Zeitkonstante des R-C-Gliedes ist mit 3,4 ms6 so gewählt, dass die Impulse (Zeitintervall < 1 µs) keinen Einfluss auf den Durchschnittswert haben, die Spannung jedoch dem Verlauf von VBrkDwn (Zeitinervall > 100 ms) folgen kann.

Timing

Während der Zufallsextraktion werden 31 zufällige Bits erzeugt. Für jedes Bit sind 8 Timingmesswerte notwendig. Zusätzlich wird, um Artefakte durch die Initialisierung des Messsystems zu vermeiden, der erste Messwert verworfen. Daher ist für einen Extraktionszyklus ein Puffer für $31 · 8 + 1 = 249$ Timingwerte erforderlich. Aus Informatikersicht wäre ein Extraktionszyklus mit 32 Bit charmanter gewesen, jedoch müsste in diesem Fall der Pufferindex ein 16-Bit-Wert sein7. Da die Messschleife performancekritisch ist und ein 16-Bit-Zähler auf einem 8-Bit-Mikrocontroller erhebliche Performanceeinbußen mit sich bringt, wurde die Anzahl der Messwerte auf weniger als 256 festgelegt. Simulation des Ausgangssignals des Komparators Am Beginn der Zufallsextraktion wird Pin PF6 (ADC6), an welchem der Referenzpegel NoiseRef zur Verfügung steht, mit dem negativen Eingang des Komparators verbunden. Pin PE6 (AIN0), der das Rauschsignal vom Punkt Noise der Schaltung führt, wird auf den positiven Eingang geschaltet. Für den nebenstehenden Oszilloskop-Screenshot wurden die entsprechenden Signale an den Pins des Mikrocontrollers abgenommen. Kanal 1 zeigt das Signal am positiven, Kanal 2 das am negativen Eingang des Komparators. Der Mathematikkanal M 8 zeigt das Ergebnis des Vergleichs zwischen Kanal 1 und Kanal 2. Dies entspricht dem Ausgangssignal des im Mikrocontroller integrierten Komparators. Timer/Counter1 ist derart konfiguriert, dass eine steigende Flanke am Ausgang des Komparators über eine Rauschunterdrückungslogik9 ein Input-Capture-Ereignis auslöst. Die Rauschunterdrückung wertet ausschließlich Signale, bei denen der Signalpegel 4 CPU-Taktzyklen (= 250 ns) stabil war. Dies sorgt dafür, dass nur Durchbrüche erkannt werden, welche das Signal klar über die Schaltschwelle anheben. Kurze Nadelimpulse und Störungen werden unterdrückt. Das Input-Capture-Ereigniss führt dazu, dass der aktuelle Zählerstand in das Register ICR1 kopiert wird.

Zur Vermeidung von Artefakten sind alle Interrupts während der Zufallsextraktion deaktiviert. In einer Schleife prüft der Mikrocontroller die folgenden Bedingungen:

  • Wurde ein Capture-Ereignis ausgelöst? Wenn ja: Kopiere das niederwertige Byte aus dem Register ICR1 in den Puffer.
  • Ist der Puffer voll? Wenn ja: Beende die Zufallsextraktion.
  • Ist der Timer übergelaufen? Wenn ja: Es sind 2ms vergangen und der Puffer war noch nicht voll. Die Rauschquelle erzeugt offensichtlich nicht genug Zufallsereignisse. In diesem Fall wechselt HardRNG in den Fehlermodus und beendet die Erzeugung von Zufallszahlen.

Zu Beginn der Zufallsextraktion wird Timer/Counter1 auf den Wert 32.768 (8000hex ) initialisiert. Da der Timer während der Zufallsextraktion mit der vollen Taktfrequenz der CPU (FCPU ) läuft, tritt ein Überlauf nach etwas mehr als 2 ms ein:

$$Δt = {Cnt_{Max} - Cnt_{Start}}/{F_{CPU}} = {65535 - 32768}/{16\,\M\H\z} ≈ 2048/{1\,\M\H\z} ≈ 2\,\m\s$$

Dieser Trick beschleunigt die Prüfung, ob das Zeitfenster für die Zufallsextraktion bereits verstrichen ist. Anstelle des Vergleichs von zwei 16-Bit-Werten muss in der Extraktionsschleife nur das Überlaufflag des Timers geprüft werden. Zum einen deutet eine zu lange dauernde Zufallsextraktion auf Probleme mit der Rauschquelle hin, zum anderen darf die Verarbeitung von Interrupts nicht zu lange deaktiviert bleiben, da ansonsten die Timingparameter der USB-Schnittstelle verletzt werden. Obwohl es sich bei Timer/Counter1 um einen 16-Bit-Zähler handelt, wird nur das niederwertige Byte aus dem Capture-Register (ICR1) in den Puffer kopiert. Auch dies ist eine Performanceoptimierung. Sie ist möglich, da die Zeitspanne zwischen einzelnen Durchbruchsereignissen in der Regel deutlich unter 16 µs liegt. Für 256 Schritte benötigt Timer/Counter1 genau 16 µs. Da später nur die Differenz zwischen zwei Messwerten weiterverarbeitet wird, lässt sich die Zeitdifferenz auch ohne Kenntnis des höherwertigen Bytes berechnen. Hierfür wird t1 vorzeichenlos10 von t2 subtrahiert. Da der Zähler streng monoton aufwärts zählt, kann t2 nur dann kleiner als t1 sein, wenn es zu einem Übertrag vom niederwertigen Byte zum höherwertigen gekommen ist. Bei der Subtraktion von t2 kommt es dann zu einem Unterlauf11, welcher den vorher aufgetretenen Überlauf kompensiert. Das Ergebnis ist, wie die Tabelle anhand zweier Beispiele zeigt, korrekt, sofern die Bedingung $Δt < 16\,\µ\s$ erfüllt ist. Ist diese Bedingung nicht erfüllt, wird ein falsches Delta berechnet. Details hierzu finden sich im nächsten Kapitel.

ICR1 t1 ICR1 t2 t2 - t1
zum Zeitpunkt t1 niederwertiges Byte von ICR1 zum Zeitpunkt t2 niederwertiges Byte von ICR1 (unter Verwendung zweier vorzeichenloser 8-Bit-Zahlen)
33.312dec 32dec 33.435dec 155dec 123dec
8220hex 20hex 829Bhex 9Bhex 7Bhex
37.242dec 122dec 37.423dec 47dec 181dec
917Ahex 7Ahex 922Fhex 2Fhex B5hex

Die Zeichnung zeigt die einzelnen Input-Capture-Ereignisse als rote Linien. Hierdurch ergeben sich die im Puffer gespeicherten Zeitpunkte t1.1 bis t4.2:

Signal am Punkt Noise der Schaltung sowie der Referenzpegel, welcher durch den Tiefpass erzeugt wird

Umgang mit Überläufen des Timers

Prinzipbedingt wird beim Überlauf des Zählers zur Differenzerfassung (nach 16 µs) ein falscher Differenzwert ermittelt, da die 8 höchstwertigen Bits des Zählers nicht erfasst werden. Ein Überlauf führt aufgrund der fehlenden höherhertigen Bits, immer zu einem zu niedrigen Differenzwert. Die nachfolgende Bitstromerzeugung kombiniert vier Messwerte, um durch Vergleich zu bestimmen, ob das Ausgabebit 0 oder 1 sein soll. Ist einer der Messwerte durch einen Überlauf zu niedrig, wird ein “falsches” Ausgangsbit erzeugt. Ob das Bit jedoch fälschlich 0 oder 1 ist, ist weiterhin zufällig, da dies davon abhängt, welcher der einzelnen Messwerte durch den Überlauf verfälscht wurde. Es kann allerdings nicht ausgeschlossen werden, dass dieses Artefakt zu Abweichungen in der Häufigkeitsverteilung führt. Aus diesem Grund wurde geprüft, ob die Menge der Überläufe noch innerhalb des Fangbereichs des Whitening-Algorithmus liegt.

Histogramm der Zeit bis zum nächsten Event

Die Grafik zeigt das gemessene Histogramm der Zeitspannen zwischen den einzelnen Durchbruchsereignissen als blaue Kurve.

Wenn die Durchbruchsereignisse als zufällig verteilt und unabhängig betrachtet werden, kann die Häufigkeit über eine geometrische Verteilung angenähert werden. Die Verteilung stimmt im linken Bereich nicht mit der erwarteten Häufigkeitsverteilung überein, da R11 zusammen mit der Sperrschichtkapazität von T2 einen Tiefpass bildet, welcher die maximale Frequenz der Durchbruchsereignisse begrenzt. Die Erfolgswahrscheinlichkeit von 0.005 je 10ns interall wurde durch Curve-Fitting ermittelt.

Zeiten, welche in den rote Bereich auf der rechten Seite des Diagramms fallen, führen zu einem Überlauf. Die Wahrscheinlichkeit für einen Überlauf ($P_{over}$) lässt sich somit folgendermaßen ermitteln12:

$$P_{over}=1-(∑↙{n=1}↖1599 {p(1-p)^{n-1}}) ≈ 0,000332$$

Bei dieser Wahrscheinlichkeit tritt alle 3011 Messungen ein Überlauf auf. Da je Ausgangsbit vier Messungen notwendig sind, kommt es also durchschnittlich alle 752 Bits zu einer Verfälschung des Ergebnisses. Wie später noch gezeigt wird, kann der Whitening Algorithmus 870 Abweichungen in 30.000 Bits kompensieren. Der Überlauf des Timers führt maximal zu 40 Abweichungen in 30.000 Bits, liegt also noch weit innerhalb der kompensierbaren Fehlermarge.

Die Berechnungen gehen vom schlechtesten Fall aus, bei welchem alle Überläufe zum gleichen Bitwert führen und dieser das Gegenteil des statistisch erforderlichen Bitwerts ist (heißt, alle 0 Bits werden durch Überläufe zu einer 1). Dies ist so gut wie unmöglich, da die Überläufe zufällig auftreten und somit zufällige Bits invertiert werden. Bei einer Zufallsfolge haben zufällige Bitinversionen keine Auswirkungen auf die Häufigkeitsverteilung. Die Berechnungen zeigen jedoch, dass der Überlauf des Timers auch im schlechtesten Fall keine signifikanten Auswirkungen auf die Häufigkeitsverteilung hat.

Bitstromerzeugung

Im nächsten Schritt werden Gruppen von acht Durchbruchzeitpunkten gebildet. Aus diesen acht Zeitpunkten lässt sich der Zeitabstand von vier unabhängigen Lawinendurchbrüchen bestimmen:
$$Δt_1 = t_{1.2} - t_{1.1}$$
$$Δt_2 = t_{2.2} - t_{2.1}$$
$$Δt_3 = t_{3.2} - t_{3.1}$$
$$Δt_4 = t_{4.2} - t_{4.1}$$

Da die Spannung VBrkDwn langsam abnimmt, ist es möglich, dass die Zeitspanne zwischen einzelnen Durchbruchsereignissen langsam anwächst. Um Artefakte aufgrund dieser Tatsache zu vermeiden, werden die vier Zeitspannen kombiniert:

$$Δt_{14} = Δt_1 + Δt_4$$
$$Δt_{23} = Δt_2 + Δt_3$$

Zwar verhält sich die Spannungskurve an einem entladenen Kondensator gemäß einer e-Funktion, das Sampling für eine Serie von Zufallsereignissen findet jedoch in dem Zeitfenster von 2 ms statt. Für diese kurze Zeit kann der Verlauf der Spannung an C15 und C16 mit ausreichender Genauigkeit durch eine Gerade angenähert werden. Die Abweichung zwischen der e-Funktion und einer einfachen linearen Interpolation zwischen Start- auf die Endspannung beträgt weniger als 8µV. Bei einer Spannung VBrkDwn von mindestens 11,4 V beläuft sich die relative Abweichung auf weniger als 0,7 ppm. Wie die statistische Auswertung zeigt, wirkt sich dieser geringe Versatz nicht nachweisbar auf die Häufigkeit der Durchbruchsereignisse aus.

Nimmt man an, dass die Auswirkungen der Verringerung der Spannung VBrkDwn auf die Zeitintervalle ebenfalls linear sind, muss der langfristige Mittelwert13 aller Zeitintervalle $Δt_1$ bis $Δt_4$ auf einer Geraden liegen. Ist dies der Fall, dann entspricht der Mittelwert von $Δt_1$ und $Δt_4$ dem Mittelwert von $Δt_2$ und $Δt_3$. Auf die Division zur Mittelwertbildung kann, nachdem die Werte im nächsten Verarbeitungsschritt einfach miteinander verglichen werden, verzichtet werden.

Aus Performancegründen werden Zeitintervallgruppen von $Δt_1$ bis $Δt_4$, bei denen einer der Werte 128 übersteigt, verworfen. Für die Verarbeitung wäre ein 16-Bit-Wert für die Addition und den Vergleich notwendig, da das Ergebnis größer als 256 ($2^8$) sein könnte. Da dieser Fall sehr unwahrscheinlich ist (zwei Zufallsereignisse müssten mehr als 8 µs auseinanderliegen) wird die Gruppe einfach verworfen, anstatt das Programm mit diesem Sonderfall zu verkomplizieren und die Performance zu reduzieren.

Anschließend wird im Ausgangsdatenstrom eine 1 geschrieben, wenn $Δt_{14} < Δt_{23}$. Wenn $Δt_{14} > Δt_{23}$ ist wird eine 0 ausgegeben. Sind beide Werte identisch, wird kein Ausgabebit erzeugt. Den Fall $Δt_{14} = Δt_{23}$ zu ignorieren stellt sicher, dass die Wahrscheinlichkeit für $Δt_{14} < Δt_{23}$ und $Δt_{14} > Δt_{23}$ gleich groß ist. Würde der Fall $Δt_{14} = Δt_{23}$ einer der beiden anderen Möglichkeiten zugeordnet, würde sich deren Wahrscheinlichkeit um die Wahrscheinlichkeit von $Δt_{14} = Δt_{23}$ erhöhen. Dies hätte eine Verschiebung in der Verteilung der Ausgabebits zugunsten von 0 oder 1 zur Folge.

Whitening

Um in der Whitening-Stufe eine optimale Verteilung der erzeugen Zufallsbits zu erzielen, müssen die verarbeiteten Bits voneinander unabhängig sein. Da das Whitening auf der Basis von Bytes arbeitet, werden die durch die Bitstromerzeugung generierten Bits zuerst auf einzelne Bytes verteilt. Hierbei wird ein Verfahren angewandt, welches dafür sorgt, dass später keine direkt nacheinander erzeugten Bits miteinander verrechnet werden. Tests haben gezeigt, dass der Generator auch ohne diesen Schritt zuverlässig arbeitet. Jedoch werden durch diese Dekorrelationsstufe Impulsstörungen14 verteilt und wirken sich so weniger auf die erzeugten Zufallszahlen aus. Der Zufallsgenerator wird störresistenter. Die Länge des für die Dekorrelation nötigen Byte-Puffers ergibt sich aus der Formel:

$$n_{Buffer} = n · 8 - 1$$

Hierbei ist n eine beliebige Zahl. Um den Puffer auf dem verwendeten 8-Bit-Mikrocontroller effizient ansprechen zu können, wurde eine Größe von 255 Byte (n = 32) gewählt. Bei dieser Puffergröße kann ein einzelnes Byte als Index genutzt werden, was den Zugriff effizienter gestaltet. Jedem Bit, welches durch die Bitstromerzeugung ausgegeben wird, wird eine Byte-Position im Puffer (iByte ) und eine Bit-Position innerhalb des Bytes (iBit ) zugeordnet. Die beiden Positionen werden aus einer fortlaufenden Bit-Nummer (c) über diese beiden Formeln bestimmt15:

$$n_{Bit} = c\;\mod\;8$$
$$n_{Byte} = c\;\mod\;n_{Buffer} = c\;\mod\;(n · 8 - 1)$$

Da nBuffer kein Vielfaches von 8 ist, haben iBit und iByte unterschiedliche Perioden. Die nachfolgende Grafik verdeutlicht dies anhand eines Beispiels mit dem Wert n=2:

Verteilung der Bits auf den Dekorrelationspuffer

Die Grafik zeigt den Wert von nBit und nByte in Abhängigeit des Wertes des Zählers c. Der Wert c stellt die Position im Bitstrom dar, der vom Zufallsgenerator geliefert wird. Über nBit und nByte werden die Bits auf den Puffer verteilt. Da nBit nByte nicht ganzzahlig teilt, wird beim Überlauf von nByte auf 0 im ersten Byte nicht das gleiche Bit erneut beschrieben. nBit verschiebt sich bei jedem Durchlauf um eine Stelle, so dass immer eine neue Diagonale mit Bits befüllt wird. Dieses Vorgehen stellt sicher, dass der Abstand der Bits im Quelldatenstrom bei allen Bits in aufeinanderfolgenden Bytes mindestens $n · 8$ Byte beträgt. Die Software des HardRNG realisiert die Zuordnung der Bits über einen Bitpuffer, in welchem ein einzelnes 1-Bit rotiert. Ist das Ergebnis der Bitstromerzeugung eine 1, wird dieser Puffer mit der aktuellen Byteposition über eine logische Oder-Operation kombiniert. Diese Methode ist um ein Vielfaches effizienter, als die beiden Positionen zu berechnen und das Bit manuell zu setzen. Der nachfolgende Whiteningalgorihmus verarbeitet aus dem Dekorrelationspuffer immer die Bytepositonen n, n+1 und n+2. HardRNG nutzt einen Puffer von 255 Byte (n=32). Somit ist sichergestellt, dass miteinander kombinierte Bits im Eingabedatenstrom mindestens 256 Bit auseinander liegen. Um eine Entropie nahe 1 zu erreichen, muss in dem durch den Zufallsgenerator erzeugten Datenstrom die Wahrscheinlichkeit für eine 0 ebenso groß sein wie für eine 1. Whiteningalgorithmen gleichen die Wahrscheinlichkeiten für 0 und 1 an den Idealwert von $1/2$ an. Die einfachste und sicherste Form des Whitening ist es, den Datenstrom des Zufallsgenerators mit einer kryptografischen Hashfunktion zu verarbeiten. Ist der gebildete Hashwert hierbei kürzer als die Eingangsdaten, lässt sich mit dieser Methode die Entropie je Bit steigern. Die Nutzung einer Hashfunktion hat jedoch einen entscheidenden Nachteil: Auch ein Eingangsdatenstrom mit geringer Entropie erzeugt sehr zufällige Hashwerte. Dieses Verhalten ist normalerweise gewollt und macht eine gute Hashfunktion aus. In diesem Fall würde es jedoch Unzulänglichkeiten des Generators hinter einem Pseudozufallsgenerator (der Hashfunktion) verstecken. Eine weitere Möglichkeit zum Whitening der Zufallszahlen ist ein Von-Neumann-Whitener. Dieser verarbeitet immer Bit-Paare. Sind die beiden Bits innerhalb eines Paares unterschiedlich, wird der Wert des zweiten Bits zurückgegeben. Sind die Bits gleich, werden sie verworfen. Für diesen Whitener ist bewiesen worden, dass er immer eine gleich verteilte Folge liefert, sofern die Eingangsbits voneinander unabhängig sind. Leider wird die Menge an Bits im besten Fall auf $1/4$ reduziert: Bei einer bereits gleich verteilten Folge, liegt die Wahrscheinlichkeit für jede der vier möglichen Kombinationen von zwei Bits bei jeweils $1/4$. Da nur die beiden Bitkombinationen 01 und 10 zu einem Ergebnis führen, beläuft sich die Wahrscheinlichkeit überhaupt ein Ergebnis zu erhalten auf $1/4 + 1/4 = 1/2$. Da für jedes Ausgangsbit mindestens zwei Eingangsbits notwendig sind, liegt die Ausbeute des Whiteners im Durchschnitt bei ${(1/2)}/{2} = 1/4$. Nachdem die durch die bisherigen Schritte erzeugte Zufallsfolge schon ziemlich gleich verteilt ist, verwendet der HardRNG eine Whiteningmethode, welche die Ausbeute nur auf $1/3$ und nicht auf $1/4$ reduziert und welche trotzdem gut nachvollziehbar ist. Diese Methode lässt sich allerdings nur anwenden, um geringfügige Abweichungen der Wahrscheinlichkeit vom Idealwert zu eliminieren: Werden mehrere unabhängige Zufallswerte mit einer XOR-Operation kombiniert, nähert sich die Wahrscheinlichkeit, dass ein einzelnes Bit 0 oder 1 ist, dem Wert $1/2$ an.

Die Wahrheitstabelle, welche für jedes Eingangsmuster das Ergebnis der Operation darstellt, sieht für eine XOR-Operation wie folgt aus:

$A$ $B$ $A ⊕ B$
0 0 0
0 1 1
1 0 1
1 1 0

Die Wahrscheinlichkeit für eine 0 und die Wahrscheinlichkeit für eine 1 müssen zusammen eins ergeben. Insofern lässt sich die Wahrscheinlichkeit für eine 1 (P1 ) auch als 1 - P0 darstellen. In die Wahrheitstabelle eingetragen, ergeben sich für die vier Ergebnisse der XOR-Operation folgende Wahrscheinlichkeiten:

$A$ $B$ $A ⊕ B$
0 0 $P_{00} = P_0 P_0$
0 1 $P_{01} = P_0 P_1 = P_0 ( 1 - P_0 )$
1 0 $P_{10} = P_1 P_0 = P_0 ( 1 - P_0 )$
1 1 $P_{11} = P_1 P_1 = ( 1 - P_0 ) ( 1 - P_0 )$

Addiert man nun die Wahrscheinlichkeiten für das Ergebnis 0 und das Ergebnis 1, entstehen folgende Gleichungen:

$$X_0 = P_{00} + P_{11} = P_0 P_0 + ( 1 - P_0 ) ( 1 - P_0 ) = ( P_0 ) ^ 2 + ( 1 - P_0 ) ^ 2$$ $$X_1 = P_{01} + P_{10} = P_0 ( 1 - P_0 ) + P_0 ( 1 - P_0 ) = 2 ( 1 - P_0 ) P_0$$

Stellt man die Wahrscheinlichkeit für eine 0 (P0) am Eingang auf der Y-Achse und die Wahrscheinlichkeit für das Ergebnis 0 (X0 ) oder 1 (X1 ) auf der X-Ache einer Zeichnung dar, ergeben sich zwei Parabeln:

Wahrscheinlichkeit von P<sub>0</sub>
 gegenüber X<sub>0</sub>
 und X<sub>1</sub>

Die durch X0 beschriebene Parabel ist nach oben offen, die durch X1 beschriebene nach unten. Wie weit eine Abweichung der Wahrscheinlichkeit P0 von $1/2$ zu einer Abweichung im Ergebnis der XOR-Operation führt, kann mit folgender Formel berechnet werden:

$$ΔX = ∣ X_0 - X_1 ∣ = ∣ ( ( P_0 ) ^ 2 + ( 1 - P_0 ) ^ 2 ) - ( 2 ( 1 - P_0 ) P_0 ) ∣$$

Sie ermittelt den Y-Abstand zwischen den beiden Parabeln. Er repräsentiert die Abweichung vom idealen Wert $1/2$.

Abweichung vom idealen Wert bei zwei/drei kombinierten Werten

Wie die Grafik zeigt, wird der Bereich, in welchem das Ergebnis eine Wahrscheinlichkeit nahe $1/2$ aufweist, durch die XOR-Operation verbreitert. Das Minimum von $ΔX$ liegt bei P0 = $1/2$. Hier ist die Abweichung der beiden Wahrscheinlichkeiten P0 und P1 = 0. Jedoch erlaubt die Parabelform der Wahrscheinlichkeitsverteilungen für X0 und X1 für P0 und P1 auch leichte Abweichungen von $1/2$ ohne das X0 und X1 sich zu weit vom Idealwert entfernen. Ohne genauer auf die Details einzugehen, kann das Ergebnis leicht für das Verknüpfen von drei Eingabeparametern A, B und C erweitert werden. Die Gleichungen für die Wahrscheinlichkeitsverteilung im Ergebnis sehen dann folgendermaßen aus:

$$X_0 = ( P_0 ) ^ 3 + 3 ( 1 - P_0 ) ^ 2 + P_0$$
$$X_1 = ( 1 - P_0 ) ^ 3 + 3 ( 1 - P_0 ) ( P_0 ) ^ 2$$

Die Kurve wird in diesem Fall im Bereich um 0,5 noch flacher. Somit erlaubt das Kombinieren von drei zufälligen Werten per XOR eine größere Abweichung von der Wahrscheinlichkeit ohne das sich die Bitwahrscheinlichkeit im Ergebnis signifikant von $1/2$ entfernt. Für eine vorgegebene Abweichung der Wahrscheinlichkeit von $X_0 = 1/2$ kann nach folgender Formel die obere und untere Grenze für die Abweichung der Ausgabewerte von $1/2$ bestimmt werden:

$$P_0 = [ {1/2} - {√^3{ΔX_0}/2} , {1/2} + {√^3{ΔX_0}/2} ]$$

Wenn alle 10000 erzeugten Bits ein Bit von der idealen Wahrscheinlichkeit von $1/2$ abweichen darf ergibt sich als Zielwert für die Wahrscheinlichkeit einer 0 im Ausgabedatenstrom $0,4999 ≤ X_0 ≤ 0,5001$. Nach der oben angegeben Formel muss die Wahrscheinlichkeit einer 0 daher folgender Bedingung genügen:

$$({1/2} - {√^3{0,5001 - 0,4999}/2}) ≤ P_0 ≤ ({1/2} + {√^3{0,5001 - 0,4999}/2})$$
$$≈ 0,470 ≤ P_0 ≤ 0,529$$

Für den Eingabedatenstrom sind also für 30000 Eingabebits etwas über 870 zusätzliche 0 oder 1 Bits zulässig, ohne dass es bei den 10000 ausgegebenen Bits zu mehr als einem Bit kommt, dessen Wert von dem abweicht, der bei einer Wahrscheinlichkeit von $1/2$ zu erwarten wäre.

HardRNG verwendet diese Methode um die Zufallsverteilung der durch den Zufallsextraktionsprozess erzeugen Bytes zu optimieren. Hierfür werden immer zwei Bytes (A, B und C) miteinander kombiniert. Da der Zufallsextraktor 255 Byte liefert, entstehen je Runde 85 Ausgabebytes.

$$E = A ⊕ B ⊕ C$$

Die 85 Bytes werden über LUFA per USB an den PC geschickt.

Steuerung

Die einzelnen Phasen der Zufallserzeugung werden durch einen endlichen Automaten (state machine) gesteuert.

FSME des HardRNG Generators

Der Automat besitzt fünf Zustände, zwischen denen je nach Betriebszustand der Schaltung gewechselt wird:

  • WaitForUSB ist der initiale Zustand nach dem Anlegen der Versorgungsspannung. Der Mikrocontroller wartet darauf, das der USB-Host die USB-Schnittstelle konfiguriert. Sobald dies geschehen ist, wird überprüft, ob an der virtuellen USB-Schnittstelle die Leitung RTS16 aktiviert ist. Ist dies der Fall, wird über das Ereignis USBReady direkt zum Zustand Charge gewechselt. Ist RTS nicht aktiv, so benötigt der Host aktuell keine Zufallszahlen und es wird das Event HostNotReady ausgelöst, was in den Zustand Stalled verzweigt.
  • Stalled wird betreten, wenn der USB-Host die RTS-Leitung der virtuellen seriellen Schnittstelle deaktiviert hat. Es werden keine Zufallszahlen erzeugt und die Schaltung benötigt wenig Energie. Da auch die Ladungspumpe nicht arbeitet, sinkt VBrkDwn auf ca. 3,8 V ab. Diese Spannung liegt unter der Durchbruchspannung von T1, was diesen als Rauschgenerator schont.
  • Charge ist der Zustand in welchem durch die Ladungspumpe die Spannung VBrkDwn erzeugt wird. C15 und C16 werden geladen. Nach Erreichen der Schlussspannung wird das Ereignis VBrkDwn Ok ausgelöst. Wird der notwendige Ladezustand nicht innerhalb von 120 ms erreicht, sorgt das Ereignis Error dafür, dass das Programm angehalten wird.
  • Generate dient der Erzeugung von Zufallszahlen. Der Zustand wird beibehalten, bis die Spannung VBrkDwn unter den Schwellwert abgesunken ist, bis ein Fehler auftritt oder der Host signalisiert, dass er keine weiteren Zufallszahlen mehr benötigt.
  • Error wird betreten, wenn ein Fehler auftritt. Hierfür wird das Ereignis Error ausgelöst. Dieser Zustand aktiviert die Fehler-LED und tritt dann in eine Endlosschleife ein, in welcher nur noch die USB-Events des Hosts beantwortet werden. Der Zufallsgenerator kann also nur durch das Abziehen vom USB-Port aus einem Fehlerzustand zurückgesetzt werden. Dies soll sicherstellen, dass nach einem Fehler keine Zufallszahlen mit zu geringer Entropie an den Host übergeben werden.

Die Ereignisse USBDisconnected und HostNotReady spielen eine Sonderrolle, da sie von jedem Zustand - außer Error - ausgelöst werden können:

  • HostNotReady verzweigt in den Zustand Stalled, wenn der Host durch Deaktivieren der virtuellen RTS-Leitung anzeigt, dass im Moment keine Zufallszahlen benötigt werden. Dieser Zustand deaktiviert die Ladungspumpe und schont somit den Rauschtransistor. Darüberhinaus sinkt der Energiebedarf der Schaltung.
  • Das Ereignis USBDisconnected tritt auf, wenn die Verbindung mit der USB-Schnittstelle durch den Host getrennt wird. In diesem Fall wird in den Zustand WaitForUSB verzweigt. Es werden nur die LUFA-Routinen zur Behandlung von USB-Ereignissen aufgerufen, bis der Host die Schnittstelle wieder initialisiert hat.

Für den Benutzer wird der Status des Programms über die beiden LEDs D1 und D2 angezeigt. Da beide den gleichen Vorwiderstand (R7) nutzen, kann immer nur eine LED durch den Mikrocontroller angesteuert werden. D1 ist hierbei eine rote LED, D2 eine grüne.

Zustand D1 (rot) D2 (grün)
Generate aus an
Charge aus aus
Stalled aus blinkend
WaitForUSB blinkend aus
Error an aus

Im Normalbetrieb ergibt sich, durch den Wechsel zwischen den Zuständen Generate und Charge, eine leuchtende grüne D2, welche in regelmäßigen Abständen kurzzeitig verlischt. Dies ist vom Blinken im Status Stalled gut zu unterscheiden, da die mit Timer0 realisierte Blinkfrequenz der LEDs bei etwa 3 Hz liegt.

Platinenlayout Hardwarerevisision K

Die Schaltung verwendet eine doppelseitige Platine. Dabei ist die Rückseite überwiegend als Massefläche ausgeprägt um das Einstreuen von Störungen in die Schaltung zu verhindern und an jedem Punkt des Layouts eine niederohmige, kurze Masseverbindung herstellen zu können. Auf der rechten Seite des Layouts ist der Rauschgenerator untergebracht. Dieser Schaltungsteil ist von Kupferflächen umgeben, auf welchen ein Abschirmgehäuse angelötet wird. Es verhindert, dass externe Störungen den Rauschgenerator beeinflussen. Darüber hinaus schirmt es ihn von der 16-MHz-Taktfrequenz des Mikrocontrollers ab.

Foto mit offenen Abschirmgehäuse (Rev. G)

Die Anbindung der USB-Schnittstelle an den Mikrocontroller ist relativ unkritisch, da nur USB 1.1 mit einer Datenrate von 12 Mbit/s verwendet wird. Trotzdem wurde darauf geachtet, die Leiterbahnen parallel zu verlegen, um die Störsicherheit der differenziellen Übertragung zu maximieren. Aufgrund der nur doppelseitigen Platine und der Platzbeschränkungen weicht der Wellenwiderstand des differenziellen Leitungspaares von der USB Spezifikation ab. Hierdurch können theoretisch Reflexionen am Übergang zwischen dem USB-Stecker und der fehlangepassten Leitung auf der Platine entstehen. Der Leitungszug auf der Platine ist jedoch so kurz, dass in der Praxis keine Beeinträchtigung der USB-Kommunikation festgestellt werden konnte. Der Zufallsgenerator kann ausschließlich über den ISP-Steckverbinder17 auf der Platine programmiert werden. Dies stellt sicher, dass die Firmware nicht über den Host-Computer verändert werdenn kann. Die Belegung des Stechverbinders entspricht AVR91018. Aufgrund der Platzbeschränkungen wurde ein Platinensteckverbinder mit einem Rastermaß von 1,27 mm verwendet. Um ein Programmiergerät mit einem Standardstecker im 2,54-mm-Raster verwenden zu können, ist ein Adapter erforderlich. Dieser kann leicht aus einer Stiftleiste im Raster 2,54 mm und einer 1,27-mm-Buchsenleiste hergestellt werden.

ISP Adapter

Wie das Foto zeigt, werden die Pins der Stiftleiste etwas nach innen und die Anschlüsse der Buchsenleiste nach außen gebogen. Anschließend werden die beiden Bauelemente miteinander verlötet. Hierdurch ergibt sich ein haltbarer und kontaktsicherer Adapter, mit dem sich die Firmware auf den Mikrocontroller aufspielen lässt.

Platzierung der Bauteile auf der Platine

Aufgrund der hohen Packungsdichte der Platine enthält der Bestückungsaufdruck keine Bauteilereferenzen. Um die Bestückung trotzdem einfach vornehmen zu können, gibt es eine Bestückungshilfe, welche ausschließlich die Position der Bauteile darstellt.

Testen von Zufallszahlen

Die Ziffernfolge “000000” würde wohl jeder auf den ersten Blick als “nicht zufällig” identifizieren. Jedoch könnte diese Einschätzung auch trügen. Die Wahrscheinlichkeit, dass sechs aufeinanderfolgende Nullen in einer Zufallsfolge vorhanden sind, lieg bei eins zu einer Million. Ist die Zufallsfolge also lang genug, ist es fast sicher, dass sie einen Abschnitt mit sechs Nullen enthält. Im Gegensatz dazu sieht die Ziffernfolge “388914361” zufällig aus. Sie ist jedoch das Ergebnis eines einfachen, linear rückgekoppelten Schieberegisters:

Linear rückgekoppeltes Schieberegister

Die Folge entsteht als Binärwert, wenn 30 Runden mit der Initialisierungssequenz 1010 durchlaufen werden. Sie ist also alles andere als zufällig. Sind einige der Ausgabewerte bekannt, lassen sich alle weiteren leicht rekonstruieren. Diese beiden Beispiele zeigen bereits, dass die Bewertung von Zufallszahlen ein schwieriges Unterfangen ist. Eine mögliche Lösung für dieses Problem ist, davon auszugehen, dass eine Folge dann zufällig ist, wenn sie sich von einer hypothetischen idealen Zufallsfolge nicht unterscheiden lässt. Pseudozufallsgeneratoren lassen sich beispielsweise von „echtem“ Zufall dadurch unterscheiden, dass sie zyklisches Verhalten an den Tag legen. Der interne Zustandsraum des Generators ist begrenzt. Da er komplett deterministisch ist, muss irgendwann wieder der Anfangszustand erreicht werden. Ab diesem Punkt wiederholt sich die Abfolge der Werte am Ausgang. Moderne, kryptografisch sichere, Zufallsgeneratoren haben sehr lange Periodendauern. Somit ist dies in der Praxis nicht mehr durchführbar. Bei einem Hardwarezufallsgenerator ist eine Wiederholung von Werten schon aus Prinzip kein Kriterium, da er keinen inneren Zustand besitzt, welcher eine Wiederholung bedingen könnte 19. Allerdings gibt es andere Kriterien, welche eine Unterscheidung des Generators von einem idealen Zufallsgenerator ermöglichen:

  • Bias
    Die Wahrscheinlichkeit für ihr Auftreten ist nicht für alle Werte gleich.
  • Abhängigkeit
    Die Wahrscheinlichkeit für das Auftreten eines bestimmten Wertes ist von seinen Vorgängern abhängig. Dies führt in der Regel zu Mustern im Datenstrom. Beispielsweise kann die Wahrscheinlichkeit für das Auftreten einer 1 am Anfang eines Samplingintervalls höher sein als am Ende.

Statistische Tests für Zufallszahlen

Es lässt sich also nicht beweisen, dass ein Zufallsgenerator tatsächlich zufällige Werte liefert. Die Statistik kann jedoch helfen, die Güte von Zufallszahlen einzuschätzen. Hierfür wird, ausgehend von einer idealen Zufallsfolge eine Nullhypothese (H0 ) aufgestellt. Die Nullhypothese nimmt an, dass es sich um einen idealen Zufallsgenerator handelt, dessen Ergebnisse statistisch gleich verteilt und voneinander unabhängig sind. Es wird also geprüft, ob die Ausgabewerte zu dieser Annahme passen. Besteht eine statistisch signifikante Abweichung zur Nullhypothese, ist dies ein Indiz, dass die Werte eine der Annahmen verletzen und daher nicht (ausreichend) zufällig sind. Zur Bewertung der Signifikanz einer Abweichung von der Nullhypothese wird in der Statistik der P-Wert herangezogen. Der P-Wert gibt die Wahrscheinlichkeit an, mit welcher die vorliegende Stichprobe oder eine noch extremere, auftreten kann, wenn die Nullhypothese wahr ist. Es muss also eine untere Grenze ($α$) für P definiert werden. In der Regel liegt diese bei 5% ($α = 0,05$). Liegt der P-Wert unter 10% ($α = 0,1$) gilt das Experiment als suspekt und es sollten weitere Daten erhoben werden. Wichtig ist hierbei, dass ein P-Wert größer als $α$ nicht bedeutet, dass die Zahlen tatsächlich zufällig sind. Er bedeutet lediglich, dass die beobachtete Verteilung auch unter der Annahme der Nullhypothese zustande gekommen sein könnte.

Für die statistische Prüfung von Zufallsgeneratoren haben sich zwei gängige Testsuiten etabliert:

Beide Testsätze erlauben eine umfassende, statistische Prüfung der erzeugten Zufallszahlen. Als Eingabedaten für die Testprogramme wurden mehrere Gigabyte Zufallszahlen mit zwei HardRNGs erzeugt. Die verwendete Schaltung ist identisch. Jedoch wurden unterschiedliche Hardwarerevisionen eingesetzt, welche sich in der Anordnung des Quarzes auf der Platine unterscheiden. Der Avalanche-Generator und der in der Firmware eingesetzte Whitening- und Dekorrelationsalgorithmus sind identisch:

Hardwarerevision Firmwareversion Menge Zufallszahlen
Rev. G 2.2 2063192064 Byte
Rev. K 2.2 3198517248 Byte

NIST SP 800-22

Die Testsuite NIST SP 800-22 enthält umfassende Tests für Zufallszahlen. Zur Testsuite gehört neben dem Quelltext des ausführbaren Programms auch ein umfassendes Dokument, welches die einzelnen Tests beschreibt. Das Dokument gibt Hinweise zur korrekten Parametrisierung der Tests und legt empfohlene p-Werte für deren Auswertung fest.

Die Test-Suite empfiehlt eine Menge an Eingabebits (n) zwischen $10^3$ und $10^7$. Für die Tests wurde ein Wert von $10^6 = 1000000$ ausgewählt. Die Menge an Wiederholungen für jeden Test wurde auf 200 gesetzt.

Für die Tests der NIST SP 800-22 Testsuite wurden zwei Parameter abweichend von den Standardwerten konfiguriert:

  • Block Frequency Test
    Die Blocklänge (M) wurde auf 680 festgelegt, da mit jeder Zufallsgenerierung 85 Byte erzeugt werden. Somit hätten auch eventuell vorhandene Artefakte eine Frequenz von 85 Byte oder 680 Bit.

  • Linear Complexity Test
    Für diesen Test wurde die Blocklänge (M), aus dem gleichen Grund wie beim Block Frequency Test, auf 680 festgelegt.

Auswertung der Ergebnisse

Die gesamte Testsuite wurde für Rev. G und Rev. K getrennt ausgeführt. Die Bewertung der Ergebnisse erfolgt nach Kapitel 4 des NIST-Dokuments.

Für alle Tests wurde gemäß der Empfehlung des NIST $α = 0,01$ gewählt. Somit deuten Tests mit einem p-Wert von weniger als 0,01 darauf hin, dass die Folge nicht zufällig ist. Allerdings existiert auch bei einer völlig zufälligen Folge eine gewisse Wahrscheinlichkeit, dass der p-Wert eines Tests kleiner als $α$ wird20. Um dem Rechnung zu Tragen, legt die Testsuite eine Mindestmenge an erfolgreichen Tests fest, die erfüllt sein muss um $H_0$ nicht abzulehnen. Für die gewählte Menge von 200 Wiederholungen liegt dieser Wert (außer beim “random excursion (variant) test” Test) bei 193 von 200 Tests. Für den “random excursion (variant) test” Test liegt der Wert bei 118 von 200 Tests. Solange also nicht weniger als die festgelegte Menge an Tests einen p-Wert von weniger als $α$ haben, sprechen auch einzelne Tests deren p-Wert kleiner als $α$ ist nicht gegen $H_0$.

Alle Tests der Bithäufigkeit wurden für die Rev. G und Rev. K getrennt durchgeführt.

Das NIST empfiehlt, zuerst den “Frequency (Monobit) Test” durchzuführen. Dieser prüft, ob die Wahrscheinlichkeit einer 1 im Zufallsdatenstrom bei $1/2$ liegt. Dieser Test ist die Voraussetzung für alle weiteren Tests. Liegt sein p-Wert bei weniger als 0,01 (1%) muss die Nullhypothese abgelehnt werden. Die Folge ist dann nicht zufällig.

Hardwarerevision # $p ≧ α$/# Tests Ergebnis
Rev. G 196/200 Ok
Rev. K 199/200 Ok

Für beide Generatoren ist in mehr als 193 Fällen $p ≧ α$. Die Bedingung, dass der “Frequency (Monobit) Test” erfolgreich abgeschlossen wird, ist damit erfüllt.

Die Auswertung der Tests erfolgt nun nach den Vorgaben des NIST-Dokuments. Zuerst wird überprüft, ob für jeden Test eine ausreichende Menge der ausgeführten Einzelprüfungen die Bedingung $p ≧ α$ erfüllt:

Test #$p ≧ α$/# Tests
(Rev. G)
#$p ≧ α$/# Tests
(Rev. K)
Ergebnis
(Rev. G & K)
Frequency 196/200 199/200 Ok
BlockFrequency 200/200 198/200 Ok
CumulativeSums 196/200 197/200 Ok
CumulativeSums 195/200 198/200 Ok
Runs 197/200 198/200 Ok
LongestRun 199/200 198/200 Ok
Rank 196/200 198/200 Ok
FFT 197/200 198/200 Ok
NonOverlappingTemplate 199/200 199/200 Ok
NonOverlappingTemplate 200/200 198/200 Ok
NonOverlappingTemplate 200/200 198/200 Ok
NonOverlappingTemplate 200/200 199/200 Ok
NonOverlappingTemplate 199/200 197/200 Ok
NonOverlappingTemplate 200/200 199/200 Ok
NonOverlappingTemplate 200/200 199/200 Ok
NonOverlappingTemplate 197/200 199/200 Ok
NonOverlappingTemplate 197/200 199/200 Ok
NonOverlappingTemplate 200/200 200/200 Ok
NonOverlappingTemplate 199/200 197/200 Ok
NonOverlappingTemplate 200/200 197/200 Ok
NonOverlappingTemplate 200/200 199/200 Ok
NonOverlappingTemplate 199/200 194/200 Ok
NonOverlappingTemplate 196/200 199/200 Ok
NonOverlappingTemplate 198/200 198/200 Ok
NonOverlappingTemplate 195/200 200/200 Ok
NonOverlappingTemplate 195/200 200/200 Ok
NonOverlappingTemplate 198/200 199/200 Ok
NonOverlappingTemplate 196/200 200/200 Ok
NonOverlappingTemplate 198/200 199/200 Ok
NonOverlappingTemplate 198/200 196/200 Ok
NonOverlappingTemplate 197/200 195/200 Ok
NonOverlappingTemplate 199/200 199/200 Ok
NonOverlappingTemplate 197/200 200/200 Ok
NonOverlappingTemplate 195/200 199/200 Ok
NonOverlappingTemplate 200/200 198/200 Ok
NonOverlappingTemplate 200/200 200/200 Ok
NonOverlappingTemplate 195/200 199/200 Ok
NonOverlappingTemplate 194/200 198/200 Ok
NonOverlappingTemplate 199/200 199/200 Ok
NonOverlappingTemplate 198/200 200/200 Ok
NonOverlappingTemplate 197/200 197/200 Ok
NonOverlappingTemplate 199/200 197/200 Ok
NonOverlappingTemplate 199/200 198/200 Ok
NonOverlappingTemplate 199/200 198/200 Ok
NonOverlappingTemplate 195/200 199/200 Ok
NonOverlappingTemplate 196/200 198/200 Ok
NonOverlappingTemplate 200/200 198/200 Ok
NonOverlappingTemplate 198/200 200/200 Ok
NonOverlappingTemplate 198/200 199/200 Ok
NonOverlappingTemplate 199/200 198/200 Ok
NonOverlappingTemplate 197/200 197/200 Ok
NonOverlappingTemplate 197/200 197/200 Ok
NonOverlappingTemplate 197/200 199/200 Ok
NonOverlappingTemplate 198/200 198/200 Ok
NonOverlappingTemplate 196/200 197/200 Ok
NonOverlappingTemplate 199/200 198/200 Ok
NonOverlappingTemplate 198/200 199/200 Ok
NonOverlappingTemplate 200/200 196/200 Ok
NonOverlappingTemplate 195/200 199/200 Ok
NonOverlappingTemplate 197/200 199/200 Ok
NonOverlappingTemplate 197/200 198/200 Ok
NonOverlappingTemplate 198/200 199/200 Ok
NonOverlappingTemplate 199/200 199/200 Ok
NonOverlappingTemplate 198/200 199/200 Ok
NonOverlappingTemplate 199/200 198/200 Ok
NonOverlappingTemplate 197/200 198/200 Ok
NonOverlappingTemplate 198/200 195/200 Ok
NonOverlappingTemplate 198/200 199/200 Ok
NonOverlappingTemplate 199/200 199/200 Ok
NonOverlappingTemplate 198/200 196/200 Ok
NonOverlappingTemplate 199/200 198/200 Ok
NonOverlappingTemplate 200/200 197/200 Ok
NonOverlappingTemplate 200/200 197/200 Ok
NonOverlappingTemplate 198/200 198/200 Ok
NonOverlappingTemplate 195/200 200/200 Ok
NonOverlappingTemplate 199/200 197/200 Ok
NonOverlappingTemplate 200/200 200/200 Ok
NonOverlappingTemplate 198/200 199/200 Ok
NonOverlappingTemplate 198/200 197/200 Ok
NonOverlappingTemplate 198/200 200/200 Ok
NonOverlappingTemplate 200/200 196/200 Ok
NonOverlappingTemplate 196/200 196/200 Ok
NonOverlappingTemplate 199/200 199/200 Ok
NonOverlappingTemplate 196/200 197/200 Ok
NonOverlappingTemplate 200/200 199/200 Ok
NonOverlappingTemplate 197/200 200/200 Ok
NonOverlappingTemplate 195/200 198/200 Ok
NonOverlappingTemplate 199/200 197/200 Ok
NonOverlappingTemplate 199/200 197/200 Ok
NonOverlappingTemplate 198/200 197/200 Ok
NonOverlappingTemplate 197/200 198/200 Ok
NonOverlappingTemplate 198/200 200/200 Ok
NonOverlappingTemplate 197/200 199/200 Ok
NonOverlappingTemplate 198/200 196/200 Ok
NonOverlappingTemplate 196/200 196/200 Ok
NonOverlappingTemplate 199/200 200/200 Ok
NonOverlappingTemplate 194/200 198/200 Ok
NonOverlappingTemplate 198/200 198/200 Ok
NonOverlappingTemplate 200/200 200/200 Ok
NonOverlappingTemplate 199/200 198/200 Ok
NonOverlappingTemplate 198/200 196/200 Ok
NonOverlappingTemplate 198/200 199/200 Ok
NonOverlappingTemplate 200/200 200/200 Ok
NonOverlappingTemplate 199/200 198/200 Ok
NonOverlappingTemplate 197/200 197/200 Ok
NonOverlappingTemplate 199/200 197/200 Ok
NonOverlappingTemplate 199/200 199/200 Ok
NonOverlappingTemplate 199/200 199/200 Ok
NonOverlappingTemplate 200/200 198/200 Ok
NonOverlappingTemplate 197/200 197/200 Ok
NonOverlappingTemplate 200/200 199/200 Ok
NonOverlappingTemplate 197/200 197/200 Ok
NonOverlappingTemplate 197/200 197/200 Ok
NonOverlappingTemplate 200/200 197/200 Ok
NonOverlappingTemplate 198/200 195/200 Ok
NonOverlappingTemplate 195/200 199/200 Ok
NonOverlappingTemplate 198/200 200/200 Ok
NonOverlappingTemplate 196/200 199/200 Ok
NonOverlappingTemplate 197/200 198/200 Ok
NonOverlappingTemplate 198/200 198/200 Ok
NonOverlappingTemplate 197/200 198/200 Ok
NonOverlappingTemplate 194/200 198/200 Ok
NonOverlappingTemplate 200/200 199/200 Ok
NonOverlappingTemplate 197/200 198/200 Ok
NonOverlappingTemplate 198/200 199/200 Ok
NonOverlappingTemplate 199/200 198/200 Ok
NonOverlappingTemplate 197/200 199/200 Ok
NonOverlappingTemplate 199/200 199/200 Ok
NonOverlappingTemplate 199/200 196/200 Ok
NonOverlappingTemplate 196/200 199/200 Ok
NonOverlappingTemplate 199/200 197/200 Ok
NonOverlappingTemplate 200/200 199/200 Ok
NonOverlappingTemplate 196/200 197/200 Ok
NonOverlappingTemplate 198/200 200/200 Ok
NonOverlappingTemplate 196/200 199/200 Ok
NonOverlappingTemplate 200/200 197/200 Ok
NonOverlappingTemplate 197/200 198/200 Ok
NonOverlappingTemplate 200/200 199/200 Ok
NonOverlappingTemplate 199/200 194/200 Ok
NonOverlappingTemplate 199/200 199/200 Ok
NonOverlappingTemplate 195/200 199/200 Ok
NonOverlappingTemplate 198/200 199/200 Ok
NonOverlappingTemplate 200/200 196/200 Ok
NonOverlappingTemplate 194/200 195/200 Ok
NonOverlappingTemplate 197/200 199/200 Ok
NonOverlappingTemplate 199/200 200/200 Ok
NonOverlappingTemplate 198/200 199/200 Ok
NonOverlappingTemplate 197/200 196/200 Ok
NonOverlappingTemplate 197/200 199/200 Ok
NonOverlappingTemplate 198/200 199/200 Ok
NonOverlappingTemplate 198/200 198/200 Ok
NonOverlappingTemplate 200/200 199/200 Ok
NonOverlappingTemplate 199/200 197/200 Ok
NonOverlappingTemplate 198/200 197/200 Ok
NonOverlappingTemplate 198/200 199/200 Ok
NonOverlappingTemplate 196/200 196/200 Ok
OverlappingTemplate 198/200 195/200 Ok
Universal 195/200 196/200 Ok
ApproximateEntropy 198/200 199/200 Ok
RandomExcursions 115/115 122/123 Ok
RandomExcursions 114/115 121/123 Ok
RandomExcursions 113/115 121/123 Ok
RandomExcursions 114/115 121/123 Ok
RandomExcursions 115/115 121/123 Ok
RandomExcursions 113/115 119/123 Ok
RandomExcursions 114/115 122/123 Ok
RandomExcursions 115/115 122/123 Ok
RandomExcursionsVariant 112/115 123/123 Ok
RandomExcursionsVariant 113/115 123/123 Ok
RandomExcursionsVariant 113/115 123/123 Ok
RandomExcursionsVariant 113/115 123/123 Ok
RandomExcursionsVariant 113/115 123/123 Ok
RandomExcursionsVariant 114/115 121/123 Ok
RandomExcursionsVariant 114/115 122/123 Ok
RandomExcursionsVariant 113/115 120/123 Ok
RandomExcursionsVariant 114/115 121/123 Ok
RandomExcursionsVariant 115/115 121/123 Ok
RandomExcursionsVariant 115/115 122/123 Ok
RandomExcursionsVariant 115/115 121/123 Ok
RandomExcursionsVariant 115/115 122/123 Ok
RandomExcursionsVariant 115/115 122/123 Ok
RandomExcursionsVariant 115/115 120/123 Ok
RandomExcursionsVariant 115/115 120/123 Ok
RandomExcursionsVariant 115/115 122/123 Ok
RandomExcursionsVariant 115/115 121/123 Ok
Serial 199/200 196/200 Ok
Serial 200/200 198/200 Ok
LinearComplexity 199/200 197/200 Ok

Als zweiter Test wird überprüft, ob die p-Werte der durchgeführten Tests gleichverteilt sind. Hierfür wird die Menge der p-Werte aller Iterationen jedes Tests in 10 Gruppen unterteilt. Das Histogramm der p-Werte wird anschließend mit Hilfe eines $χ^2$-Tests mit der erwarteten Gleichverteilung verglichen. Die p-Werte sind dann gleichverteilt, wenn der p-Wert des $χ^2$-Tests ($p_T$) $≧ 0.0001$ ist.

Test $pT$
(Rev. G)
$pT$
(Rev. K)
Ergebnis
(Rev. G & K)
Frequency 0,158133 0,941144 Ok
BlockFrequency 0,616305 0,268917 Ok
CumulativeSums 0,162606 0,122325 Ok
CumulativeSums 0,060875 0,946308 Ok
Runs 0,842937 0,224821 Ok
LongestRun 0,282626 0,375313 Ok
Rank 0,484646 0,017305 Ok
FFT 0,437274 0,375313 Ok
NonOverlappingTemplate 0,342451 0,428095 Ok
NonOverlappingTemplate 0,544254 0,585209 Ok
NonOverlappingTemplate 0,075719 0,699313 Ok
NonOverlappingTemplate 0,311542 0,437274 Ok
NonOverlappingTemplate 0,779188 0,574903 Ok
NonOverlappingTemplate 0,585209 0,749884 Ok
NonOverlappingTemplate 0,807412 0,282626 Ok
NonOverlappingTemplate 0,383827 0,689019 Ok
NonOverlappingTemplate 0,326749 0,788728 Ok
NonOverlappingTemplate 0,075719 0,657933 Ok
NonOverlappingTemplate 0,668321 0,964295 Ok
NonOverlappingTemplate 0,392456 0,983453 Ok
NonOverlappingTemplate 0,465415 0,213309 Ok
NonOverlappingTemplate 0,709558 0,951205 Ok
NonOverlappingTemplate 0,626709 0,437274 Ok
NonOverlappingTemplate 0,383827 0,383827 Ok
NonOverlappingTemplate 0,729870 0,428095 Ok
NonOverlappingTemplate 0,595549 0,093720 Ok
NonOverlappingTemplate 0,875539 0,145326 Ok
NonOverlappingTemplate 0,080519 0,083018 Ok
NonOverlappingTemplate 0,176657 0,983453 Ok
NonOverlappingTemplate 0,564639 0,437274 Ok
NonOverlappingTemplate 0,158133 0,176657 Ok
NonOverlappingTemplate 0,465415 0,118812 Ok
NonOverlappingTemplate 0,554420 0,998376 Ok
NonOverlappingTemplate 0,955835 0,191687 Ok
NonOverlappingTemplate 0,564639 0,129620 Ok
NonOverlappingTemplate 0,859637 0,524101 Ok
NonOverlappingTemplate 0,494392 0,176657 Ok
NonOverlappingTemplate 0,410055 0,779188 Ok
NonOverlappingTemplate 0,564639 0,904708 Ok
NonOverlappingTemplate 0,484646 0,637119 Ok
NonOverlappingTemplate 0,249284 0,282626 Ok
NonOverlappingTemplate 0,219006 0,616305 Ok
NonOverlappingTemplate 0,616305 0,494392 Ok
NonOverlappingTemplate 0,867692 0,616305 Ok
NonOverlappingTemplate 0,859637 0,311542 Ok
NonOverlappingTemplate 0,930026 0,657933 Ok
NonOverlappingTemplate 0,564639 0,605916 Ok
NonOverlappingTemplate 0,202268 0,637119 Ok
NonOverlappingTemplate 0,867692 0,834308 Ok
NonOverlappingTemplate 0,816537 0,050305 Ok
NonOverlappingTemplate 0,719747 0,689019 Ok
NonOverlappingTemplate 0,911413 0,514124 Ok
NonOverlappingTemplate 0,105618 0,935716 Ok
NonOverlappingTemplate 0,268917 0,186566 Ok
NonOverlappingTemplate 0,544254 0,275709 Ok
NonOverlappingTemplate 0,068999 0,044220 Ok
NonOverlappingTemplate 0,319084 0,788728 Ok
NonOverlappingTemplate 0,834308 0,935716 Ok
NonOverlappingTemplate 0,358641 0,637119 Ok
NonOverlappingTemplate 0,437274 0,668321 Ok
NonOverlappingTemplate 0,955835 0,455937 Ok
NonOverlappingTemplate 0,129620 0,875539 Ok
NonOverlappingTemplate 0,410055 0,224821 Ok
NonOverlappingTemplate 0,729870 0,044220 Ok
NonOverlappingTemplate 0,678686 0,141256 Ok
NonOverlappingTemplate 0,657933 0,167184 Ok
NonOverlappingTemplate 0,334538 0,392456 Ok
NonOverlappingTemplate 0,657933 0,350485 Ok
NonOverlappingTemplate 0,504219 0,883171 Ok
NonOverlappingTemplate 0,544254 0,392456 Ok
NonOverlappingTemplate 0,883171 0,428095 Ok
NonOverlappingTemplate 0,392456 0,125927 Ok
NonOverlappingTemplate 0,446556 0,980883 Ok
NonOverlappingTemplate 0,514124 0,474986 Ok
NonOverlappingTemplate 0,904708 0,678686 Ok
NonOverlappingTemplate 0,574903 0,564639 Ok
NonOverlappingTemplate 0,585209 0,319084 Ok
NonOverlappingTemplate 0,410055 0,739918 Ok
NonOverlappingTemplate 0,524101 0,554420 Ok
NonOverlappingTemplate 0,176657 0,249284 Ok
NonOverlappingTemplate 0,911413 0,401199 Ok
NonOverlappingTemplate 0,678686 0,428095 Ok
NonOverlappingTemplate 0,342451 0,437274 Ok
NonOverlappingTemplate 0,616305 0,020548 Ok
NonOverlappingTemplate 0,875539 0,191687 Ok
NonOverlappingTemplate 0,465415 0,289667 Ok
NonOverlappingTemplate 0,514124 0,029796 Ok
NonOverlappingTemplate 0,647530 0,474986 Ok
NonOverlappingTemplate 0,350485 0,392456 Ok
NonOverlappingTemplate 0,112047 0,769527 Ok
NonOverlappingTemplate 0,219006 0,296834 Ok
NonOverlappingTemplate 0,779188 0,392456 Ok
NonOverlappingTemplate 0,296834 0,073417 Ok
NonOverlappingTemplate 0,890582 0,023545 Ok
NonOverlappingTemplate 0,524101 0,262249 Ok
NonOverlappingTemplate 0,350485 0,647530 Ok
NonOverlappingTemplate 0,699313 0,534146 Ok
NonOverlappingTemplate 0,102526 0,807412 Ok
NonOverlappingTemplate 0,002043 0,311542 Ok
NonOverlappingTemplate 0,657933 0,867692 Ok
NonOverlappingTemplate 0,236810 0,851383 Ok
NonOverlappingTemplate 0,410055 0,605916 Ok
NonOverlappingTemplate 0,668321 0,911413 Ok
NonOverlappingTemplate 0,637119 0,085587 Ok
NonOverlappingTemplate 0,626709 0,834308 Ok
NonOverlappingTemplate 0,383827 0,419021 Ok
NonOverlappingTemplate 0,249284 0,296834 Ok
NonOverlappingTemplate 0,392456 0,709558 Ok
NonOverlappingTemplate 0,282626 0,524101 Ok
NonOverlappingTemplate 0,078086 0,176657 Ok
NonOverlappingTemplate 0,358641 0,122325 Ok
NonOverlappingTemplate 0,437274 0,647530 Ok
NonOverlappingTemplate 0,392456 0,911413 Ok
NonOverlappingTemplate 0,455937 0,141256 Ok
NonOverlappingTemplate 0,779188 0,975012 Ok
NonOverlappingTemplate 0,064822 0,484646 Ok
NonOverlappingTemplate 0,455937 0,514124 Ok
NonOverlappingTemplate 0,834308 0,564639 Ok
NonOverlappingTemplate 0,719747 0,366918 Ok
NonOverlappingTemplate 0,437274 0,108791 Ok
NonOverlappingTemplate 0,514124 0,090936 Ok
NonOverlappingTemplate 0,709558 0,075719 Ok
NonOverlappingTemplate 0,230755 0,392456 Ok
NonOverlappingTemplate 0,564639 0,311542 Ok
NonOverlappingTemplate 0,955835 0,062821 Ok
NonOverlappingTemplate 0,668321 0,249284 Ok
NonOverlappingTemplate 0,678686 0,534146 Ok
NonOverlappingTemplate 0,207730 0,605916 Ok
NonOverlappingTemplate 0,930026 0,975012 Ok
NonOverlappingTemplate 0,825505 0,897763 Ok
NonOverlappingTemplate 0,911413 0,842937 Ok
NonOverlappingTemplate 0,595549 0,935716 Ok
NonOverlappingTemplate 0,181557 0,504219 Ok
NonOverlappingTemplate 0,268917 0,779188 Ok
NonOverlappingTemplate 0,040108 0,946308 Ok
NonOverlappingTemplate 0,118812 0,224821 Ok
NonOverlappingTemplate 0,122325 0,709558 Ok
NonOverlappingTemplate 0,975012 0,401199 Ok
NonOverlappingTemplate 0,554420 0,428095 Ok
NonOverlappingTemplate 0,668321 0,311542 Ok
NonOverlappingTemplate 0,275709 0,585209 Ok
NonOverlappingTemplate 0,678686 0,474986 Ok
NonOverlappingTemplate 0,875539 0,554420 Ok
NonOverlappingTemplate 0,149495 0,078086 Ok
NonOverlappingTemplate 0,455937 0,544254 Ok
NonOverlappingTemplate 0,605916 0,304126 Ok
NonOverlappingTemplate 0,605916 0,788728 Ok
NonOverlappingTemplate 0,383827 0,504219 Ok
NonOverlappingTemplate 0,236810 0,326749 Ok
NonOverlappingTemplate 0,053627 0,647530 Ok
NonOverlappingTemplate 0,446556 0,729870 Ok
NonOverlappingTemplate 0,042808 0,807412 Ok
NonOverlappingTemplate 0,544254 0,544254 Ok
NonOverlappingTemplate 0,699313 0,342451 Ok
NonOverlappingTemplate 0,834308 0,358641 Ok
NonOverlappingTemplate 0,657933 0,358641 Ok
OverlappingTemplate 0,358641 0,930026 Ok
Universal 0,446556 0,616305 Ok
ApproximateEntropy 0,971699 0,719747 Ok
RandomExcursions 0,656043 0,119392 Ok
RandomExcursions 0,938710 0,593823 Ok
RandomExcursions 0,314955 0,881915 Ok
RandomExcursions 0,357895 0,593823 Ok
RandomExcursions 0,251604 0,014635 Ok
RandomExcursions 0,818179 0,542566 Ok
RandomExcursions 0,525011 0,780786 Ok
RandomExcursions 0,905328 0,445002 Ok
RandomExcursionsVariant 0,879035 0,476590 Ok
RandomExcursionsVariant 0,072800 0,108256 Ok
RandomExcursionsVariant 0,328861 0,182384 Ok
RandomExcursionsVariant 0,171007 0,093251 Ok
RandomExcursionsVariant 0,892563 0,559523 Ok
RandomExcursionsVariant 0,506913 0,330628 Ok
RandomExcursionsVariant 0,036243 0,663130 Ok
RandomExcursionsVariant 0,188880 0,281464 Ok
RandomExcursionsVariant 0,849861 0,611108 Ok
RandomExcursionsVariant 0,849861 0,218048 Ok
RandomExcursionsVariant 0,171007 0,811993 Ok
RandomExcursionsVariant 0,065007 0,072289 Ok
RandomExcursionsVariant 0,229125 0,960899 Ok
RandomExcursionsVariant 0,489065 0,144641 Ok
RandomExcursionsVariant 0,090936 0,764655 Ok
RandomExcursionsVariant 0,188880 0,270040 Ok
RandomExcursionsVariant 0,086061 0,731550 Ok
RandomExcursionsVariant 0,162606 0,293235 Ok
Serial 0,564639 0,125927 Ok
Serial 0,524101 0,035174 Ok
LinearComplexity 0,484646 0,605916 Ok

Die Tests der NIST 800-22 Testsuite zeigen keine Auffälligkeiten die eine Ablehnung von $H_0$ erforderlich machen.

Dieharder

Die Testsuite Dieharder21 gehört zu den anerkannten Tests für Zufallsgeneratoren. Der einzige Nachteil ist, dass sie Unmengen an Zufallszahlen benötigt und dass der HardRNG verglichen mit einem Software-Pseudozufallsgenerator ziemlich langsam ist. Der HardRNG wurde 140 Tage lang an einem Raspberry-PI betrieben um die notwendige Menge an Zufallszahlen zu erzeugen. Ergebnis war eine 11,6 GiByte große Datei und folgendes Testergebnis:

Tests p-Wert Ergebnis
diehard_birthdays 0,68060996 Ok
diehard_operm5 0,96288413 Ok22
diehard_rank_32x32 0,72396526 Ok
diehard_rank_6x8 0,72737480 Ok
diehard_bitstream 0,74238785 Ok
diehard_opso 0,84058352 Ok
diehard_oqso 0,91553991 Ok
diehard_dna 0,21516088 Ok
diehard_count_1s_str 0,51753616 Ok
diehard_count_1s_byt 0,07538205 Ok
diehard_parking_lot 0,65655550 Ok
diehard_2dsphere 0,76442050 Ok
diehard_3dsphere 0,10045300 Ok
diehard_squeeze 0,00586033 Ok
diehard_sums 0,00000061 Abweichung23
diehard_runs 0,53138878 Ok
diehard_runs 0,56967863 Ok
diehard_craps 0,86443880 Ok
diehard_craps 0,90656575 Ok

Keiner der Tests zeigt Auffälligkeiten. Die p-Werte der einzelnen Tests sowie die Verteilung der p-Werte von jeweils mindestens 100 Tests zeigten für die durch Dieharder durchgeführten Tests keine Auffälligkeiten.

Ausgabe DieHarder auf 11,6 GiByte Zufallsdaten der Rev. K

ENT

Das Testprogramm ENT von John Walker ist ein weiteres Programm, welches statistische Tests für Zufallsgeneratoren durchführt. Auch bei diesen Tests wird untersucht, ob deren Ergebnis unter Verwendung der erzeugten Zufallswerte von den erwarteten Ergebnissen bei Verwendung idealer Zufallszahlen statistisch signifikant abweicht.

Die Referenzen zu den durchgeführten Tests inkl. der Quellanangaben sind auf der Webseite von ENT zu finden.

Entropie

Dieser Test ermittelt die Entropie des Datenstromes. Der ermittelte Wert von 8,000000 entspricht dem Erwartungswert bei einer idealen Zufallsfolge.

Chi-Quadrat-Test

Der Chi-Quadrat-Test berechnet die Chi-Quadrat-Verteilung des Datenstroms. Es wird ein absoluter Wert ermittelt und prozentual angegeben, wie oft eine perfekte Zufallsfolge diesen Wert überschreitet. Idealerweise liegt der Prozentwert bei exakt 50%. Gemäß der Dokumentation von ENT sind Werte zwischen 10% und 90% unkritisch.

Hardwarerevision Chi-Quadrat-Wert Häufigkeit der Abweichung Ergebnis
Rev. G 276,13 17,35% Ok
Rev. K 256,95 45,40% Ok

Arithmetischer Mittelwert

Der Mittelwert der gesamten Folge sollte 127,5 betragen.

Hardwarerevision Mittelwert
Rev. G 127.5004
Rev. K 127.5008

Monte Carlo Wert für PI

Dieser Test liest die Zufallswerte als 24 Bit X und Y Koordinaten von Punkten innerhalb eines Quadrates. Für jeden Punkt wird geprüft, ob dieser innerhalb eines Kreises liegt. Aufgrund der Punkte innerhalb und außerhalb des Kreises lässt sich der Wert von $π$ annähern. Wenn die Werte der Folge zufällig sind, nähert sich der Wert immer mehr dem idealen Wert von $π$ an.

Hardwarerevision $π$ Abweichung
Rev. G 3.141604337 0,00 %
Rev. K 3,141504730 0,00 %

Serielle Korrelation

Dieser Test prüft, in wie weit die einzelnen Bytes der Folge voneinander abhängen. Je näher der Wert an 0 liegt, desto weniger ist jedes Byte von seinem Vorgänger abhängig und desto zufälliger ist die Folge.

Hardwarerevision Koeffizient
Rev. G -0.000016
Rev. K 0.000000

Performance

Der Zufallsgenerator erzeugt etwa 1590 Byte pro Sekunde. Die exakte Datenrate hängt von der Menge der durch T1 erzeugten Zufallsereignisse ab, kann also bei unterschiedlichen HardRNG etwas schwanken.

Einsatz des Zufallsgenerators

Ungeachtet der Ergebnisse der statistischen Tests sollten weder dieser, noch ein anderer Zufallsgenerator als alleinige Zufallsquelle für sicherheitskritische Anwendungen verwendet werden. Um die Sicherheit auch dann zu gewährleisten, wenn einer der genutzten Generatoren Schwächen zeigt, lässt sich ihr Output per XOR kombinieren.

Integration in Linux

Um den HardRNG Zufallsgenerator in Linux nutzen zu können, muss für diesen ein hwrng-Device bereitgestellt werden. Dies geht am einfachsten mit einer udev-Regel, welche für die virtuelle serielle Schnittstelle des HardRNG einen Symlink mit dem Namen hwrng anlegt. Außerdem lässt sich über diese Regel auch gleich die Konfiguration der seriellen Schnittstelle erledigen:

SUBSYSTEM=="tty", SUBSYSTEMS=="usb", ATTRS{manufacturer}=="Flash Systems", ATTRS{product}=="HardRNG - Hardware random number generator", SYMLINK+="hwrng", OWNER="root", GROUP="root", MODE="0600" RUN+="/bin/stty -F /dev/hwrng raw"

Der Abschnitt /bin/stty -F /dev/hwrng raw schaltet die virtuelle serielle Schnittstelle in den RAW-Modus. Hierdurch werden keine Steuerzeichen (XON/XOFF, etc.) mehr interpretiert. Da der Datenstrom von HardRNG zufällig ist, besteht sonst das Risiko, dass eines der auftretenden Zeichen zufällig als Steuerzeichenfolge interpretiert wird.

Jetzt müssen die Zufallszahlen nur noch in den Entropiepool von Linux übernommen werden. Hierfür gibt es das Programm rngd aus der Sammlung rng-tools. Dieser Dienst übernimmt Entropie aus dem HardRNG in den Entropiepool des Kernels. Er unterzieht die Zufallszahlen den in FIPS 140-2 festgelegten Tests. Hierdurch werden grobe Fehler bzw. Defekte bei der Zufallserzeugung erkannt und es wird vermieden, dass diese die Entropie der durch den Kernel bereitgestellten Zufallszahlen verschlechtern.

Normalerweise fügt rngd nur so lange Zufall zum Entropiepool des Kernels hinzu, bis dessen Füllstand 50% beträgt. Hierdurch wird vermieden, dass die externe Zufallsquelle den Inhalt des Entropiepools des Kernels dominiert. Aus Sicherheitsgründen sollte dieser Wert nicht über 50% angehoben werden. Bei meinen Tests war der Wert von 50% ausreichend um die Erzeugung von SSL-Zertifikaten und anderen Schlüsseln auf dem System deutlich zu beschleunigen.

Entropie im Entropie-Pool von Linux

Die Grafik zeigt den Wert von /proc/sys/kernel/random/entropy_avail des Linux-Kernels im Abstand von zwei Sekunden. Die Grafik wurde unter Debian 9 aufgezeichnet. Das System besitzt keine eigne Hardware-Entropiequelle. Wie die rote Linie zeigt, baut sich die Entropie im Pool deutlich langsamer auf sobald sie verbraucht wurde. Die Stufen der roten Linie rühren von dem Standardwert von 64 für /proc/sys/kernel/random/read_wakeup_threshold. Sobald dieser Wert erreicht wird erlaubt das System das Lesen aus /dev/random. Es ist gut zu erkennen, wie die Entropie sofort durch die wartenden Prozesse aufgebraucht wird. Die blaue Kurve des HardRNG unterstützten Systems erreicht dagegen deutlich höhere Werte und erholt sich auch schneller. Dies zeigt deutlich, dass dem System deutlich mehr Entropie zur Verfügung stand.

Integration in KVM

Gerade wenn viele VMs auf einem Hostsystem Zufallszahlen benötigen, kann den Gastsystemen schon mal die Entropie ausgehen. Um das zu vermeiden kann sich der Gast bei KVM an der Entropie des Hostsystems bedienen. Um das zu erlauben ist das paravirtualisierte Gerät virtio-rng nötig. Details sind im QEMU-Wiki oder bei Google zu finden.


  1. Quelle: Inside Intel (ISBN 3-455-11204-8) [return]
  2. HSM: Hardware Security Module: Appliances oder Steckkarten, welche eine sichere Umgebung für die Erzeugung und Handhabung kryptografischer Schlüssel bereitstellen. Diese enthalten - ebenso wie Smartcards - einen kryptografisch sicheren Zufallsgenerator. [return]
  3. Dies ist zumindest bei der klassischen Silizium- und Germaniumdiode der Fall. Es existieren auch andere Formen, welche beispielsweise einen Metall-Halbleiter-Übergang (Schottky-Diode) verwenden. [return]
  4. Laut Datenblatt ist die maximal zulässige Emitter-Basis-Spannung 6 V. [return]
  5. Bei einem Leckstrom von 50 nA am Eingang des Komparators kann man durchaus von einem unbelasteten Spannungsteiler sprechen. Der Stromfluss im Spannungsteiler liegt mit ca. 100 µA um den Faktor 2000 höher. [return]
  6. Bis zu einer Ladung von mehr als 99 %. Dies entspricht 5τ. [return]
  7. $32 · 8 + 1 = 257$. 257 ist größer als $2^8$. Die nächste Stufe wäre die Nutzung von 2 Byte mit einem Wertebereich von $2^{16}$. [return]
  8. Nein, das ist kein neuer Spartenkanal neben Arte. Die meisten digitalen Oszilloskope bieten die Möglichkeit, das Ergebnis einer mathematischen Operation als zusätzliches Signal anzuzeigen. Dieses Signal wird häufig auf meinem “M” oder “Math” genannten, gesonderten Kanal dargestellt. [return]
  9. Denoise hat hier nichts mit dem erwünschten Rauschen aus der Rauschquelle zu tun. Die Denoise Funktion des Mikrocontrollers sorgt dafür, dass kurzzeitige Überschreitungen der Schaltschwelle (sog. Glitches) nicht sofort zu einem Event führen. Die Zeitspanne für diese Filterung ist mit 240 ns kleiner als die Zeitspanne der Ereignisse auf die reagiert werden (> 300 ns) soll. Theoretisch könnte die Leistung des HardRNG durch das Entfernen der Rauschunterdrückung etwas gesteigert werden, da auch kürzere Ereignisse erfasst werden können. Da die 4 Taktzyklen der Rauschunterdrückung jedoch noch innerhalb der minimalen Durchlaufzeit der Auswerteschleife liegen wäre der, auf Kosten der Störfestigkeit erzielte, Gewinn gering. [return]
  10. Unsigned arithmetic: Alle Werte werden als Variablen ohne Vorzeichen dargestellt. Unter- oder Überläufe werden ignoriert. [return]
  11. negativer Überlauf [return]
  12. Die Wahrscheinlichkeit für einen Wert, der einen Überlauf verursacht ist Eins, minus die Summe der Wahrscheinlichkeiten aller 1599 10ns-Intervalle (0,01µs bis 15,99µs) die keinen Überlauf verursachen. [return]
  13. Der langfristige Mittelwert ist notwendig um die gewünschte Zufälligkeit der Werte heraus zu filtern. Das Ausgangssignal des Tiefpass-Filters folgt dem langfristigen Mittelwert und legt damit den Referenzpegel automatisch fest. Hierdurch wird der langsamen Abnahme von VBrkDwn während der Zufallserzeugung Rechnung getragen. [return]
  14. Impulsstörungen sind Störungen, welche einige wenige aufeinanderfolgende Bits betreffen und diese vorhersagbar machen (z. B. in dem diese fest auf 0 oder 1 gelegt werden). [return]
  15. Alle Indizes sind hierbei nullbasiert. [return]
  16. RTS: Request to send [return]
  17. ISP: In System Programming: Erlaubt das Programmieren des Mikrocontrollers innerhalb der Schaltung. Er muss nicht entfernt und in ein gesondertes Programmiergerät gesteckt werden. [return]
  18. http://www.atmel.com/Images/doc0943.pdf [return]
  19. Natürlich kann es eine Wiederholung von Werten, aufgrund von Problemen bei der Zufallserzeugung geben. Diese sind dann jedoch ein Artefakt der Erzeugung der Zufallszahlen und nicht - wie beim Pseudozufallsgenerator - systemimmanent. [return]
  20. Der p-Wert gibt an, wo innerhalb der Normalverteilung sich das Ergebnis befindet, dass heißt die Wahrscheinlichkeit das eine perfekte Zufallsfolge einen p-Wert kleiner $α$ hat, ist nicht 0. Daher spricht eine begrenzte Menge von Tests, bei denen $p < α$ nicht gegen $H_0$. [return]
  21. …jetzt erst Recht. [return]
  22. Die Homepage von Dieharder listet diesen Test als “suspekt”. Auch wenn das Ergebnis Ok ist, sollte man diesem Test nicht unbedingt viel Beachtung schenken. [return]
  23. Diese Abweichung ist kein Fehler des HardRNG sondern ein Artefakt des diehard_sums-Tests. Die Dokumentation zu Dieharder schreibt hierzu: “At this point I think there is rock solid evidence that this test is completely useless in every sense of the word. It is broken, and it is so broken that there is no point in trying to fix it. The problem is that the transformation above is not linear, and doesn’t work. Don’t use it.” [return]