Kryptographisch sicherer Zufallszahlengenerator
Ein kryptographisch sicherer Zufallszahlengenerator (auch kryptographisch geeigneter Zufallszahlengenerator, bzw. englisch 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 Nonces (zufällige Bytefolgen)
- 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. Zum einen darf die von ihm erzeugte Zahlenfolge nicht von einer echten Zufallszahlenfolge unterscheidbar sein. Zum anderen darf es nicht möglich sein, anhand der Ausgabe des Generators auf seinen internen Zustand zu schließen, auch wenn die genaue Funktionsweise bekannt ist.
Das BSI spezifiziert Anforderungen an Zufallszahlengeneratoren zur Verwendung in Projekten der Bundesregierung in der Technische Richtlinie BSI TR-03116. Dort werden Funktionsklassen unterschieden und genannt. Die verwendeten Bezeichnungen (PTG.1, PTG2,… DRG.1, DRG.2,…, NTG.1) werden im mathematisch-technischen Anhang aufgelistet.[1] Im Wesentlichen werden dort physikalische RNG (PTG.) von deterministischen RNG (DRG) unterschieden, mit weiterer Unterteilung nach Fehlerdetektion und stochastischer Nachverarbeitung und somit zu den hybriden RNGs gehören, die in dieser Definition keine namentliche Klassen darstellen.
Nichtdeterministische CSRNG
Im Idealfall wird die Erstellung von Zufallszahlen durch eine nicht deterministische Entropiequelle gespeist. Das kann zum Beispiel ein hardwarebasierter Zufallsgenerator sein oder auch ein hybrider Generator. Für kryptologische Anwendungen sollten nicht-deterministische Generatoren verwendet werden, denn nur bei diesen kann garantiert werden, dass sie nicht reproduzierbar oder vorhersagbar sind.
Deterministische CS(P)RNG
In der Regel ist der Einsatz eines nichtdeterministischen Generators nicht möglich oder zu langsam. In diesem Fall greift man auf einen deterministischen, kryptologisch sicheren Pseudozufallszahlengenerator zurück. Kryptologisch sichere Pseudozufallszahlengeneratoren basieren entweder auf einem kryptographischen Primitiv wie einer Block- oder Stromverschlüsselung oder einer sicheren Hash-Funktion, oder auf mathematisch harten Problemen.
Auf kryptographischen Primitiven basierende Generatoren
Eine Verschlüsselungs- oder Hash-Funktion kann im sog. Counter- oder Output-Feedback-Modus betrieben werden. Hierbei ist es wichtig, dass es nicht möglich sein sollte, den Anfangszustand des Generators herausfinden zu können. Den internen Zustand des Generators zu ermitteln, ist dann gleichbedeutend damit, die Verschlüsselung selbst zu brechen.[2]
Die hierbei generierte Zahl ist kryptologisch sicher und pseudozufällig (soweit es auch die verwendete Funktion garantiert). Generatoren, die auf bewährten Funktionen, wie z. B. AES oder SHA-1 basieren, bestehen alle gängigen statistischen Tests auf Zufälligkeit.[3]
Auf zahlentheoretischen Problemen basierende Generatoren
Die Sicherheit des Blum-Blum-Shub-Generators beruht auf der Annahme, dass die Primfaktorzerlegung von Ganzzahlen ein schwieriges Problem ist, das nicht in Polynomialzeit 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 mit dem Geburtstagsparadox.
- Overlapping Permutations (überlappende Permutationen)
- untersucht jeweils fünf aufeinanderfolgende (Integer-)Zahlen auf Gleichverteilung. Diese können 5!=120 verschiedene Anordnungen haben, die gleich wahrscheinlich 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 221 sich überlappende 20-Bit-Worte und 220 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 100×100-Quadrat. Ein Kreis gilt als erfolgreich geparkt, wenn es keine Überlappung mit einem bereits erfolgreich geparkten Kreis gibt. Die Anzahl der erfolgreich geparkten Kreise nach n=12000 Versuchen sollte annähernd normalverteilt sein.
- Minimum Distance Test (Minimaler Abstand)
- platziert n=8000 Punkte in ein 10000×10000-Punkte-Quadrat. Dann wird der kleinste Abstand zwischen den Punktepaaren bestimmt. Das Quadrat dieser Abstände sollte exponentialverteilt sein.
- 3D Spheres Test (3D-Kugel-Test)
- platziert n=4000 Punkte in einen Würfel der Kantenlänge 1000. Danach wird um jeden Punkt eine Kugel gebildet. Der Radius dieser Kugeln ist der Abstand zwischen dem Mittelpunkt und dem jeweils nächstgelegenen Punkt. Die sich so ergebenden Kugelvolumen sollten einer Exponentialverteilung 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:
Siehe auch
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
- Random Number Generation. NIST Computer Security Division (englisch) – Referenz für CSPRNG
- Testsuite
- Diehard Testsuite
- Zufallszahlengenerator zur Erzeugung von One-Time-Pads (englisch)
Einzelnachweise
- Wolfgang Killmann, Werner Schindler: A proposal for: Functionality classes for random number generators. Version 2.0 Bundesamt für Sicherheit in der Informationstechnik (BSI), 2011. (online)
- NIST 800-20 (PDF; 3,1 MB)
- Pierre L’Ecuyer, Richard Simard: TestU01 Paper
- National Institute of Standards and Technology (Hrsg.): Digital Signature Standard (DSS) (= Federal Information Processing Standards. Nr. 186-2). 2000, Appendix 3. Random Number Generation for the DSA (csrc.nist.gov (Memento vom 18. Mai 2009 im Internet Archive) [PDF]). Digital Signature Standard (DSS) (Memento vom 18. Mai 2009 im Internet Archive)