Wie funktioniert ein kryptografisch sicherer Zufallszahlengenerator?

Ich verstehe, wie Standard-Zufallszahlengeneratoren funktionieren. Aber wenn man mit Krytographie arbeitet, müssen die Zufallszahlen wirklich zufällig sein.

Ich weiß, dass es Instrumente gibt, die kosmisches weißes Rauschen lesen , um sichere Hashes zu generieren, aber Ihr Standard-PC hat dies nicht.

Wie erhält ein kryptografisch sicherer Zufallszahlengenerator seine Werte ohne wiederholbare Muster?

Ein kryptografisch sicherer Zufallsgenerator für Zahlen, wie Sie ihn möglicherweise zum Generieren von Verschlüsselungsschlüsseln verwenden, sammelt Entropie - dh unvorhersehbare Eingaben - aus einer Quelle, die andere Personen nicht beobachten können.

Beispielsweise sammelt / dev / random (4) unter Linux Informationen aus der zeitlichen Variation von Hardware-Interrupts von Quellen wie Festplatten, die Daten, Tastendrücke und eingehende Netzwerkpakete zurückgeben. Dieser Ansatz ist sicher, vorausgesetzt, der Kernel überschätzt nicht, wie viel Entropie er gesammelt hat. Vor einigen Jahren wurden die Schätzungen der Entropie aus den verschiedenen Quellen reduziert, was sie weitaus konservativer machte. Hier ist eine Erklärung, wie Linux die Entropie schätzt .

Keines der oben genannten Verfahren weist einen besonders hohen Durchsatz auf. / dev / random (4) ist wahrscheinlich sicher, aber es behält diese Sicherheit bei, indem es sich weigert, Daten weiterzugeben, sobald nicht sicher ist, ob diese Daten sicher zufällig sind. Wenn Sie beispielsweise viele kryptografische Schlüssel und Nonces generieren möchten, sollten Sie wahrscheinlich auf Hardware-Zufallszahlengeneratoren zurückgreifen.

Häufig werden Hardware-RNGs entwickelt, um die Differenz zwischen einem Paar von Oszillatoren abzutasten, die mit nahezu derselben Geschwindigkeit laufen, deren Raten jedoch je nach thermischem Rauschen geringfügig variieren. Wenn ich mich recht erinnere, funktioniert der Zufallszahlengenerator, der für die britische Premium Bond Lotterie ERNIE verwendet wird, auf diese Weise.

Alternative Schemata umfassen das Abtasten des Rauschens auf einem CCD (siehe lavaRND ), den radioaktiven Zerfall (siehe Hotbits ) oder das atmosphärische Rauschen (siehe random.org ) oder das Anschließen eines AM-Radios, das an einem anderen Ort als einem Sender eingestellt ist, an Ihre Soundkarte. Oder Sie können den Benutzer des Computers direkt bitten, eine Minute lang wie ein gestörter Schimpanse auf die Tastatur zu schlagen , unabhängig davon, was auf Ihrem Boot schwimmt.

Wie andras betonte, dachte ich nur daran, über einige der häufigsten Entropiesammelschemata zu sprechen. Thomas Pornin Antwort und Johannes Rössel Antwort tun beide gute Jobs zu erklären , wie man über Mangeln gesammelt Entropie um Hand Bits es wieder heraus gehen kann.

Für kryptografische Zwecke ist es erforderlich, dass der Strom "rechnerisch nicht von gleichmäßig zufälligen Bits zu unterscheiden" ist. "Computergestützt" bedeutet, dass es nicht wirklich zufällig sein muss, sondern dass es jedem ohne Zugang zu Gottes eigenem Computer so erscheint.

In der Praxis bedeutet dies, dass das System zuerst eine Folge von n wirklich zufälligen Bits erfassen muss. n muss groß genug sein, um eine erschöpfende Suche zu verhindern, dh es muss unmöglich sein, alle 2 ^ n Kombinationen von n Bits auszuprobieren . Dies wird in Bezug auf die heutige Technologie erreicht, solange n größer als etwa 90 ist, Kryptographen jedoch nur Zweierpotenzen lieben. Daher ist es üblich, n = 128 zu verwenden .

Diese n zufälligen Bits werden erhalten, indem "physikalische Ereignisse" gesammelt werden, die für die Physik unvorhersehbar sein sollten. Normalerweise wird das Timing verwendet: Die CPU verfügt über einen Zykluszähler, der mehrere Milliarden Mal pro Sekunde aktualisiert wird, und einige Ereignisse treten mit unvermeidlichem Jitter auf (eingehende Netzwerkpakete, Mausbewegungen, Tastenanschläge ...). Das System codiert diese Ereignisse und "komprimiert" sie dann durch Anwenden einer kryptografisch sicheren Hash-Funktion wie SHA-256 (die Ausgabe wird dann abgeschnitten, um unsere n Bits zu erhalten). Was hier zählt, ist, dass die Codierung der physikalischen Ereignisse genug Entropie hat : grob gesagt, dass diese Ereignisse zusammen mindestens 2 ^ n angenommen haben könntenKombinationen. Die Hash-Funktion sollte per Definition gute Arbeit leisten, um diese Entropie in einem n- Bit-String zu konzentrieren.

Sobald wir n Bits haben, verwenden wir einen PRNG (Pseudo-Random Number Generator), um so viele Bits wie nötig herauszukurbeln. Ein PRNG wird als kryptografisch sicher bezeichnet, wenn unter der Annahme, dass es über einen ausreichend breiten unbekannten n- Bit-Schlüssel arbeitet, seine Ausgabe rechnerisch nicht von gleichmäßig zufälligen Bits zu unterscheiden ist. In den 90er Jahren war RC4 eine beliebte Wahl , die sehr einfach zu implementieren und recht schnell ist. Es stellte sich jedoch heraus, dass es messbare Vorurteile gab, dh es war nicht so ununterscheidbar, wie ursprünglich gewünscht. Das eSTREAM-Projektbestand darin, neuere Designs für PRNG zu sammeln (tatsächlich Stream-Chiffren, da die meisten Stream-Chiffren in einem PRNG bestehen, dessen Ausgabe mit den zu verschlüsselnden Daten XOR-verknüpft ist), sie zu dokumentieren und die Analyse durch Kryptographen zu fördern. Das eSTREAM-Portfolio enthält sieben PRNG-Designs, die als sicher genug eingestuft wurden (dh sie widersetzten sich der Analyse, und Kryptographen haben in der Regel ein gutes Verständnis dafür, warum sie sich widersetzten). Unter ihnen sind vier "für Software optimiert". Die gute Nachricht ist, dass diese neuen PRNG zwar viel sicherer als RC4 zu sein scheinen, aber auch spürbar schneller sind (wir sprechen hier von Hunderten von Megabyte pro Sekunde). Drei von ihnen sind "für jede Verwendung kostenlos" und der Quellcode wird bereitgestellt.

Aus gestalterischer Sicht verwendet PRNG einen Großteil der Elemente von Blockchiffren wieder. Die gleichen Konzepte der Lawine und der Diffusion von Bits in einen breiten internen Zustand werden verwendet. Alternativ kann ein anständiges PRNG aus einer Blockverschlüsselung erstellt werden: Verwenden Sie einfach die n- Bit-Sequenz als Schlüssel für eine Blockverschlüsselung und verschlüsseln Sie aufeinanderfolgende Werte eines Zählers (ausgedrückt als m- Bit-Sequenz, wenn die Blockverschlüsselung m - verwendet) Bitblöcke). Dies erzeugt einen pseudozufälligen Strom von Bits, der rechnerisch nicht von zufällig zu unterscheiden ist, solange die Blockverschlüsselung sicher ist und der erzeugte Strom nicht länger als m * 2 ^ (m / 2) Bits ist (für m = 128)Dies bedeutet ungefähr 300 Milliarden Gigabyte, das ist also groß genug für die meisten Zwecke. Diese Art der Verwendung wird als Counter Mode (CTR) bezeichnet .

Normalerweise ist eine Blockverschlüsselung im CTR-Modus nicht so schnell wie eine dedizierte Stream-Verschlüsselung (der Punkt der Stream-Verschlüsselung besteht darin, dass durch den Verlust der Flexibilität einer Blockverschlüsselung eine bessere Leistung erwartet wird). Wenn Sie jedoch zufällig eine der neuesten CPUs von Intel mit den AES-NI- Anweisungen haben (bei denen es sich im Grunde um eine AES-Implementierung in Hardware handelt, die in die CPU integriert ist), führt AES mit CTR-Modus zu einer unschlagbaren Geschwindigkeit (mehrere Gigabyte pro) zweite).

Zunächst einmal geht es bei einem kryptografisch sicheren PRNG nicht darum, völlig unvorhersehbare Sequenzen zu generieren. Wie Sie bemerkt haben, macht das Fehlen von etwas, das große Mengen (mehr oder weniger) wahrer Zufälligkeit ^{1 erzeugt} , dies unmöglich.

Sie greifen also auf etwas zurück, das nur schwer vorherzusagen ist. "Schwer" bedeutet hier, dass es unvorstellbar lange dauert, bis zu welchem ​​Zeitpunkt alles, wofür es notwendig war, sowieso veraltet wäre. Es gibt eine Reihe von mathematischen Algorithmen, die dabei eine Rolle spielen. Sie können einen Blick darauf werfen, wenn Sie einige bekannte CSPRNGs verwenden und sich ansehen, wie sie funktionieren.

Die gebräuchlichsten Varianten zum Erstellen eines solchen PRNG sind:

• Verwendung einer Stream-Verschlüsselung, die bereits einen (angeblich sicheren) pseudozufälligen Bitstrom ausgibt.
• Verwenden einer Blockverschlüsselung im Zählermodus

Manchmal werden auch Hash-Funktionen auf einem Zähler verwendet. Wikipedia hat mehr dazu .

Allgemeine Anforderungen sind lediglich, dass es nicht möglich ist, den ursprünglichen Initialisierungsvektor aus dem Bitstrom eines Generators zu bestimmen, und dass das nächste Bit nicht einfach vorhergesagt werden kann.

Für die Initialisierung verwenden die meisten CSPRNGs verschiedene im System verfügbare Quellen, die von wirklich zufälligen Dingen wie Leitungsrauschen, Interrupts oder anderen Ereignissen im System bis zu anderen Dingen wie bestimmten Speicherorten usw. reichen. Der Initialisierungsvektor ist vorzugsweise wirklich zufällig und nicht von einem mathematischen Algorithmus abhängig. Diese Initialisierung wurde für einige Zeit in Debians Implementierung von OpenSSL unterbrochen, was zu schwerwiegenden Sicherheitsproblemen führte.

¹ Das hat auch seine Probleme und man muss vorsichtig sein, um Vorspannungen zu beseitigen, da Dinge wie thermisches Rauschen je nach Temperatur unterschiedliche Eigenschaften haben - Sie haben fast immer Vorspannungen und müssen diese beseitigen. Und das ist an sich keine triviale Aufgabe.

Damit ein Zufallszahlengenerator als kryptografisch sicher angesehen werden kann , muss er gegen Angriffe eines Gegners geschützt sein, der den Algorithmus und eine (große) Anzahl zuvor generierter Bits kennt. Dies bedeutet, dass jemand mit diesen Informationen keinen der verborgenen internen Zustände des Generators rekonstruieren und Vorhersagen darüber treffen kann, wie die nächsten erzeugten Bits mit einer Genauigkeit von mehr als 50% aussehen werden.

Normale Pseudozufallszahlengeneratoren sind im Allgemeinen nicht kryptografisch sicher, da die Rekonstruktion des internen Zustands aus zuvor ausgegebenen Bits im Allgemeinen trivial ist (häufig ist der gesamte interne Zustand nur die letzten N Bits, die direkt erzeugt werden). Ein Zufallszahlengenerator ohne gute statistische Eigenschaften ist auch nicht kryptografisch sicher, da seine Ausgabe zumindest ohne Kenntnis des internen Zustands von der Partei vorhersehbar ist.

In Bezug auf ihre Funktionsweise kann jedes gute Kryptosystem als kryptografisch sicherer Zufallszahlengenerator verwendet werden. Verwenden Sie das Kryptosystem, um die Ausgabe eines "normalen" Zufallszahlengenerators zu verschlüsseln. Da ein Gegner die Klartextausgabe des normalen Zufallszahlengenerators nicht rekonstruieren kann, kann er sie nicht direkt angreifen. Dies ist eine etwas zirkuläre Definition, die die Frage aufwirft, wie Sie das Kryptosystem verschlüsseln, um es sicher zu halten, was ein ganz anderes Problem darstellt.

Jeder Generator verwendet seine eigene Seeding-Strategie. Hier ist jedoch ein Teil der Windows-API-Dokumentation zu CryptGenRandom

Bei Microsoft-CSPs verwendet CryptGenRandom denselben Zufallszahlengenerator, der auch von anderen Sicherheitskomponenten verwendet wird. Dadurch können zahlreiche Prozesse zu einem systemweiten Seed beitragen. CryptoAPI speichert mit jedem Benutzer einen zufälligen Zwischenstart. Um den Startwert für den Zufallszahlengenerator zu bilden, liefert eine aufrufende Anwendung möglicherweise Bits, die sie haben könnte - beispielsweise eine Maus- oder Tastatur-Timing-Eingabe -, die dann sowohl mit dem gespeicherten Startwert als auch mit verschiedenen Systemdaten und Benutzerdaten wie der Prozess-ID und kombiniert werden Thread-ID, Systemuhr, Systemzeit, Systemzähler, Speicherstatus, freie Festplattencluster, Block der Hash-Benutzerumgebung. Dieses Ergebnis wird verwendet, um den Pseudozufallszahlengenerator (PRNG) zu setzen.

In Windows Vista mit Service Pack 1 (SP1) und höher wird eine Implementierung des auf AES-Gegenmodus basierenden PRNG verwendet, das in der NIST-Sonderpublikation 800-90 angegeben ist. In Windows Vista, Windows Storage Server 2003 und Windows XP wird das im FIPS (Federal Information Processing Standard) 186-2 angegebene PRNG verwendet. Wenn eine Anwendung Zugriff auf eine gute Zufallsquelle hat, kann sie den pbBuffer-Puffer mit einigen zufälligen Daten füllen, bevor sie CryptGenRandom aufruft. Der CSP verwendet diese Daten dann, um seinen internen Startwert weiter zu randomisieren. Es ist akzeptabel, den Schritt des Initialisierens des pbBuffer-Puffers vor dem Aufrufen von CryptGenRandom wegzulassen.