Tohuwabohu

Generell geht es in der EDV eher geordnet zu. Will man einem Computer das Würfeln beibringen, muss man mitunter erheblichen Aufwand treiben – vor allem, wenn er ehrlich spielen soll.

In Pocket speichern vorlesen Druckansicht 7 Kommentare lesen
Lesezeit: 4 Min.
Von
  • Michael Riepe

Normalerweise sollen Berechnungen immer dasselbe (korrekte) Ergebnis liefern. Eine Reihe von Algorithmen basiert jedoch auf Zufall, etwa Monte-Carlo-Simulationen und genetische Algorithmen im wissenschaftlichen Umfeld, das Erzeugen von Schlüsseln in der Kryptografie oder das Testen von Software mit der Fuzzing-Methode.

Sie stellen unterschiedliche Anforderungen an die verwendeten Zufallszahlen. Kryptografische Schlüssel müssen unvorhersehbar sein und dürfen keine Redundanz aufweisen: Kann ein Angreifer den Schlüssel oder Teile davon erraten, ist die Verschlüsselung nicht sicher. Wissenschaftliche Algorithmen hingegen benötigen Zahlenfolgen, deren Elemente eine bestimmte – meist gleichmäßige – Verteilung besitzen.

Pseudo-Zufallsgeneratoren wie rand() liefern Zahlenfolgen, die einfachen Ansprüchen genügen. Als kryptografische Schlüssel sind sie jedoch völlig ungeeignet, da die Zahlen einem Schema folgen und sich nach einer Weile wiederholen. Modernere PRNGs (pseudo-random number generators) liefern längere Folgen ohne Wiederholungen oder decken einen größeren Zahlenraum ab, was vor allem wissenschaftlichen Anwendungen zugute kommt.

Unvorhersehbare Zahlenfolgen liefern Hardware-Generatoren, die zum Beispiel physikalische Effekte wie das Rauschen eines Transistors als Quelle nutzen. Sie sind allerdings nicht in allen Rechnern zu finden. Als Alternative bietet es sich an, unregelmäßig stattfindende externe Ereignisse zu nutzen, etwa die von Maus und Tastatur erzeugten Interrupts. Linux und einige Unix-Varianten füttern auf diese Weise ihren internen Zufallsgenerator, der in Form des Geräts /dev/random auch Anwendungen zur Verfügung steht. Andere Betriebssysteme können auf spezielle Software wie den Entropy Gathering Daemon egd zurückgreifen.

In der Regel ist die Ausbeute solcher Generatoren jedoch gering: Manche liefern nur einige zig Bit pro Sekunde. Außerdem kann es vorkommen, dass der Strom der Zufallszahlen versiegt, weil nicht mehr genug Entropie zur Verfügung steht – etwa bei „kopflosen“ Servern ohne Eingabegeräte. Ein Webserver beispielsweise, der laufend neue Sitzungsschlüssel für SSL/TLS generieren muss, kann dadurch leicht ins Stocken geraten.

Als Kompromiss kann man einen hybriden Zufallsgenerator verwenden, der die vorhandene Entropie in einen Pseudo-Zufallsgenerator einspeist, etwa den egd-kompatiblen prngd. Unter Linux steht dafür das Gerät /dev/urandom zur Verfügung. Man muss sich jedoch darüber im Klaren sein, dass mit solchen Generatoren erzeugte Schlüssel schwächer sind als solche, die auf „echtem“ Zufall beruhen.

Ein relativ junger Ansatz namens HAVEGE (hardware volatile entropy gathering and expansion) verwendet den internen Zustand des Prozessors als Entropiequelle. Die Sicherheit des Verfahrens beruht auf der Tatsache, dass sich der genaue Zustand moderner CPUs mit ihren langen Pipelines und einer Vielzahl von Caches weder im Detail beobachten noch vorhersagen lässt. Die Zeit, die der Prozessor zum Ausführen einer bestimmten Befehlssequenz benötigt, ist daher unvorhersehbaren Schwankungen unterworfen. HAVEGE misst sie und erzeugt daraus Zufallszahlen. Da der Algorithmus nicht auf externe Ereignisse wie Nutzereingaben angewiesen ist, kann seine Entropiequelle nicht versiegen.

HAVEGE ist als ladbares Modul für den Linux-Kernel (ab Version 2.6.13) und als Bibliothek erhältlich. Ersteres stellt zwei Geräte bereit: /dev/hrandom0 für den normalen Gebrauch und /dev/hrandom1 für kryptografische Anwendungen. libhavege enthält die Funktionen ndrand() und crypto_ndrand(), die sich als Ersatz für rand() nutzen lassen.

Linux-Nutzern bietet sich mit haveged außerdem die Möglichkeit, den Kernel-internen Zufallsgenerator mit Entropie „anzureichern“. Der Prozess läuft im Hintergrund und füllt den Entropie-Pool des Kernels nach, wenn sein Pegel unter eine einstellbare Schwelle fällt.

Mit audio-entropyd lässt sich unter Linux das Rauschen eines Audio-Eingangs als zusätzliche Entropiequelle nutzen. video_entropyd verwendet stattdessen das Signal einer Kamera, etwa einer Webcam. timer_entropyd wertet Schwankungen der Wartezeit bei Aufrufen der Funktion usleep() aus. rngd aus dem Debian-Paket rng-tools kann die Ausgabe eines Hardware-Zufallsgenerators in den Entropie-Pool des Kernels einspeisen.

Außerdem enthält das Softwarepaket das Testprogramm rngtest, mit dem sich die Zufälligkeit einer Bitfolge überprüfen lässt. Weitere Testprogramme sind im Quellcode-Paket von haveged enthalten. Wer jedoch einen Zufallsgenerator einem intensiven Qualitätstest unterziehen will, sollte zu diehard oder besser gleich zu dieharder greifen.

www.ix.de/ix1002151 (mr)