Hochwertige Zufallszahlen sind schwieriger zu erzeugen, als man denkt. Dieser Artikel verrät, wie Linux virtuell würfelt und damit eine hohe Qualität der generierten Zahlenfolgen sicherstellt. Einige Bereiche lassen aber noch Raum für Verbesserungen.

Nicht nur Computerspiele, in denen Monster sich zufällig bewegen, sondern vor allem Programme mit kryptographischen Funktionen benötigen Zufallszahlen. Während sich Games auch mit Pseudo-Zufallszahlen zufrieden geben, die ein Mathematiker knacken könnte, benötigen Programme und Protokolle wie SSL/TLS, SSH, IPsec oder PGP hochwertige Zufallszahlensequenzen, die weder berechenbar noch leicht zu erraten sind. Der Betriebssystemkern hat es sich zur Aufgabe gemacht, solche echten Zufallszahlen zu generieren.

Zufall aus Rauschen

Ähnlich den Physikern, die ihre Zufallszahlen aus dem Rauschen einer Strahlungsquelle oder elektronischer Bauelemente erzeugen, nutzt Linux ebenfalls ein Rauschen, das so genannte Umgebungsrauschen. Genauer: Linux berücksichtigt den zeitlichen Abstand zwischen Anforderungen unterschiedlicher Peripheriegeräte.

Zum Beispiel misst der Kernel den zeitlichen Abstand zwischen zwei Tastenanschlägen oder zwischen zwei Interrupts, die von der Festplatte ausgelöst werden. Da sich kaum vorhersagen lässt, wann ein Benutzer die nächste Taste auf dem Keyboard anschlägt oder die Festplatte den nächsten Interrupt auslöst, handelt es sich um zufällige Zeitpunkte, die Linux in einen Zufallszahlenpool einspeist. Timer-Interrupts berücksichtigt es dagegen nicht, da sie im ungefähr gleichen zeitlichen Abstand auftreten und damit vorhersagbar sind.

Hilfe durch Anwendungen

Wer einen Gerätetreiber schreibt, kann beim Reservieren des Interrupts durch Setzen des Flag »SA_SAMPLE_RANDOM« dem Kernel anzeigen, dass die Geräte-Interrupts zufällig auftreten und er sie deshalb beim Erzeugen von Zufallszahlen berücksichtigen kann. Zufällig heißt in diesem Zusammenhang, dass der Wert weder vorhersagbar noch der Auftrittszeitpunkt beobachtbar ist. Je mehr gute, unkorrelierte Zufallsquellen zusammenkommen, desto besser. Applikationsprogrammierer können mit Schreibzugriffen auf die Gerätedatei »/dev/urandom« Daten zur Erzeugung guter Zufallszahlen beisteuern.

Der Kernel übernimmt dabei nicht jeden mutmaßlichen Zufallswert blind. Er merkt sich die Differenz zum letzten (»delta«) und vorletzten Wert (»delta2«) und überprüft, ob die Werte ausreichend unterschiedlich sind. Regelmäßige Tastenanschläge tragen kaum zur Generierung von Zufallszahlen bei.

Zwar mischt der Kernel jeden noch so schlechten Wert in seinen Input Pool, stellt aber mit der Entropie eine Maßzahl bereit, die die Zufallsqualität und damit den Zustand des Speichers ausdrückt. Ein 32-Bit-Wert kann maximal 12 Bit Entropie liefern, 1 Byte liefert also 3 Bit Entropie. Das Kommando »cat /proc/sys/kernel/random/entropy_avail« gibt die Entropie des Input Pool aus (siehe Tabelle 1). Der Superuser kann per IO-Control diesen Entropiewert sogar manipulieren (siehe Tabelle 2).

Besser mischen

Da einzelne Zeitdifferenzen zum Teil nicht so zufällig sind wie erwünscht, legt der Kernel sie nicht einfach nacheinander im Speicher ab. Vielmehr verrechnet er jeden neuen Zufallswert über die so genannte Mixing Function mit einigen im Input Pool bereits vorhandenen Daten (siehe auch [1]). Im ungünstigen Fall (der neue Wert ist nicht wirklich zufällig) werden damit bereits vorhandene Zufallswerte nicht noch zufälliger.

Zur Verrechnung dienen Bit-Schiebereien und XOR-Verknüpfungen, die einen kryptologischen Angriff verhindern sollen. Der Input Pool ist übrigens 128 Wörter à 4 Bytes (also 512 Bytes beziehungsweise 4096 Bits) groß. Den schematischen Aufbau des Zufallszahlengenerators zeigt Abbildung 1.

Abbildung 1: Möglichst viele unkorrelierte Input-Quellen liefern Zufallswerte, die eine Mixing Function in den so genannten Input Pool mischt. Liest eine Applikation über »/dev/random« oder »/dev/urandom« eine Zufallszahl, vermischt der Kernel gehashte Daten aus dem Input Pool mit den Daten im sekundären Pool und liefert sie mit einem Hash zurück. Der sekundäre Pool teilt sich wiederum in Nonblocking und Blocking Pool.

Für den Zugriff auf die Zufallszahlen stellt der Kernel zwei Gerätedateien zur Verfügung. Über »/dev/random« und »/dev/urandom« lesen Applikationen Zufallszahlen aus. Damit die Applikationen aus den gelesenen Daten keine Rückschlüsse auf den Inhalt des Input Pool ziehen können, ergreift der Kernel eine Reihe von Maßnahmen:

• Er bildet über jeweils 512 Bit des Input Pool einen
  SHA-1-Hash (siehe Kasten “SHA-1”) mit 5 Wörtern
  à 4 Byte (=160 Bit). Mit jeweils einem dieser Wörter
  modifiziert er den Input Pool. Nach einer weiteren Änderung
  des Input Pool kopiert er 16 Wörter (512 Bit) an Daten in
  einen Zwischenspeicher. Der Zugriff auf den Input Pool führt
  also zu einer Veränderung der Daten im Input Pool. Von den
  Daten im Zwischenspeicher bildet der Zufallszahlengenerator den
  SHA-1-Hash, den er an einen so genannten Sekundärspeicher
  weiterreicht.
• Den SHA-1-Hash vermischt der Kernel mit den Daten des
  Sekundärspeichers, also des Blocking und des Nonblocking
  Pool.
• Über jeweils 512 Bits des Secondary Pool bildet der Kernel
  einen SHA-1-Hash. Mit jeweils einem der fünf Wörter des
  Hash modifiziert er den Secondary Pool (Abbildung 2, a und b). Nach
  einer weiteren Modifikation des Pool kopiert er 512 Bit an Daten in
  einen Zwischenspeicher (Abbildung 2, c). Somit wird mit jedem
  Lesezugriff auch der Secondary Pool für einen Angreifer nicht
  nachvollziehbar modifiziert. Von den Daten im Zwischenspeicher
  errechnet der Kernel wieder einen SHA-1-Hash (Abbildung 2, d).
  Dessen Bytes verknüpft der Zufallszahlengenerator dann noch
  Byte-weise über XOR mit sich selbst.
• Den Hash kopiert er als Zufallswert in den Speicherbereich der
  aufrufenden Instanz.
• Variablen, die Zwischenwerte aufgenommen haben, setzt der
  Kernel explizit auf 0.

Abbildung 2: Auch der Secondary Pool wird mehrfach durchmischt, wenn eine Applikation oder der Kernel Zufallszahlen auslesen. Kritiker finden, dass diese Methode die Qualität der Zufallszahlen nicht verbessert.

Für jedes Byte, das der Kernel vom primären in den sekundären Pool überführt, erniedrigt sich die Entropie des Input Pool um 8 (1 Byte = 8 Bits). Ebenso sinkt die Entropie des sekundären Pools um die Anzahl der Bits, die dort tatsächlich entnommen werden. Zur Sicherheit speist Linux für jedes entnommene Zufallsbyte (bei der Entnahme gehen 8 Bit Entropie verloren) 3 echte Zufallsbytes (mit jeweils 3 Bit Entropie) in seinen Input Pool (siehe Abbildung 4).

Mehr Entropie

Abbildung 1 zeigt, dass Linux zwei sekundäre Pools implementiert, den Blocking Pool und den Nonblocking Pool. Der Blocking Pool ist der Gerätedatei »/dev/random« zugeordnet. Wie sein Name bereits vermuten lässt, können diesem Pool nicht mehr Zufallsbits entnommen werden, als Entropie im Speicher vorhanden ist.

Ist die Entropie aufgebraucht, schläft eine zugreifende Applikation, bis wieder genug Lese-Entropie (Proc-Datei »/proc/sys/kernel/random/read_wakeup_threshold«) vorhanden ist. Der Screenshot in Abbildung 3 zeigt dieses Verhalten: Vor dem Aufruf des Kommandos »hexdump /dev/random« ist mit 3585 Bit genügend Entropie im Input Pool vorhanden. Gut 400 Zufallswerte gibt das Kommando direkt nach dem Aufruf aus, danach blockiert sie. Unterbricht der Programmierer nach 18 Sekunden das Hexdump-Kommando mit [Strg]+[C] und liest die Entropie erneut aus, zeigt sich: Sie ist auf 87 gesunken. Zwischen unterschiedlichen Systemen variieren diese Werte natürlich, abhängig davon, in welchem Ausmaß Zufallswerte erzeugt und verbraucht werden.

Der Nonblocking Pool ist der Gerätedatei »/dev/urandom« zugeordnet. Über diesen Pool erzeugt der Kernel per SHA-1-Hash beliebig viele Zufallszahlen, selbst dann, wenn die gesamte Entropie bereits aufgebraucht ist. Auch wenn Kryptographen die auf diese Weise generierten Zufallszahlen nicht unbedingt als stark bezeichnen, reichen sie für die meisten Applikationen aus. Ein Angreifer müsste nämlich aus dem Hash den initialen Zustand des Pools herleiten können, was nach dem heutigem Stand der Forschung nicht möglich ist.

Über den Nonblocking Pool greifen typischerweise auch In-Kernel-User zu. Für diese exportiert der Zufallszahlengenerator die Funktion »get_random_bytes(void *buf, int nbytes)«. Die Funktion extrahiert »nbytes« Zufallzahlen und legt sie an der Adresse »buf« im Speicher ab. TCP nutzt beispielsweise diese Funktion für die initialen Sequenznummern.

Abbildung 3: Ansatzpunkt für eine Denial-of-Service-Attacke: Bei ungenügender Entropie im Zufallszahlenspeicher blockieren jene Applikationen, die von »/dev/random« lesen. Die Vergabe geeigneter Zugriffsrechte minimiert diese Gefahr.

Abbildung 4: Die Entropiebilanz zeigt, dass Linux auf Nummer Sicher geht: Jeder echte Zufallswert mit 8 Bit liefert maximal 3 Bit Entropie. Jedes entnommene Zufallsbyte schlägt jedoch mit 8 Bit zu Buche.

Schwelle fürs Schlafen

Mit einem Schreibzugriff auf die Gerätedatei »/dev/urandom« fügen Applikationsprogrammierer Daten dem Input Pool hinzu. Allerdings wird die Entropie dabei nicht aktualisiert. Die Gerätedateien »/dev/random« und »/dev/urandom« unterstützen auch die Funktion »select()«. Eine Applikation kann sich also so lange schlafen legen, bis der Entropiewert des Input Pool unterhalb von »write_wakeup_threshold« (128 Bit) fällt. Dann wird die Applikation aufgeweckt, um den Pool mit ausreichend neuen Zufallsdaten zu füllen.

Ein Schreibzugriff auf die Gerätedatei »/dev/urandom« initialisiert den Zufallszahlengenerator. Da typischerweise gerade beim Hochfahren des Rechners die Abläufe vorhersagbar sind, könnte ein Angreifer mit etwas Glück den Zustand des Zufallszahlengenerators direkt nach dem Hochfahren prädizieren. Wenn aber der Zahlenspeicher noch vor dem ersten Zugriff mit echten Zufallswerten gefüllt wird, hat ein Angreifer, der diese Werte nicht kennt, keine Chance. Daher speichern moderne Linux-Systeme beim Herunterfahren einige Zufallswerte in einer Datei und kopieren sie beim Hochfahren zurück in den Input Pool.

Direkt nach dem Kopieren überschreibt das System die in der Datei gespeicherten Zufallszahlen mit neuen Werten. Wird der Rechner nämlich nicht ordentlich heruntergefahren, sondern einfach ausgeschaltet, verhindert diese Maßnahme, dass Linux den Input Pool mit immer den gleichen Werten initialisiert. Das zugehörige Skript heißt »/etc/init.d/urandom«.

Keine Panik

Die Kernelentwickler haben eine ganze Reihe von Maßnahmen ergriffen, um echte Zufallszahlen zu generieren. Dennoch ist ihre Implementierung nicht frei von Kritik. Im Mai dieses Jahres veröffentlichten drei Autoren aus Israel eine Analyse der rund 2500 Codezeilen und kritisierten darin vor allem die Qualität des Code: Er sei unübersichtlich und zudem weitgehend undokumentiert, so lautet ihr Fazit.

Doch ihre Kritik zielt auch auf die Implementation selbst. Die wiederholte Anwendung von SHA-1 erhöhe nur die Komplexität, nicht aber die Sicherheit. Der blockierende Zugriff über »/dev/random« erlaube zudem eine Denial-of-Service-Attacke. Denn sobald ein Angreifer dem System ausreichend Entropie (durch eigene Zugriffe auf die Gerätedatei) entzieht, blockiert eine zweite Applikation unter Umständen lebenslang.

Dass die (Lese-)Modifikationen am Input, Blocking und Nonblocking Pool durch Rückführung einzelner SHA-1-Wörter geschehen, bevor die Zufallszahl generiert wird, ermöglicht einen Vorwärtsangriff. Ist nämlich der Zustand des Pools bekannt, lässt sich damit die daraus generierte Zufallszahl ableiten. Würden erst die Daten dem Pool entnommen und danach die (Lese-)Modifikation stattfinden, wäre es nicht möglich, aus dem Poolzustand die letzte Zufallszahl abzuleiten.

Die Angriffsgefahr ist zwar nachvollziehbar, für die Kernelhacker selbst aber nur theoretisch. Der nicht blockierende Zugriff über »/dev/urandom« ist vor einem Denial-of-Service-Angriff gefeit und liefert ausreichend echte Zufallszahlen. Und wenn der Zustand des Input Pool bekannt ist, ist es ohnehin zu spät. Der Hacker ist schon im System.

Mehr Zufall durch Hardware

Übrigens: Wem die Qualität des Linux-Zufallszahlengenerators wider Erwarten nicht ausreicht, dem sei die Bastelanleitung aus [4] empfohlen. Alles was er dazu braucht, sind eine Webcam, ein Rauchmelder und ein wenig Geschick im Umgang mit Strahlungsquellen. Viel Spaß beim Bauen. (ofr)