Hardware gegen Software-RNGs

Das erste, was Sie erwähnen, ist eine Hardware-Rauschquelle. Eine hochpräzise Messung eines metastabilen Phänomens reicht aus, um unvorhersehbare Daten zu generieren. Dies kann mit einer in Sperrrichtung vorgespannten Zenerdiode, mit Ringoszillatoren, mit einem ADC oder sogar mit einem Geigerzähler erfolgen. Es kann sogar meine Messung von Verzögerungen im Nanosekundenbereich zwischen den Tastenanschlägen durchgeführt werden. Diese Rauschquellen können ausfallen, wenn die Hardware selbst ausfällt. Zum Beispiel kann ein Transistor ausfallen, wenn er nicht speziell für den Rückwärtsbetrieb bei hohen Spannungen ausgelegt ist. Obwohl diese Techniken ein unterschiedliches Maß an Fragilität aufweisen, wird dies in dem von Ihnen zitierten Text nicht behandelt.

Der zweite von Ihnen erwähnte RNG-Typ ist ein Software-RNG, der als Pseudozufallszahlengenerator (PRNG ^{) bezeichnet wird * sup>). Dies ist ein Algorithmus, der einen Startwert , der einem Verschlüsselungsschlüssel ähnelt, zu einem endlosen Datenstrom erweitert. Es wird versucht sicherzustellen, dass die Daten nicht vorhergesagt oder abgesehen von reiner Zufälligkeit erzählt werden können, ohne den geheimen zufälligen Startwert zu kennen, mit dem der Algorithmus begonnen hat. In diesem Fall ist das PRNG in reiner Software implementiert, sodass nur ein Fehler in den Code eingeführt werden muss, um den es in dem von Ihnen zitierten Text geht. Es ist lediglich Code, der zerbrechlich ist und ein vollständiges Versagen riskiert, wenn Änderungen am Code vorgenommen werden, die vom beabsichtigten Verhalten des Algorithmus abweichen.}

Ein PRNG kann als eine Wiederholung angesehen werden Zweckmäßiger Verschlüsselungsalgorithmus. Tatsächlich können Sie ein kryptografisch sicheres PRNG erstellen, indem Sie einen Zähler wie AES zum Verschlüsseln eines Zählers verwenden. Solange der Verschlüsselungsschlüssel (Seed) geheim ist, kann die Ausgabe nicht vorhergesagt und der Seed nicht entdeckt werden. Wenn Sie so darüber nachdenken, wird es einfacher zu verstehen, wie eine kleine, unwichtige Änderung des Codes die Sicherheit des Algorithmus vollständig beeinträchtigen kann.

Sammeln von Zufälligkeiten

Wie sammeln moderne Geräte tatsächlich Zufälligkeiten? Nehmen wir einen Server, der irgendwo in einem Rechenzentrum leise läuft. Um Dinge wie TLS zu unterstützen, benötigt es eine große Menge völlig unvorhersehbarer Daten, die nicht von einem wirklich zufälligen Stream unterschieden werden können. Ohne eine dedizierte Hardware-Rauschquelle muss die Zufälligkeit von innen kommen. Computer streben danach, vollständig deterministisch zu sein, aber sie haben viel Input von nicht deterministischen Geräten. Enter ... Interrupts!

In moderner Hardware ist ein Interrupt ein Signal, das von der Hardware ausgegeben wird, um die CPU auf eine Statusänderung aufmerksam zu machen. Dadurch kann die CPU vermeiden, dass jedes Hardwaregerät schnell nach Updates abgefragt wird, und stattdessen darauf vertrauen, dass das Gerät es zu gegebener Zeit asynchron benachrichtigt. Wenn ein Interrupt auftritt, wird ein Interrupt-Handler aufgerufen, um das Signal zu verarbeiten. Es stellt sich heraus, dass dieser Handler der perfekte Ort ist, um Zufälligkeit zu erlangen! Wenn Sie das Timing von Interrupts auf Nanosekundenebene messen, erhalten Sie schnell ein gutes Stück Zufälligkeit. Dies liegt daran, dass Interrupts für alle möglichen Dinge ausgelöst werden, von Paketen, die auf der Netzwerkkarte ankommen, bis zu Daten, die von einer Festplatte gelesen werden. Einige dieser Interrupt-Quellen sind in hohem Maße nicht deterministisch, wie eine Festplatte, die auf der physischen Bewegung eines Aktuators beruht.

Sobald das Betriebssystem genügend zufällige Bits gesammelt hat, mindestens ein kleiner Startwert 128 Bit können in ein kryptografisch sicheres PRNG eingespeist werden, um einen unbegrenzten Strom von Pseudozufallsdaten zu erzeugen. Wenn jemand nicht genau vorhersagen kann, wann jeder vergangene Interrupt aufgetreten ist, kann er den Keim nicht ableiten und die zukünftige PRNG-Ausgabe nicht vorhersagen. Dadurch ist die Ausgabe vollständig für TLS-Schlüssel geeignet.

_{* Ein sicherheitsorientiertes PRNG wird als kryptografisch sicheres PRNG oder CSPRNG bezeichnet. Die Verwendung eines regulären PRNG, wenn eine Anwendung ein CSPRNG anfordert, kann zu Sicherheitslücken führen. Sub>}

In der Vergangenheit waren für die Kryptografie geeignete Hardware-RNGs auf dem PC nicht allgemein verfügbar: gemäß dieser Frage AMD hat erst vor einigen Jahren Unterstützung hinzugefügt, sodass ein Softwareanbieter dies auch heute noch kann. ' Ich gehe einfach davon aus, dass es verfügbar sein wird. Dies ist vermutlich der Grund, warum OpenSSL (wie in Ihrem Zitat beschrieben) eine Software RNG verwendete, wodurch es für den im Code gefundenen Fehler anfällig wurde.

(Wie in den Kommentaren ausführlich erläutert, enthält ein Standard-PC eine Reihe von "Entropiequellen", die ein Software-RNG nutzen kann - und ich glaube, OpenSSL tut dies, obwohl ich nicht besonders vertraut bin damit - aber offensichtlich kann in diesem Szenario ein Fehler in der Software zu schlechten Zufallszahlen führen, wie es tatsächlich passiert ist.)

Es gibt auch Bedenken, dass Hardware-RNGs möglicherweise hinter der Tür stehen Dies führt dazu, dass Hardware-RNGs mit anderen Entropiequellen kombiniert werden, anstatt sie unverändert zu verwenden. (Backdoor-Hardware wird auch in Ihrem verlinkten Artikel erwähnt, einige Absätze nach dem von Ihnen zitierten Bit.)

Es sollte auch erwähnt werden, dass Hardware-RNGs bei weitem nicht so einfach zu implementieren sind wie Ihre Frage schlägt vor ... zum einen können naive Implementierungen für verschiedene physische Angriffe anfällig sein. Wenn Sie beispielsweise zufällige Bits basierend auf Vibrationen erzeugen, was passiert, wenn jemand einen Ultraschall darauf richtet? Selbst unter idealen Bedingungen gibt es wahrscheinlich eine Art Verzerrung in den Ergebnissen, die die generierten Bits für die kryptografische Verwendung unsicher machen könnte.

Aus diesem Grund verwenden reale Implementierungen Hardware-Rauschen, verarbeiten es aber auch kryptographisch. An diesem Punkt sind Sie jedoch wieder bei der Frage, ob der Algorithmus (oder seine Implementierung) absichtlich sabotiert wurde oder vielleicht nicht so robust ist, wie angenommen.

Weil sie schwer zu testen sind

Während es einfach zu testen ist, ob ein Zufallszahlengenerator eine Ausgabe mit dem richtigen Format erzeugt, ist die Bestimmung, ob sie statistisch zufällig ist, viel komplizierter und Es ist unwahrscheinlich, dass sie in eine automatisierte Testsuite aufgenommen werden. Viele andere Codes sind viel offensichtlicher, wenn Sie sie beschädigen.

Krypto muss richtig sein

Stellen Sie im Allgemeinen sicher, dass der Code korrekt ist ist schwierig. Eine Rettung für viel Code ist, dass nur ein kleiner Teil der Korrektheitsfehler zu Sicherheitslücken führt. Bei kryptografischem Code - einschließlich Zufallszahlengeneratoren - führen viele Korrektheitsfehler jedoch zu Sicherheitslücken. Krypto-Code muss korrekt und sicher sein und es ist schwierig, sicherzustellen, dass er korrekt ist.

Der Debian-Betreuer hat einen schwerwiegenden Fehler gemacht.

Der Code ist nicht korrekt eigentlich so zerbrechlich. Damit es unsicher gemacht werden konnte, musste der Betreuer größere Fehler machen. Nur Zeilen herauszuschneiden, die Warnungen mit nur flüchtigen Überprüfungen erzeugen, dass nichts kaputt ist, ist ziemlich mies.

Bearbeiten: Es war nicht nur das Schuld des Betreuers, siehe Angels Kommentar

Einer der wichtigsten Aspekte eines Zufallsgenerators ist, dass der Wert jedes Zufallsbits nicht nur vollständig unabhängig von den Werten aller anderen von ihm erzeugten Bits sein muss, sondern auch vollständig unabhängig von allem anderen im Universum könnte ein Gegner beobachten oder beeinflussen. Leider ist diese Eigenschaft oft eine der am schwersten zu garantierenden. Das Beste, was man im Allgemeinen tun kann, ist, Bits auf eine Weise zu erzeugen, die wahrscheinlich keine ausnutzbare Beziehung zu irgendetwas anderem im Universum hat.

Als einfaches Beispiel, wenn ein Gegner mit einem hochfokussierten HF-Sender dies getan hätte die Fähigkeit, Ihren Zufallszahlengenerator so zu beeinflussen, dass bestimmte Stichproben seiner Wahl eine Wahrscheinlichkeit von 95% haben, solche zu ergeben, während der Rest nur eine Wahrscheinlichkeit von 5% hat, dies zu tun. Wenn man einfach 128 Bit von einem solchen Generator lesen und sie in einen 128-Bit-Schlüssel einbauen würde, hätte ein Angreifer, der einen Brute-Force-Angriff auf Bitmuster in der Nähe desjenigen konzentrierte, das zur Beeinflussung des Generators verwendet wurde, eine viel größere Wahrscheinlichkeit schneller Erfolg als wenn der Generator unvoreingenommen gewesen wäre. Nehmen wir jedoch an, dass man nicht einzeln Bits auswählt, sondern Gruppen von 7 Bits auswählt und sie zusammen xoriert. Dies würde die Zeit für die Generierung eines 128-Bit-Schlüssels um das Siebenfache verlängern, aber der Einfluss eines Angreifers würde von 95/5 auf 74/26 verringert, was die Wahrscheinlichkeit, dass der Schlüssel dem Bitmuster des Angreifers nahe kommt, erheblich verringert versuchen zu erzwingen.

Nehmen wir alternativ an, man würde 128 zufällige Bits generieren, sie auf irgendeine Weise hashen und sie dann mit weiteren 128 zufälligen Bits xor. Dies würde nur das Generieren von 256 Bit anstelle von 896 erfordern, würde es einem Angreifer jedoch sehr schwer machen, eine Verzerrung im Generator auszunutzen. Obwohl die Aufzählung der wahrscheinlichsten 95.000.000.000-Bit-128-Bit-Muster eine Wahrscheinlichkeit von ungefähr 50% hätte, mit einer Gruppe von 128 Bits übereinzustimmen, die vor dem Hash verwendet wurden, oder derjenigen, mit der der Hash-Wert xor'ed wurde, der endgültigen Verteilung nach dem xor Es ist unwahrscheinlich, dass ausnutzbare Verzerrungen oder Informationslecks auftreten.

Die häufig verwendeten sicheren RNGs wie Linux / dev / random, ChaCha20 oder RdRand funktionieren in vielen herkömmlichen Fällen gut. Sie sind jedoch alles andere als idiotensicher. Angenommen, Sie tun etwas Lustiges, als würden Sie Ihre Echtzeituhr nicht einrichten, wenn Sie beim Booten Zufallszahlen generieren. Wenn Sie nicht verstehen, wie sich dies auf Ihr RNG auswirkt, kann jemand, der dies tut, mit Ihrem privaten Schlüssel davonlaufen. Hier gibt es wenig Raum für Fehler, da eine kleine Menge an Nicht-Zufälligkeit ein gesamtes kryptografisches Protokoll wie die Schlüsselgenerierung gefährden kann.

Während Probleme mit naiven Roll-Your-Own-Implementierungen von Zufallszahlengeneratoren oder physische Interferenzen in Ihrer Hardware für gute Diskussionen sorgen, sind die meisten Schwachstellen in den Nachrichten mit Zufallszahlengeneratoren wie z Das von Ihnen erwähnte Debian-Problem ist nicht auf diese Probleme zurückzuführen. Die größten Probleme, die ich wiederholt gesehen habe, sind Entwickler, die glauben, sie hätten eine gute Entropiequelle, um den Zufallszahlengenerator zu säen, wenn sie dies tatsächlich nicht tun, und fälschlicherweise zulassen, dass der Zustand des Zufallsgenerators entdeckt und ausgenutzt wird, oder dass es an strengen Tests mangelt des Zufallszahlengenerators selbst. Die NSA muss Ihre Schlüsselgenerierung nicht hintertüren, wenn Sie einer von 0,75% der TLS-Clients sind, die Schlüssel mit niedriger Entropie verwenden. Zusammenfassend lässt sich sagen, dass Entwickler die wenigen, wenn überhaupt, Warnungen ignorieren und davon ausgehen, dass ihr RNG in jeder Anwendung funktioniert.

Was ist Entropie und woher bekomme ich welche?

Da alle Computerprogramme produzieren Dieselben Ausgänge bei gleichen Eingaben müssen von einer Entropiequelle (oder unvorhersehbaren Daten) im Betriebssystem oder in der Hardware gelesen werden. Heutzutage haben wir Dinge wie den RdRand-Befehl, der jede Sekunde Dutzende oder Hunderte von MB Entropie erzeugen kann. Geräte mit Hardware-Zufallszahlengeneratoren wie der Ferranti Mark 1 von 1951 oder der Intel 82802 Firmware Hub von 1999 waren jedoch bis in die 2010er Jahre eher die Ausnahme als die Regel.

Historisch gesehen verlassen sich Zufallszahlengeneratoren daher auf relativ langsame Entropiequellen wie menschliche Eingaben oder Computer-Timings, und Legacy-Systeme verfügen möglicherweise fast über keine integrierten Funktionen mit guten Entropiequellen. Linuxs / dev / random kann beispielsweise die Startuhrzeit, das Timing menschlicher Eingabegeräte, Festplatten-Timings, IRQ-Timings und sogar die Änderung des Entropiepools durch andere Threads verwenden.

In vielerlei Hinsicht Zufallszahlengeneratoren sind zerbrechlich, weil diese Standardmethoden, um Entropie zu erhalten, nicht narrensicher sind. Alles, was diese Entropiequellen vorhersehbar oder eingeschränkt macht, gefährdet Ihr RNG, zum Beispiel:

• Der von Ihnen festgestellte Debian-Fehler verwendete nur die Prozess-ID für die Entropie.
• Wenn Sie ein kopfloses, vorkonfiguriertes Betriebssystem verwenden, das beim Booten Schlüssel generiert, können viele Entropiequellen von Linux vorhersehbar sein. Quelle
• Die Java-Kryptografiearchitektur von Android erfordert auf einigen Geräten eine explizite Initialisierung von einer guten Entropiequelle.
• Wenn Sie unter Linux zu schnell Zufallszahlen generieren, wird der Entropiepool schneller erschöpft, als er wieder aufgefüllt werden kann, was zu weniger zufälligen Zahlen führt.

Herausfinden des Zustands und des Mangels an Nachsaat

Oft erhalten RNGs nicht bei jedem Funktionsaufruf eine neue Entropie, wie dies bei / dev / random der Fall ist. Manchmal kann man nicht schnell genug Entropie bekommen oder man vertraut der Entropiequelle nicht vollständig. Stattdessen wird das RNG mit einer bekannten Entropiequelle ausgesät und erzeugt dann unabhängige Werte aus diesem Keim. Wenn jedoch jemand den internen Zustand des Generators herausfindet, laufen die Dinge schlecht, was zu allem führt, vom Klonen von Smartcards bis zum Betrügen eines Spielautomaten in Vegas.

Ein Pufferüberlaufangriff oder ein ähnlicher Angriff kann den Status des Zufallszahlengenerators anzeigen. Das Erlernen des Zustands kann auch mit einem Brute-Force-Angriff möglich sein, insbesondere wenn der Algorithmus bekannt und reversibel ist, schnell berechnet werden kann oder ein Klartext bekannt ist. Dies war der Fall bei Problemen mit Windows XP, Dropbear SSH-Bibliothek, XorShift128 + in Chrome und dem Messerne-Twister-Algorithmus unter vielen anderen.

Wenn für diese Angriffe im bekannten Zustand eine erweiterte Abschwächung erforderlich ist, ist das RNG anfällig. Der beste Weg, um Angriffe mit bekanntem Status abzuschwächen, besteht darin, keinen anfälligen Algorithmus zu verwenden (wie die meisten CSRNGs). Diese Frage erklärt auch genauer, was ein gutes RNG sicher macht. Manchmal weisen jedoch auch CSRNGs Schwachstellen auf (z. B. die RNG-Sicherheitsanfälligkeit im Linux 2.6.10-Kernel). Eine gründliche Verteidigung erfordert daher Abschwächungen wie die Verwendung separater Zustände für Zufallszahlengeneratoren (möglicherweise einen pro Benutzer), die häufige Aktualisierung des Seeds und den Schutz vor Seitenkanalangriffen und Pufferüberläufen.

Schuldzuweisungen zwischen Entwicklern und Benutzern

Oft sind diese RNGs fragil, da die Einschränkungen zwischen Bibliotheksentwicklern oder Betriebssystemerstellern, die kein narrensicheres System entwickeln können, und Benutzern, die dies erwarten, falsch kommuniziert werden einer. Linux beispielsweise zwingt Benutzer, zwischen hoher Latenz / dev / random und potenziell niedriger Entropie / dev / urandom zu wählen. Als weiteres Beispiel hatte PHP vor 5.3 keine Unterstützung für starke PRNGs in Windows über Schnittstellen wie mcrypt_create_iv () und hatte vor 7.0 kein gutes integriertes CSPRNG.

Schwierigkeiten bei der Erkennung

Bei der Diskussion von Zufallszahlen gibt es einen beliebten Diskussionspunkt, bei dem für eine wirklich zufällige Zahl jede Möglichkeit gleich wahrscheinlich ist und es unendlich viele mögliche Muster gibt. Wie können Sie also eine Sequenz wirklich betrachten und sagen, dass sie nicht zufällig ist? (relevanter Dilbert)

In Wirklichkeit ist das Erkennen von Mustern in Zufallszahlen ein ausgereiftes, wenn auch unvollkommenes Feld, und die Frage, ob Nicht-Zufälligkeit erkannt werden kann, wurde seit M.G. Kendall und B. Babington-Smiths Arbeit von 1938. Sie können nachweisen, dass bestimmte Arten von Mustern nicht wesentlich häufiger auftreten als zufällige Zufälle. Zum Beispiel kann ich überprüfen, ob die Ziffer 1 häufiger als andere Ziffern ist, wobei die Schwellenwerte durch einen Chi-Quadrat-Test bestimmt werden. Solange diese getesteten Muster zumindest aus der Ferne wahrscheinlich sind und Sie einen ausreichend langen Satz generierter Zahlen überprüfen, ist die Wahrscheinlichkeit eines falsch positiven Ergebnisses gering. Während einige versteckte Probleme mit einigen Zufallszahlengeneratoren jahrelang unentdeckt bleiben können, sind Sie es, wenn Sie eine grundlegende Kryptoanalyse durchgeführt und dann Tests in Industriequalität durchgeführt haben, wie in dieser Frage beschrieben kann nicht zu viel falsch machen.

Designer unterschätzen jedoch möglicherweise auch nur ihre Angreifer (wie sollten Sie vorhersagen, dass Leute Ihren Spielautomaten rückentwickeln und zeitlich festlegen würden?). Schlimmer noch, manchmal wird der Zufallszahlengenerator oder die Entropieerzeugung nie von einem Experten überprüft, und nur das Ergebnis der Verwendung des RNG wird untersucht, beispielsweise wenn PS3-Firmware-Signaturen mit einer konstanten "zufälligen" Ausgabe signiert wurden .

Letztendlich ist das Problem hier ähnlich wie bei einem Großteil der Cybersicherheit: Sie haben einen sehr komplexen Satz von Protokollen, Anforderungen und Geräten für Zufallszahlen. Wenn Sie die Komplexität nicht verstehen, sind Sie wie immer anfällig für einen Angreifer, der dies tut.