Kryptographisch sicherer Zufallszahlengenerator

Ein kryptographisch sicherer Zufallszahlengenerator (auch kryptographisch geeigneter Zufallszahlengenerator, bzw. engl. cryptographically secure pseudo-random number generator (CSPRNG)) ist ein für die Kryptologie geeigneter Generator für Pseudozufallszahlen. Solche Zufallszahlen werden in vielen Bereichen der Kryptologie benötigt wie zum Beispiel:

• bei der Schlüsselgenerierung
• einmal genutzten Zahlen Nonces
• Stromverschlüsselung
• Salt

Die Qualitätsanforderungen für die Zufälligkeit solcher Zahlen sind sehr unterschiedlich. Für Nonces genügt es, die Einmaligkeit der Zahl im Zufallsexperiment zu garantieren, für die Erstellung eines Hauptschlüssels oder sogar eines One-Time-Pads sind die Anforderungen an die Zahl ungleich höher. So bleibt ein One-Time-Pad in der Theorie nur unknackbar, wenn er aus natürlichen Zufallszahlen erstellt wurde.

Grundsätzlich sind für einen CSPRNG dieselben Voraussetzungen wie für einen normalen Pseudozufallszahlengenerator vonnöten, nur dass für die Sicherheit noch einige zusätzliche Bedingungen erfüllt sein müssen. Die von ihm erzeugte Zahlenfolge sollte für einen Beobachter nicht von einer echten Zufallszahlenfolge unterscheidbar sein. Außerdem sollte für einen Beobachter sein interner Zustand geheim bleiben, d. h. der Generator stellt eine Black Box dar.

Nichtdeterministische CSRNG

Im Idealfall wird die Erstellung solcher Zufallszahlen durch andere zufällige Informationsquellen gespeist. Das kann zum Beispiel ein hardwarebasierter Zufallsgenerator sein kann, aber auch nicht vorhersehbare Zustände in bestimmten Prozessen des Systems. Theoretisch kann die Entropie einer aus solchen Initialdaten generierten Zufallszahl nicht höher sein als die Ausgangswerte selbst.

Für kryptologische Anwendungen sollten nicht-deterministische Generatoren verwendet werden. Nur sie können echte Zufälligkeit garantieren und sind weiterhin nicht reproduzierbar.

Siehe auch: physikalischer Zufallszahlengenerator

Deterministische CS(P)RNG

Unter Umständen ist der Einsatz eines nicht-deterministischen Generators nicht möglich oder zu langsam. In diesem Fall greift man auf einen deterministischen, kryptologisch sicheren Pseudozufallszahlen-Generator zurück. Dieser kann auf Block- oder Stromverschlüsselung, einer sicheren Hash-Funktion oder anderen mathematisch harten Problemen basieren.

Kryptologische Generatoren

Eine Verschlüsselungs- oder Hash-Funktion kann im sog. Counter- oder Output-Feedback-Modus betrieben werden. Hierbei ist kritisch, dass es nicht möglich ist den Anfangszustand herauszufinden. Den internen Zustand des Generators zu ermitteln, ist dann gleichbedeutend damit, die Verschlüsselung selbst zu „knacken“.

Die hierbei generierte Zahl ist kryptologisch sicher und pseudozufällig (soweit es auch die verwendetete Funktion garantiert). Generatoren, die auf bewährten Funktionen basieren, wie z. B. AES oder SHA-1, bestehen alle gängigen statistischen Tests auf Zufälligkeit.

Zahlentheoretische Generatoren

Blum-Blum-Shub-Generator

Der BBS-Generator beruht auf der Annahme, dass Faktorisierung von Ganzzahlen ein schwieriges Problem ist, das nicht in polynomieller Zeit gelöst werden kann.

Beispiele

RC4 ist ein Stromchiffrieralgorithmus, das als CSPRNG gebraucht wird. Zu dieser Gruppe zählt auch ISAAC.

ANSI X9.17

Dieser Pseudozufallszahlengenerator beruht auf Triple-DES, einem Blockverschlüsselungsverfahren.

FIPS-186-Generator

Der in FIPS-186 standardisierte Generator verwendet eine Einwegfunktion, die wahlweise auf der Hash-Funktion SHA-1 oder der Blockchiffre DES basiert, um Schlüssel und zufällige Geheimnisse für das Signieren mit dem Digital Signature Algorithm zu erzeugen.

Tests auf Zufälligkeit

FIPS 140

In diesem Standard ist eine Test-Suite für CSPRNG aufgeführt. Dazu werden 20000 Ausgabebits verschiedenen statistischen Tests unterworfen:

• Monobit-Test
• Pokertest
• Run-Test
• Long-Run-Test (ein Run mit >34 Bits fällt durch)

Maurer's Universal Test

Die Idee hinter diesem Test ist, dass es nicht möglich sein sollte, eine Zufallszahlenfolge signifikant zu komprimieren.

Marsaglias Diehard Testsuite

Umfangreiche Testsuite, u. a.:

Birthday Spacings Test (Geburtstagsabstände)

wählt zufällige Punkte auf einem Intervall. Diese sollten Poisson-verteilt sein. Das Prinzip des Tests ist verwandt dem Geburtstagsparadox.

Overlapping Permutations (überlappende Permutationen)

untersucht jeweils fünf aufeinanderfolgende (Integer-)Zahlen auf Gleichverteilung. Diese können 5!=120 verschiedene Anordnungen haben, die gleichwahrscheinlich sind.

Binary Rank Test (binärer Rangtest)

bildet aus den Bits der zu testenden Zahlenfolge zufällige Matrizen, berechnet deren Ränge. Darauf wird ein Chi-Quadrat-Test angewandt.

Bitstream Test (Bitfolgen-Test)

betrachtet die zu testende Zahlenfolge als Bitfolgen aus jeweils 20-Bit-„Worten“, die sich überlappen. Es gibt 2²¹ sich überlappende 20-Bit-Worte und 2²⁰ mögliche 20-Bit-Worte. Der Test zählt die fehlenden 20-Bit-Worte. Diese sollten annähernd normalverteilt sein.

Count-The-1s Test (Zähle die Einsen)

untersucht Bytefolgen. Er zählt die „1“-Bits in den Bytefolgen und vergleicht die erhaltenen Werte mit den statistisch zu erwartenden Werten.

Parking Lot Test (Parkplatztest)

platziert zufällig Einheitskreise in ein 100x100 Quadrat. Die Anzahl der n=12000 „geparkten“ Kreise sollte einer Normalverteilung folgen.

Minimum Distance Test (Minimaler Abstand)

platziert n=8000 Punkte in ein 10000x10000 Punkte Quadrat. Dann wird der kleinste Abstand zwischen den Punktepaaren bestimmt. Der Quadrat dieser Abstände sollte exponentialverteilt sein.

3D Spheres Test (3D-Kugel-Test)

platziert zufällig n=4000 Punkte in einen Würfel der Kantenlänge 1000. Danach wird um jeden Punkt eine Kugel mit dem Radius (Mittelpunkt, Punkt mit minimalem Abstand) gebildet. Das kleinste Kugelvolumen sollte einer Exponential-Verteilung folgen.

Runs Test

entnimmt n Kugeln aus einer Urne mit zwei verschiedenen Kugelsorten. Gleichfarbige nacheinanderfolgend gezogene Kugeln werden zu einem Zug („Run“) zusammengefasst. Die Anzahl der übriggebliebenen Züge soll der einer echten Zufallsziehung zur gegebenen Länge n entsprechen.

Craps Test

wendet eine Teststatistik auf 200000 Craps-Spiele an

Standards

Viele Designs von CSPRNGs wurden standardisiert und sind dokumentiert in:

• FIPS 186-2 (veraltet)
• ANSI X9.17-1985 Appendix C
• ANSI X9.31-1998 Appendix A.2.4
• ANSI X9.62-1998 Annex A.4

Literatur

• Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone: Handbook of Applied Cryptography. CRC Press, Boca Raton FL u. a. 1997, ISBN 0-8493-8523-7 (CRC Press Series on Discrete Mathematics and its Applications), Kapitel 5.

Weblinks

• Referenz für CSPRNG (englisch)
• Testsuite
• Diehard Testsuite
• Zufallszahlengenerator zur Erzeugung von One-Time-Pads (englisch)