Pseudozufallszahlen in der Kryptographie

Diplomarbeit von Christian Schiestl

Einleitung:

Viele Bereiche der Informatik sind in steigendem Ausmaß auf Zufallszahlen angewiesen. Man denke nur an Monte-Carlo-Simulationen, Optimierungen mittels genetischer Algorithmen oder aber an Computerspiele, die ohne „intelligente“ Monster wohl nur halb so interessant wären. Durch die zunehmende weltweite Vernetzung von Rechnern haben Sicherheitsaspekte in den letzten Jahren an Bedeutung gewonnen. Schutzmechanismen gegen unbefugten Zugriff auf vertrauliche Daten sowie zur Authentifizierung und Identifikation von Kommunikationspartnern spielen eine immer größer werdende Rolle. Kryptographische Verfahren wie symmetrische Verschlüsselungs-, Public-Key- und Signaturverfahren bieten Möglichkeiten, diese Sicherheitsrisiken zu verringern.

Gerade diese kryptographischen Basismechanismen kommen heutzutage kaum noch ohne Zufallszahlen aus. Beinahe jedes Kryptosystem benötigt irgendwann geheime, nicht vorhersagbare Zufallszahlen. Ohne Zufallsgeneratoren gäbe es keine Kryptographie! Man denke nur an folgende, exemplarische Einsatzgebiete:

Schlüsselerzeugung: Symmetrische und asymmetrische Kryptosysteme benötigen für die sichere Datenverschlüsselung zufällige Schlüssel.

Parametererzeugung: Ein weiteres wichtiges Einsatzgebiet für Zufallszahlen ist die Erzeugung von Parametern für asymmetrische Verschlüsselungsverfahren (z.B. die Generierung großer Primzahlen im RSA-Verfahren). Symmetrische Blockchiffren im CBC-Mode erfordern in Form von Initialisierungsvektoren ebenfalls zufällige Parameter.

Identifikationsprotokolle: Bei Challenge-Response-Verfahren wird auf einer Seite eine zufällige Challenge erzeugt, die die Gegenseite mit ihrem geheimen Schlüssel in signierter Form retourniert. Im Zuge einseitiger Challenge-Response-Verfahren empfängt und verarbeitet beispielsweise jedes GSM-Handy bei jeder Netzanmeldung eine Zufallszahl.

Digitale Signatur-Verfahren: Bestimmte digitale Signatur-Verfahren (wie z. B. DSA, ElGamal) benötigen bei jedem Signiervorgang einen neuen Zufallswert. Bei Zero-Knowledge-Signatur-Verfahren setzt der Signierende eine Zufallszahl ein, um sein Geheimnis zu verbergen.

Protokolle zur Schlüsselverteilung: Zu Beginn einer Sitzung müssen zufällige Sitzungsschlüssel erzeugt und verteilt werden. Bei Diffie-Hellman ähnlichen Protokollen benötigen dazu beide Parteien jeweils einen zufälligen Startwert.

Verschlüsselung: Zufallsfolgen können unmittelbar zur Verschlüsselung eingesetzt werden. Man denke dabei an das informationstheoretisch sichere Verschlüsselungsverfahren „One-Time-Pad“ oder an das Vernam-Verfahren. Das Übermittlungsproblem der langen Zufallsfolgen auf einem sicheren Kanal führte zur Entwicklung von Stromchiffren. Dabei werden ausgehend von einem kurzen zufälligen Startwert mittels Schlüsselstromgenerator auf deterministische Art und Weise reproduzierbare Zufallswerte erzeugt und diese zur Nachrichten-Verschlüsselung verwenden. Der Vorteil von Stromchiffren gegenüber einem One-Time-Pad liegt darin, dass nur noch der kurze, zufällige Initialisierungswert dem Kommunikationspartner auf geheimen Wege mitgeteilt werden muss. Der Einsatz von deterministischen Schlüsselstromgeneratoren hat aber den Verlust der informationstheoretisch beweisbaren Sicherheit zur Folge.

Die Güte der in Kryptosystemen verwendeten Zufallszahlen wirkt sich unmittelbar auf deren Sicherheit aus. Wie Beispiele aus der jüngsten Vergangenheit zeigen (z. B. die aufsehenerregenden Angriffe zweier Berkeley-Studenten auf den Netscape-Browser im Jahre 1995), ermöglicht der Einsatz naiver Zufallszahlengeneratoren in Kryptosystemen diese mit relativ geringem Aufwand zu brechen. Schwache Zufallsgeneratoren stellen somit eine Gefährdung der Sicherheit von Kryptosystemen dar. Selbst Jeff Schiller, Co-Autor des 1994 veröffentlichten Internet RFC mit dem Titel „Randomness Recommendations for Security“ und Mitentwickler von Kerberos V4, hat mit dem Zufall seine liebe Not, konnten doch 1996 Cyberpunks aufgrund einer Schwäche im Kerberos-Zufallszahlengenerator das weltweit eingesetzte System erfolgreich attackieren und die erzeugten Sitzungsschlüssel kompromittieren Viele der in der einschlägigen Literatur beschriebenen Verfahren zur Erzeugung von Zufallszahlen taugen zwar für unterschiedlichste Anwendungen (z.B. für die Monte-Carlo-Simulation), erweisen sich jedoch für kryptographische Zwecke oft als ungeeignet. Eine zufällige Folge, die zwar verschiedenste statistische Tests besteht, gilt noch lange nicht als kryptographisch sicher, sondern ist vielmehr nur dann für die Anwendung in der Kryptographie geeignet, wenn sie unter keinen Umständen vorhersagbar ist. Es stellt sich also die Frage: Welche Generatoren können in der Kryptographie verwendet werden und von welchen Generatoren sollte man lieber die Finger lassen?

Da keine fundierte Studie in Österreich zur Problematik der Zufallszahlenerzeugung für die Kryptographie vorlag, verfolgte ich mit meinem Diplomarbeitsprojekt das Ziel, eine repräsentative Studie zum Thema „Pseudozufallszahlengeneratoren in der Kryptographie“ zu verfassen. Generell werden zwei Klassen von Zufallszahlen unterschieden: Echte Zufallszahlen, die im Zuge von Zufallsexperimenten (z. B. Glücksspiele) erzeugt werden, und sogenannte, reproduzierbare Pseudozufallsfolgen, die mittels deterministischer Algorithmen ausgehend von einem echt zufällig gewählten kurzen Startwert berechnet werden. In der Diplomarbeit konzentrierte ich mich vor allem auf die Klasse der Pseudozufallsgeneratoren und legte besonderes Augenmerk auf Sicherheitsaspekte.

Gang der Untersuchung:

Im ersten Kapitel der Diplomarbeit wird der Leser mit der komplexen Problematik rund um die Erzeugung von Zufallzahlen vertraut gemacht. Eine Diskussion allgemeiner Forderungen an Pseudozufallsgeneratoren bildet den Abschluss des Kapitels.

Von Pseudozufallsfolgen wird verlangt, dass sie über dieselben statistischen Eigenschaften wie echte Zufallsfolgen verfügen. In Kapitel 2 wird eine informelle Darstellung ausgewählter, statistischer Testverfahren zur Überprüfung der Gleichverteilung bzw. der Unabhängigkeit von Pseudozufallsfolgen gegeben. Nach einem in die statistische Testtheorie einführenden Abschnitt, der den Leser kurz mit einigen Grundlagen vertraut machen soll, werden die historisch interessanten Golomb‘schen Zufallskriterien präsentiert. Anschließend wird eine Beschreibung ausgewählter Tests der klassischen Standard-Tests von Donald Knuth sowie der von George Marsaglia entwickelten Stringent- und Monkey-Tests gegeben. Abschließend wird ein universeller Test von Ueli Maurer vorgestellt.

Zufall kann nicht einfach durch zufälliges Aneinanderreihen komplexer Funktionen erzeugt werden. Ein historischer Rückblick auf „naive“ Zufallsgeneratoren in Kapitel 3 soll dem Leser die Notwendigkeit vor Augen führen, dass nur auf solider Mathematik basierende Pseudozufallsgeneratoren zur Erzeugung von kryptographischen Zufallswerten geeignet sind. Beginnend mit Glücksspielen, Glücksrädern und Tabellen werden ältere Generatoren wie die britische Lotto-Maschine ERNIE oder der EUMEL-Generator vorgestellt. Auch die als gescheitert zu betrachtenden Ansätze, aus transzendenten und irrationalen Zahlen Zufallswerte zu extrahieren, werden kurz beleuchtet. Den Abschluss des historischen Rückblicks bilden die ersten arithmetischen Verfahren zur Erzeugung von Pseudozufallszahlen wie die beiden Zufallszahlengeneratoren von Apple und Commodore, die Middle-Square-Methode von John von Neumann sowie der komplexe Super-Random-Number-Generator von Donald Knuth.

Kapitel 4 beschreibt häufig verwendete klassische Pseudozufallsgeneratoren. Zum einen handelt es sich dabei um Generatoren, die rekursiv nach der linearen Kongruenzen-Methode arbeiten. Zum anderen wird auf linear bzw. nicht-linear rückgekoppelte Schieberegister näher eingegangen. Sowohl für Kongruenzgeneratoren wie auch für rückgekoppelte Schieberegister werden kryptoanalytische Angriffe präsentiert und bekannte Schwachpunkte dieser klassischen Generatoren aufgezeigt. Auf diese Art und Weise soll vor dem bedenkenlosen Einsatz dieser für die Kryptographie nur beschränkt geeigneten Generatoren gewarnt werden.

Starke Pseudozufallsgeneratoren werden in Kapitel 5 diskutiert. Diese in diversen Standards (ANSI, FIPS-PUB, ISO) publizierten und eigens für die Kryptographie konzipierten Generatoren verwenden zur Erzeugung von Pseudozufallszahlen Einwegfunktionen, um damit ansonsten einfach vorherzusagende Operationen zu verschleiern. Diese einfachen Operationen reichen vom Hochzählen eines Zählers bis hin zu klassischen Pseudozufallsgeneratoren. Als Einwegfunktionen werden kryptographische Primitive wie kryptographische Hashfunktionen oder Blockchiffren eingesetzt.

Kapitel 6 ist kryptographisch sicheren Pseudozufallsgeneratoren (z. B. Blum-Blum-Shub-, Blum-Micali-, RSA-Generator, etc.) gewidmet. Diese Pseudozufallsgeneratoren wurden speziell für den Einsatz in der Kryptographie entwickelt und ermöglichen die Konstruktion von Kryptosystemen mit höherer Sicherheit. Die Klasse der kryptographisch sicheren Pseudozufallsgeneratoren beruht auf Annahmen der Komplexitätstheorie, d. h. auf der Nicht-Existenz effizienter Algorithmen für wohlbekannte zahlentheoretische Probleme (wie z. B. der Faktorisierung großer Zahlen). Unter diesen Annahmen sind Angreifer nachweislich nicht in der Lage, aus der Kenntnis einiger Zufallswerte zukünftige Zufallszahlen vorherzusagen und auf diese Art und Weise das System anzugreifen.

Betrachtungen über echte Zufallszahlen runden die behandelte Thematik ab. Hochwertige, auf speziellen physikalischen Apparaten und Standard-Hardware basierende Zufallsquellen liefern Bits, die von Angreifern nur schwer zu erraten sind. Neben diesen hochwertigen Zufallsquellen werden auch einige minderwertige Zufallsquellen, die Systempuffer, Netzwerkstatistiken oder den Menschen als Zufallsquelle nutzen, diskutiert. Angreifer können unter Umständen bei diesen Verfahren mit geringem Aufwand die gewonnenen Zufallsbits vorhersagen oder sogar aktiv den Generierungsprozess beeinflussen und manipulieren. Minderwertige Zufallsquellen dürfen daher nicht als alleinige Zufallsquelle, sondern nur in Kombination mit weiteren Zufallsquellen zur Erzeugung von Zufallsbits eingesetzt werden. Da die gelieferten Zufallsbits nur in den seltensten Fällen gleichverteilt und unabhängig sind, bedarf es einer entsprechenden Nachbearbeitung. Dazu werden sogenannte triviale bzw. starke Mischfunktionen eingesetzt. Mit einer Beschreibung der bekanntesten Mischfunktionen endet das Kapitel 7.

Mit den in Kapitel 5 sowie in Kapitel 6 beschriebenen Verfahren ist die kryptotaugliche Pseudozufallsgenerierung mittlerweile einigermaßen in den Griff zu bekommen. Unglücklicherweise leiden diese starken und sicheren Pseudozufallsgeneratoren an ernsthaften Effizienzproblemen. Die nicht gerade triviale Aufgabe der Implementierung eines kryptotauglichen Pseudozufallsgenerators kann auch heute noch getrost als Herausforderung für jeden Entwickler eines Kryptosystems bezeichnet werden. Wer also glaubt, mit einem schnell gebastelten Verfahren oder mit einem möglichst komplexen Algorithmus kryptographisch sichere Pseudozufallszahlen erzeugen zu können, wird fast zwangsläufig Schiffbruch erleiden. Auch vor dem kryptographischen Einsatz der im Kapitel 3 präsentierten historischen Verfahren bzw. den im Kapitel 4 vorgestellten klassischen Pseudozufallsgeneratoren muss an dieser Stelle ausdrücklich gewarnt werden.

Nur gewissenhaft betriebene (Pseudo-)Zufallszahlen-Erzeugung kann die für Kryptosysteme notwendige Sicherheit bieten. Was bringt das sicherste Verschlüsselungsverfahren, wenn die mit einem schwachen Zufallsgenerator erzeugten Schlüssel mit geringem Aufwand kompromittierbar sind? Kryptographische Pseudozufallsgeneratoren müssen daher neben Stromchiffren, Hashfunktionen, Blockchiffren, asymmetrischen Verschlüsselungsverfahren und Signatur-Verfahren als ebenbürtige kryptographische Primitive angesehen werden. Ähnlich wie bei Verschlüsselungsverfahren müssen auch für diesen kryptographischen Basismechanismus mögliche Angriffsszenarien entwickelt, bereits eingesetzte Verfahren in dieser Hinsicht analysiert und neue, gegen die Angriffe immune Verfahren entwickelt werden.

Durch die rasanten Entwicklungen auf dem IT-Markt gibt es einen steigenden Bedarf an kryptographischen Pseudozufallszahlen. Daher werden Hardware- und Software-Hersteller vermutlich in Zukunft verstärkt Tools und Ansatzpunkte für echte Zufallsquellen anbieten. Durch die Möglichkeit der Nutzung echter Zufallszahlen kann die kryptographische Sicherheit von Krypto-Verfahren und Protokollen beträchtlich verbessert werden. Bis jedoch sämtliche Systemarchitekturen standardmäßig mit echten Zufallsgeneratoren ausgestattet sein werden, können für die Gewinnung von Zufallswerten einige im Kapitel 7 beschriebene Verfahren herangezogen werden.

Die komplexe Problemstellung der Erzeugung kryptotauglicher Zufallszahlen konnte auch gegen Ende des 2. Jahrtausends noch nicht zufriedenstellend gelöst werden und stellt daher einen aktuellen und interessanten Forschungsgegenstand dar. Die wissenschaftliche Diskussion muss fortgeführt werden!

Inhaltsverzeichnis:

1.	Einleitung	3
2.	Was ist Zufall?	7
2.1	Eigenschaften von Zufallsfolgen	8
2.2	Turing-Kolmogorov-Chaitin-Komplexität	11
2.3	Quellen für Zufallszahlen	12
2.4	Forderungen an Pseudozufallsgeneratoren	14
3.	Empirisch-statistische Testverfahren	17
3.1	Grundlagen der statistischen Testtheorie	18
3.2	Golombsche Zufallskriterien	24
3.3	Klassische Standard-Tests	26
3.4	Statistische Test nach FIPS PUB 140-1	32
3.5	Stringent- und Monkey Tests	33
3.6	Universal Statistical Test	39
4.	Historische Zufallsgeneratoren	41
4.1	Glücksspiele, Tabellen und physikalische Apparate	41
4.2	Ziffern in transzendenten und irrationalen Zahlen	43
4.3	Arithmetische Verfahren	44
5.	Klassische Pseudozufallsgeneratoren	47
5.1	Lineare Kongruenzgeneratoren	47
5.2	Nicht-lineare Kongruenzgeneratoren	72
5.3	Linear rückgekoppelte Schieberegister	77
5.4	Nicht-linear rückgekoppelte Schieberegister	88
5.5	Feedback with Carry Shift Register	101
6.	Starke Pseudozufallsgeneratoren	103
6.1	Blockchiffre im Counter-Mode	104
6.2	Blockchiffre im Output-Feedback-Mode	105
6.3	Pseudozufallsgeneratoren nach FIPS PUB-112	106
6.4	Pseudozufallsgeneratoren nach FIPS PUB-186	107
6.5	ANSI X9.17 Generator	110
6.6	Pseudozufallsgeneratoren in CryptoLib	112
6.7	BSAFE 3.x Pseudozufallsgenerator	114
7.	Sichere Pseudozufallsgeneratoren	116
7.1	Next-Bit-Vorhersagbarkeit und Unterscheidbarkeit	117
7.2	Existenz kryptographisch sicherer Pseudozufallsgeneratoren	118
7.3	Vertreter kryptographisch sicherer Pseudozufallsgeneratoren	121
8.	Echte Zufallszahlen	131
8.1	Hochwertige Quellen für Zufallsbits	132
8.2	Minderwertige Quellen für Zufallsbits	134
8.3	Bestimmung der Entropie	138
8.4	Triviale und starke Mischfunktionen	139
9.	Ausblick	144
	Abkürzungsverzeichnis	145
	Tabellenverzeichnis	146
	Abbildungsverzeichnis	147
	Literaturverzeichnis	149
	Biographie	164