Kryptografische Zufallsgeneratoren

Kryptografische Zufallsgeneratoren bzw. Zufallszahlengeneratoren spielen eine wichtige Rolle in der Kryptografie. Jedes Verschlüsselungsverfahren benötigt Zufallszahlen zum Erzeugen von digitalen Schlüsseln.
Ein Zufallsgenerator ist ein Verfahren das eine Zufallsfolge als Ergebnis liefert. Unter einer Zufallsfolge versteht man eine Bitfolge von Nullen und Einsen deren Reihenfolge zufällig und nicht vorhersagbar ist. Eine Zufallszahl ist ein Ausschnitt aus einer Zufallsfolge mit begrenzter Länge.

Zufallszahlengeneratoren sind ein oft unterschätzter Bereich in der Kryptografie. Dabei kann ein Angreifer das sicherste Verschlüsselungsverfahren knacken, wenn er die Zufallszahl bei der Schlüsselgenerierung kennt oder sogar beeinflussen kann.
Mit der Qualität bzw. dem Grad der Zufälligkeit eines solchen Schlüssels steht und fällt jede Verschlüsselung.

Zufall (Entropie)

Zufall bzw. Entropie ist in gewisser Weise ein Ereignis in der Gegenwart, dessen Ergebnis in der Vergangenheit nicht bestimmt oder vorausgesagt werden konnte. Doch Zufall ist in Computern, wie wir sie heute kennen, eigentlich nicht vorgesehen. Hier arbeiten logische Funktionen, deren Ergebnisse jederzeit vorherbestimmt und nachvollzogen werden können. Und das ist auch richtig so. Denn Computer sind dafür ausgelegt, dass bei immer der gleichen Eingabe immer die gleiche Ausgabe erfolgt. Addiert ein Computer die Zahlen 1 und 1, dann soll immer 2 herauskommen. Das ist die Bedingung, warum Computer sich durchgesetzt haben. Sie tun immer die gleichen Dinge auf die gleiche Weise.
Das ist aber dann ein Problem, wenn das Ergebnis "Zufall" sein soll. Also eine Funktion soll nicht immer das gleiche Ergebnis ausgeben, sondern jedes Mal etwas anderes. Doch wo soll dieser "Zufall" herkommen, in einem System, dass immer das gleiche tut und nichts dem Zufall überlassen ist?
In der Praxis begnügt man sich mit der Definition, dass "der Zufall statistisch möglichst gut verteilt und nicht vorhersehbar sein soll". Die Zufälligkeit einer ausgegebenen Zufallsfolge muss mit mathematischen Mitteln nachweisbar sein.

Wo kommt der Zufall her?

Ein echter Zufallsgenerator bedingt einen physikalischen Vorgang, der nicht reproduzierbar ist. Am besten eignet sich dafür ein separates Hardware-Modul, dass Zufallszahlen aus Messwerten generiert. Hier eignen sich insbesondere Spannungsschwankungen an Widerständen und Halbleiterbauelementen. Wegen Exemplarstreuung bei diesen Bauteilen und komplexen physikalischen Bedingungen ist davon auszugehen, dass die Messwerte immer anders ausfallen und nicht nachträglich erzeugt werden können. Genau darum geht es. Solche Hardware-Module gehören allerdings nicht zur Standardausstattung eines Computers.
Eine weitere gute Quelle für Zufall sind Zeitdifferenzen zwischen Ereignissen innerhalb eines Computers, die aus mechanisch generierten Informationen herrühren und sich ohne Hardware-Modul bestimmen lassen.

• physikalisches Rauschen in Bauelementen
• Timing zwischen Netzwerkpaketen
• Rotationslatenz von Festplatten
• Timing von Maus- und Tastatureingaben

Zeitdifferenzen sind nicht vorhersagbar. Beispielsweise die Zeit zwischen Laufwerkszugriffen, Mausbewegungen und Tastatureingaben. Wenn man mehrere davon miteinander kombiniert, dann kann man das Ergebnis als zufällig ansehen und gleichzeitig fast unmöglich vorhersagen oder nachbilden.

Was so einfach klingt ist in der Praxis manchmal schwer oder unmöglich umzusetzen. Beispielsweise in Smartcards. Hier gibt es keine Eingabegeräte oder Festplatten. Auch auf Smartphones ist der Zufall nur eingeschränkt zufällig. Diese Geräte sind besonders dann anfällig, wenn ein Angreifer die verbliebenen Mechanismen der Zufallsgenerierung manipulieren und somit den Zufall vorhersagen kann.
In der Praxis ist das ein echtes Problem, weil es auch neu gestartete Rechner, im speziellen Server, betrifft. Wird ein Gerät hochgefahren und die Krypto-Dienste gestartet, dann wollen die natürlich Zufall für temporäre Schlüssel haben. Bei einem PC ist das nicht so das Problem, weil hier der Nutzer zeitnah für Benutzereingaben durch Maus- und Tastatur sorgt. Auf einem Server, der keine Festplatte hat (weil SSD oder Network Storage) und wo keine Maus- und Tastatur-Eingaben erfolgen, ist das Material für den Zufall nur in geringem Umfang verfügbar. Da ist nicht viel, aus was man Zufall generieren kann.

Pseudozufallsgenerator

Jedes Betriebssystem und jede Programmiersprache stellt Funktionen für die Generierung von Zufallszahlen bereit. Doch diese Zufallsfunktionen sind für die Kryptografie nicht gut genug. Beispielsweise dann, wenn sie rein in Software implementiert sind. Die meisten dieser Zufallsgeneratoren liefern Ergebnisse, die sich von einem Angreifer erraten lassen. Deshalb sind alle Zufallsgeneratoren, die ohne physikalische Messung auskommen, Pseudozufallsgeneratoren.

Ein Pseudozufallsgenerator ist ein Verfahren, das einen Startwert, auch Seed genannt, zu einer beliebig langen Zufallsfolge verarbeitet. Dabei wird eine Fortschaltfunktion auf den Startwert beliebig oft angewendet.
Prinzipiell liefern Pseudozufallsgeneratoren nur nachvollziehbare Zufallsfolgen. Außerdem liefern sie bei immer dem gleichen Startwert den gleichen Zufallswert. Das bedeutet, dass ein Pseudozufallsgenerator ohne einen echten zufälligen Startwert wenig wert ist.
Wird ein solcher Pseudozufallsgenerator in der Kryptografie verwendet, dann hat das Konsequenzen auf die Sicherheit. Wenn ein Angreifer eine Zufallsfolge und die Fortschaltfunktion kennt, dann kann er alle Zufallszahlen erzeugen. Aus diesem Grund gibt ein Zufallszahlengenerator die Zufallszahl nur zum Teil oder als Hash-Wert aus. Eine andere Möglichkeit ist, eine schlüsselabhängige Fortschaltfunktion zu verwenden.

Damit eine Zufallszahl in der Kryptografie verwendet werden darf, muss dafür gesorgt sein, dass der Startwert von einem Angreifer nicht erraten und auch nicht manipuliert werden kann. Dem Angreifer bleibt dann nur noch die Kenntnis über die Fortschaltfunktion.
Grundsätzlich liefert ein Pseudozufallsgenerator immer vorhersagbare Ergebnisse. Nur dann, wenn der Startwert nicht bekannt ist, dann ist das Ergebnis nicht vorhersagbar.

Bei manchen Zufallsgeneratoren liegt der Ausgabewert zwischen Zufall und Pseudozufall. Beispielsweise wenn die Funktion Speicherbereiche des Hauptspeichers heranzieht, die sich häufig ändern. Das Problem dabei ist, dass wenn dieser Teil des Hauptspeichers von Software beeinflusst wird, dann ist das eher Pseudozufall. Anders sieht es aus, wenn der Speicherbereich unmittelbar von Hardware beeinflusst wird.

Primzahlengenerator

Wenn man nach dem RSA-Verfahren zwei Primzahlen benötigt, dann greift man auf einen Primzahlengenerator zurück. Damit ein Angreifer die Zahlen nicht erraten kann, nimmt man große Primzahlen. Beispielsweise mit einer Länge von 512 Bit, deren Anzahl natürlich begrenzt ist. Davon gibt es allerdings 10⁵⁰. Bei 1.024 Bit wären es sogar 10¹⁰⁰. Es ist somit ausgeschlossen, dass ein Angreifer die zufällig gewählte Primzahl errät.
Die Funktionsweise eines Primzahlengenerators ist recht einfach. Es wird einfach eine Zufallszahl generiert und danach geprüft, ob es sich um eine Primzahl handelt. Falls nicht, wird eine neue Zufallszahl generiert und erneut geprüft. Das wird so lange wiederholt, bis eine Primzahl gefunden wurde.
Der Algorithmus, der die Zahl prüft darf natürlich nicht unendlich lange brauchen. Aus diesem Grund arbeitet man mit einem Algorithmus, der im Ausnahmefall eine normale Zahl als Primzahl erkennt. Das ist kein Problem, weil das RSA-Verfahren auch mit normalen Zahlen funktioniert, nur dann nicht mehr so ganz sicher ist. Für einen Angreifer wäre das ein gefundenes Fressen. Doch er müsste ebenfalls erst einmal feststellen, dass es keine Primzahl ist. Je nach Situation und Angriff ist der Aufwand dafür zu groß.
Das bedeutendste Verfahren zur Generierung von Primzahlen ist das Miller-Rabin-Verfahren. Es ist leicht zu implementieren und die Gefahr, dass eine falsche Primzahl herauskommt ist gering.

Ein guter Zufallsgenerator

Um sicher zu sein, dass der Zufallswert möglichst zufällig ist, zieht man mehrere Zufallsquellen heran. Je mehr desto besser, desto geringer die Wahrscheinlichkeit, dass ein Angreifer den Zufall erraten kann. Wenn ein Angreifer es doch versucht, dann muss er er den gesamten Zufallspool erraten oder manipulieren.
Das Mischen der Zufallsquellen erfolgt am besten mit einer kryptografischen Hash-Funktion. Der Ausgabewert kann dann aus dem Hash-Wert gebildet werden.

Der Zeitpunkt an dem der Zufallszahlengenerator initialisiert wird ist wichtig. Bei einem normalen PC kann das schon recht früh im Bootprozess erfolgen. Anders sieht es bei Embedded-Hardware, zum Beispiel Router, aus. Hier ist der Zufall schwieriger herzustellen. Hier braucht es einfach länger, bis genug Zufall bereitsteht.

Eine guter Zufallsgenerator zieht den Zufall immer aus mehreren Quellen. Es könnte ja sein, dass eine der Quellen nicht genug Zufall ausgibt. Beispielsweise weil sie manipuliert wurde.

Zufälligerweise sind Zufallsgeneratoren gar nicht so zufällig

Immer wieder gibt es Meldungen über fehlerhafte Implementierungen von Zufallsgeneratoren. Die Folge ist oft keine ausreichende Entropie beispielsweise bei der Schlüsselgenerierung.
In einem Betriebssystem wie Linux gibt es die Funktion "/dev/random" in die ein Programm Daten in Form von selber generiertem Zufall reinschreiben kann. Das macht Sinn, wenn man den Einfluss einer Manipulation von außen begrenzen möchte. In Windows-Betriebssystemen gibt es eine ähnliche Funktion, der man aber keine Daten übergeben kann. Ein Programmierer hat also keinen Einfluss darauf, wie zufällig der Zufall ist, der dabei herauskommt.
In einem anderen Fall hatte man eine Idee, um der Problematik des eingeschränkten Zufalls bei frisch gestarteten Systemen zu begegnen. Beim Herunterfahren soll Zufall erzeugt und gespeichert werden, um es beim Neustart zu nutzen. Das ist natürlich keine gute Idee, weil ein Angreifer auf diesen Zufall Zugriff hat und ebenfalls nutzen kann. In so einem Fall wäre der erzeugte Schlüssel leicht ermittelbar.

Durch die Veröffentlichungen durch Edward Snowden Mitte 2013 wurde bekannt, dass die NSA Hintertüren in Zufallsgeneratoren einbauen lässt. In einem Fall konnte der Zufallsgenerator nur 256 verschiedene Zufallszahlen erzeugen, wodurch die NSA in der Lage war zufallsgenerierte Schlüssel zu rekonstruieren.
Der Fehler konnte nur durch Quelloffenheit und der nie nachlassenden Aufmerksamkeit von Millionen Augen gefunden und korrigiert werden.
Normale Anwender haben keine Chance zu prüfen, wie gut eine bestimmte Implementierung arbeitet, um einen schlechten Zufallszahlengenerator zu erkennen. Sie müssen ihrer Software vertrauen.

Übersicht: Pseudozufallsgeneratoren

Im Vergleich zu anderen kryptografischen Verfahren gibt es bei Zufallsgeneratoren sehr viele unterschiedliche Verfahren, von denen allerdings nur die wenigsten standardisiert sind. Das ist auch verständlich. Bei Zufallsgeneratoren ist keine Interoperabilität nötig.
Manch guter Pseudozufallsgenerator findet sich in den Veröffentlichungen von Standardisierungsorganisationen, was aber keiner Standardisierung entspricht. Das ist auch nicht nötig, denn wenn die Implementierung jedes Mal anders aussieht, dann muss auch ein Angreifer sich immer wieder aufs Neue damit befassen und kann keine fertige Bibliothek verwenden. Das schlimmste was bei einer Implementierung passieren kann ist, dass der Ausgabewert doch nicht ganz so zufällig ist. Von daher schadet es nicht, wenn Programmierer auf gute Bibliotheken zurückgreifen.
Pseudozufallsgeneratoren basieren meist auf anderen kryptografischen Verfahren, wie zum Beispiel Hash-Funktionen oder Verschlüsselungsverfahren.

• Kryptografische Hash-Funktionen
• Schlüsselabhängige Hash-Funktionen
• Blockchiffren
• Rückgekoppelte Schieberegister

Weitere verwandte Themen:

• Kryptografische Hash-Funktionen
• SHA - Secure Hash Algorithm (SHA-1 / SHA-2 / SHA-3)
• Kryptografie
• Verschlüsselung
• Digitale Schlüssel (Verschlüsselung)

Netzwerktechnik-Fibel

Alles was Sie über Netzwerke wissen müssen.

Die Netzwerktechnik-Fibel ist ein Buch über die Grundlagen der Netzwerktechnik, Übertragungstechnik, TCP/IP, Dienste, Anwendungen und Netzwerk-Sicherheit.

Das will ich haben!

Artikel-Sammlungen zum Thema Netzwerktechnik

Collection: Netzwerk-Sicherheit

Was du über Netzwerk-Sicherheit wissen solltest.

eBook kaufen

Collection: Netzwerk-Grundlagen

Was du über Netzwerk-Grundlagen wissen solltest.

eBook herunterladen

Collection: IPv6

Was du über IPv6 wissen solltest.

eBook kaufen

Schützen Sie Ihr Netzwerk

Die TrutzBox enthält einen leistungsstarken Content-Filter, der Werbetracker blockiert und vor Schadcode auf bösartigen Webseiten schützt.
Alle Internet-fähigen Geräte, egal ob Desktop-PCs, vernetzte Produktionsanlagen und IoT-Geräte, werden vor Überwachung durch Tracker, Einschleusen von Schadsoftware und dem unbedachten Zugriff auf bösartige Webseiten geschützt.

• Sicheres Surfen mit Content-Filter und Blocker gegen Werbetracker
• Mehrstufige Sicherheitsarchitektur mit Stateful-Inspection-Firewall und Intrusion-Prevention-System
• Laufende Aktualisierung gegen neue Bedrohungen

Bestellen Sie Ihre TrutzBox mit integriertem Videokonferenz-Server jetzt mit dem Gutschein-Code "elko50" und sparen Sie dabei 50 Euro.

Mehr über die TrutzBox TrutzBox jetzt mit Gutschein-Code bestellen