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
• One-Time-Pads
• 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.

Im Idealfall wird die Erstellung solcher Zufallszahlen durch andere zufällige Informationsquellen gespeist, was zum Beispiel ein hardwarebasierter Zufallsgenerator sein kann, aber auch nicht vorhersehbare Zustände in bestimmten Prozessen des Systems. Theoretisch ist es natürlich so, dass die Zufälligkeit einer aus solchen Initialdaten generierten Zufallszahl nicht höher sein kann als die Ausgangswerte. Jedoch ist es manchmal notwendig, größere Mengen von Zufallszahlen zu generieren, als aus diesen Quellen zu beziehen sind, in diesem Fall bedient man sich eines CSPRNG.

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.

Aufbau eines CSPRNG

Ein CSPRNG kann aus unterschiedlichen kryptografischen Primitiven aufgebaut werden: Stromverschlüsselung, Blockverschlüsselung, Hash-Funktionen oder auf der Grundlage mathematisch harter Probleme.

Beispiele

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

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.

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.

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

• Craps Test

wendet eine Teststatistik auf 200000 Craps-Spiele an

Standards

Viele Designs von CSPRNGs wurden standardisiert und sind dokumentiert in:

• FIPS 186-2^[2]
• ANSI X9.17-1985 Appendix C
• ANSI X9.31-1998 Appendix A.2.4
• ANSI X9.62-1998 Annex A.4

Einzelnachweise

1. ↑ http://burtleburtle.net/bob/rand/isaac.html
2. ↑ DIGITAL SIGNATURE STANDARD (DSS), Januar 2000

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)