8.2.8. Kryptographisch sichere Zufallszahlen

Wie wir bereits gesehen haben, werden in der Kryptographie an vielen Stellen Zufallszahlen benötigt. Nun könnte man meinen, daß das auf einem Rechner kein Problem darstellt, denn schließlich bieten die meisten Laufzeitbibliotheken unterschiedliche Funktionen zur Ermittlung von Zufallszahlen an.

Leider taugen diese in der Regel für kryptographische Applikationen, die besonders hohe Forderungen an die Qualität der Generatoren stellen (müssen), überhaupt nicht. Schwächen bei der Erzeugung von Zufallszahlen stellen einen guten Angriffspunkt für die Kryptoanalyse dar und haben vielfach erfolgreiche Attacken auf konkrete Implementierungen von Verfahren und Protokollen ermöglicht.

Es ist natürlich klar, daß die typischen, durch Computer-Programme algorithmisch realisierten Zufallszahlen-Generatoren keine echt zufälligen Folgen liefern können. Donald Knuth (der Vater des Textsatzsystems TeX) zitiert im zweiten Band seines bekannten Buches The Art of Computer Programming, der den Titel Seminumerical Algorithms trägt, John von Neumann mit den Worten:

"Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin."
Mit Hilfe eines Computer-Programms lassen sich allerdings Pseudozufallszahlen-Generatoren (pseudorandom number generators, kurz PRNG) konstruieren. Darunter wollen wir Algorithmen verstehen, deren Ausgabe zufällig aussieht, d.h., statistische Tests sollten keinen Hinweis darauf liefern, daß die Zahlen keiner echt zufälligen Folge entstammen.

So erwarten wir z.B. eine Gleichverteilung, d.h., alle Zahlen sollten ungefähr gleich oft vorkommen. Außerdem sollte die Periode (d.h. die Anzahl der Werte, nach denen sich die gesamte Ausgabe wiederholt) so groß sein, daß die tatsächlich verwendete Teilfolge keinen periodischen Charakter trägt. Genauere Informationen zu verschiedenen in der Praxis üblichen Tests der Qualität von PRNGs finden sich z.B. bei Menezes.

Für kryptographisch sichere Pseudozufallszahlen-Generatoren gilt eine zusätzliche Forderung: Es darf rechnerisch nicht möglich sein, die nächste Zahl vorherzusagen, obwohl man den Algorithmus und alle zuvor erzeugten Zahlen kennt. Die Sicherheit beruht auf der Geheimhaltung des Schlüssels, von dem die jeweils generierte Folge eindeutig abhängt, da er den Anfangszustand des Generators bestimmt. Dadurch lassen sich die Ausgaben, im Gegensatz zu echten Zufallsfolgen, immer wieder reproduzieren.

Kryptographisch sichere PRNGs sind wie andere kryptographische Verfahren auch Gegenstand kryptoanalytischer Attacken und können daher ebenfalls gebrochen werden. Deshalb ist es sehr wichtig, sie gegen Angriffe resistent zu machen.

Wir wollen nachfolgend einige konkrete Realisierungen von kryptographisch sicheren PRNGs kurz vorstellen, die z.T. schon an anderer Stelle angesprochen worden sind.

Zyklische Verschlüsselung

Um z.B. zufällige Sitzungsschlüssel Xi aus einem Master Key Km abzuleiten, kann man einen Zähler verwenden und dessen Inhalt wiederholt durch eine Chiffre verschlüsseln. Das in jedem Schritt entstehende Chiffrat stellt einen pseudozufälligen Schlüssel dar. Sobald er generiert wurde, erhöht man den Zähler um 1, so daß jede Ausgabe von einer anderen Zahl abhängt. Wenn man den Master Key geheimhält, kann man den nächsten Schlüssel der Folge nicht rechnerisch vorhersagen.

Statt des einfachen Zählers könnte man auch die Ausgabe eines anderen guten Zufallszahlen-Generators als Eingabe verwenden.

Blockchiffre im OFB

Betreibt man eine Blockchiffre (DES, IDEA, ...) im Output Feedback Mode, so stellen die pro Verschlüsselungsschritt erzeugten Chiffrate Pseudozufallszahlen dar. Die gesamte Folge wird eindeutig durch den Key sowie den IV bestimmt. Kennt man den Schlüssel nicht, so läßt sich auch das nächste Element der Folge nicht vorausberechnen.

ANSI X9.17

Einen der kryptographisch stärksten PRNG spezifiziert der ANSI-Standard X9.17. Die dort beschriebene Technik wird von vielen Applikationen genutzt, z.B. beim kryptographischen Schutz von Finanztransaktionen oder (in modifizierter Form) auch bei PGP 2.x.

X9.17 nutzt Triple DES als Blockchiffre. Folgende Elemente spielen eine Rolle:

Der Aufbau des Generators läßt sich so veranschaulichen:

Die verwendeten Symbole haben folgende Bedeutung:

DTi Wert für Datum und Uhrzeit zu Beginn des i-ten Schrittes
Vi Seed zu Beginn des i-ten Schrittes
Ri die im i-ten Schritt erzeugte Pseudozufallszahl
K1, K2 die für alle Schritte gemeinsam genutzten 2 DES-Keys
Die Entstehung der Ergebnisse können wir formal so beschreiben:
Ri = EDEK1, K2 [ EDEK1, K2 (DTi)  XOR  Vi ]

Vi+1 = EDEK1, K2 [ EDEK1, K2 (DTi)  XOR  Ri ]

PGP 2.x

PGP 2.x nutzt ein sehr komplexes und mächtiges Schema zur Erzeugung echter Zufallszahlen sowie Pseudozufallszahlen. Die echten Zufallszahlen dienen folgenden Zwecken:

Pseudozufallszahlen werden bei

verwendet.

Anmerkung zu CFB: Bei PGP 2.x wird zur symmetrischen Verschlüsselung nicht der CBC, sondern der 64-bit Cipher Feedback Mode von IDEA eingesetzt.

PGP 2.x verwaltet einen Puffer von echt zufälligen Bits. Als zufälliger Input dienen die Tastatureingaben der Nutzer, wobei sowohl die eingegebenen 8-Bit-Werte als auch die Zeitabstände zwischen den Tastenanschlägen ausgewertet werden. Der zur Erzeugung der Pseudozufallszahlen verwendete Algorithmus basiert auf ANSI X9.17, wobei allerdings IDEA statt Triple DES als Blockchiffre zum Einsatz kommt.

Nutzung von Einweg-Hashfunktionen

Wie wir bereits bei der Diskussion der Hashfunktionen erwähnt hatten, eignen sich Einweg-Hashfunktionen, die zufällig aussehende Hashwerte erzeugen, ebenfalls als Basis für die Generierung von Zufallszahlen. So findet sich im Digital Signature Standard (DSS) eine Beschreibung zur Konstruktion eines Zufallszahlen-Generators unter Verwendung des Secure Hash Algorithm SHA-1. Die Details können in den entsprechenden FIPS-Publikationen nachgelesen werden.

© Holger Trapp, 13.10.1998