Zufallszahlen und ihre Generierung

Unterscheidung zwischen echten und Pseudo-Zufallszahlen

Eine Zufallszahl ist eine zufällige Zahl aus einer durch Minimum und Maximum begrenzten Zahlenmenge, die vom Gewinnungsverfahren abhängt. Man unterscheidet zwischen echten Zufallszahlen (auch "physikalischen", "natürlichen") Gewinnungsverfahren (auch "Zufallszahlengeneratoren") und Pseudozufallszahlen ("künstlichen").

Zu den Gewinnungsverfahren für echte Zufallszahlen gehören z. B. Münzwurf (Zufallszahl 1 oder 2), Würfeln (Zufallszahl zwischen 1 und 6), Roulette (Zufallszahl zwischen 0 und 36) oder auch radioaktiver Zerfallsprozesse (gerade oder ungerade gemessene Teilchenanzahl in einem bestimmten Zeitabschnitt). Die gewonnenen Zahlen sind rein zufällig und nicht hervorsehbar.

Pseudozufallszahlen werden dagegen durch mathematische Algorithmen gewonnen und sind damit hervorsagbar, da sie ja nach einem bestimmten Schema berechnet werden und die Zahlenreihe dadurch willkürlich weitergeführt wird. Pseudozufallszahlen machen aber auf den ersten Blick den Eindruck als seien sie echt, denn sie erfüllen die gleichen oder ähnliche statistische Eigenschaften (Gleichverteilung, Korrelation). Je besser ein Pseudozufallszahlengenerator ist, desto weniger sieht man seinen Zufallszahlen an, dass diese künstlich sind.

Zufallszahlengeneratoren, die echte Zufallszahlen liefern, also solche, die nicht errechnet wurden, nennt man auch nicht-deterministischen Zufallszahlengeneratoren. Sie stehen im Gegensatz zu den deterministischen Pseudozufallszahlengeneratoren, dessen Zahlen Ergebnis einer Berechnung ist und bei der gleichen Ausgangsbasis (sogenannter Seed-Wert) auch immer die selbe Zufallszahlenreihe ausgegeben wird. Nicht-deterministische Zufallszahlengeneratoren liefern hingegen immer unterschiedliche Zahlenfolgen.

Ein in Software abgebildeter Zufallszahlengenerator muss immer deterministisch sein (liefert als Pseudo-Zufallszahlen), da er immer auf einem Algorithmus, einer Rechenvorschrift, basiert und die Zufallszahlen damit errechnet sind. Nur mit einer zusätzlichen nicht-deterministischen Quelle kann ein Computer echte Zufallszahlen ausgeben.

Um auszuschließen, dass ein Angreifer das Muster hinter einem Pseudozufallszahlengenerator vielleicht erkennt, sind für entsprechende Verschlüsselungsverfahren (z. B. One Time Pad) echte Zufallszahlen die erste Wahl.

Gibt es Häufungen in bestimmten "zufälligen" Ziffern oder Zahlen, so kann man diese Erkenntnis einsetzen, um statistische Analysen zu fahren und es evtl. schaffen, das eigentlich sichere One-Time-Pad-Verfahren zu brechen.

Historische Zufallszahlengeneratoren

Bei den Deutschen hieß das One-Time-Pad-Verfahren "Wurmverfahren" und die Zufallszahlen, die für die Verschlüsselung nötig waren und an die Agenten verteilt wurden, bezeichnete man als "individuelle Würmer" (kurz "I-Würmer") oder Wurmtabellen. Für die Gewinnung von echten Zufallszahlen wurden unterschiedliche Geräte benutzt.

Eines davon ist ein Gerät namens "Violine", dessen Zufallszahlen für die Chiffrierung von Funksprüchen auf Generalstabsebene eingesetzt wurden.(1, 2) Die Violine war ein Holzbrett in der Form einer eben solchen, in die 5 große Kuhlen eingearbeitet waren, von denen 5 parallele Rinnen einen langen Steg entlangliefen. In den fünf Kuhlen befinden sich jeweils 30 mit 0 bis 9 nummerierte Dekaeder oder Murmeln. Das Violinen-System ist geschlossen und die Rinnen sind nicht übergehend, so dass immer 30 Murmeln je Rinne vorhanden waren.

Zur Erzeugung von Zufallszahlen hielt man die Violine schräg, so dass die Murmeln zurück in die Kuhlen liefen. Dann schüttelte man die Violinie kräftig durch, um für eine zufällige Durchmischung zu sorgen. Danach hob man die Violine auf der Kuhlenseite langsam an. Dadurch liefen die Murmeln die fünf Rinnen entlang und stoppten an deren Enden und formten Ziffernkolonnen, die man in Fünfergruppen als Zufallszahlen aufschrieb. Mit einer "Ziehung" konnten so 150 (5 mal 30) Zufallsziffern generiert werden, wobei eine Kopie als sogenannte Wurmtabelle an einen Agenten als Enschlüsselungsgrundlage weitergegeben wurde.

Nachdem man die Geräte der 60er Jahre, die radioaktiven Zerfall zur Zufallserzeugung genutzt hatten, wegen gesundheitlichen Bedenken ausgemustert hatte, wurde in der Zentralstelle für das Chiffrierwesen ein elektronisches Gerät in der Größe eines Kleiderschrankes entwickelt. Viel ist über die Funktionsweise des Geräte nicht bekannt, nur soviel dass es das Hintergrund-Rauschen von Dioden oder Trioden genutzt haben soll, um Zufallszahlen zu erzeugen.

Die Russen haben ihre Schlüssel wohl auch von Menschen auf Schreibmaschinen "zufallsgenerieren" lassen. Man gab den Typisten wohl einfach die Anweisung, zufällig auf den Zifferntasten herumzuhacken und vertraute darauf, dass das Ergebnis zufällig sein würde.

David Kahn, einem bekannten amerikanischen Kryptologen, fiel auf, dass sich gehäufterweise eine kleine mit einer großen Ziffer abwechselte wie in "29184" und er schloss daraus, dass das wohl daran liegen wird, dass sich die Menschen einen gewissen Rhythmus beim tippen angewöhnt hatten: linke Hand, rechte Hand (was nicht verwunderlich ist bei den damals schwergängigen Schreibmaschinen). Ihm fiel auch auf, dass 75% der Zahlen mit einer niedrigen Ziffer (linke Hand) begannen und nur 25% mit einer hohen (rechte Hand). Das lag wohl daran, dass die meisten Typisten die Leertaste mit dem rechten Daumen bedienten und danach wieder die andere Hand benutzten. Zudem fiel ihm auf, dass doppelte oder dreifache Vorkommen derselben Ziffer hintereinander wesentlich seltener vorkam als das für echt zufällige Zahlen anzunehmen war. Die Typisten dachten sich vielleicht: "drei mal die drei hintereinander, das ist doch nicht mehr zufällig!" und nahmen so bewusst oder unbewusst Einfluss auf die Zahlenreihen. Korrekturen und Radierungen sprachen auch für ein solchen Vorgehen.

Moderne Zufallszahlengeneratoren

Heutige kryptografische Verfahren mittels Computer werden ebenfalls durch Zufallszahlen bereichert, zum Beispiel, wenn man diese bei der Schlüsselgenerierung heranzieht.

Aber auch ein moderner Computer muss über eine nicht-deterministischen Quelle verfügen, die echte Zufallszahlen liefert, um wirklich zufällige Zahlen zu erzeugen. Rein in Software abgebildeter Zufallszahlengeneratoren sind immer deterministisch und damit nur Pseudo-Zufallszahlengeneratoren, deren Sicherheit je nach Algorithmus hoch sein kann, aber niemals absolut sein kann.

Dazu stellt man dem Hauptprozessor (CPU), der die in Code gegossenen Algorithmen abarbeitet einen sogenannten Kryptografie-Co-Prozessor zur Seite. Dieser enthält dann eine nicht-deterministischen Rauschquelle, aus der sich echte Zufallszahlen generieren lassen. In den meistens Fällen bieten die Crypto-Co-Prozessoren auch gleich einen Zufallszahlengenerator, der fertige Zufallszahlen zur Weiterverwendung durch die CPU ausgibt.

Für eine nicht-deterministischen Rauschquelle muss immer ein physikalischer Effekt Basis sein, wie zum Beispiel: Einige Quellen sind gesundheitlich bedenklich (radioaktiver Zerfall) oder zu langsam oder umständlich und sind deswegen in einem Co-Prozessor nicht geeignet. Am geeignetsten sind für Crypto-Co-Prozessoren wohl eine Kombination von Halbleitern, die sich in einem integriertem Schaltkreis auf einer separaten Chip-Die-Fläche unterbringen lassen.

Ein beliebter Crypto-Co-Prozessor ist zum Beispiel der ATECC608B von Microchip, der nach Angaben des Herstellers über einen hochqualitativen kryptografichen Zufallszahlengenerator verfügt, der über eine nicht-deterministischen Rauschquelle verfügt, dessen Werte er über einen deterministischen AES-Algorithmus mit 128 Bit zu brauchbaren Zufallszahlen weiterverarbeitet. Der Chip lässt sich mit seinen Abmessungen von 3 x 2 x 0.55 mm sehr platzsparend unterbringen. Außer der Generierung von Zufallszahlen besitzt er noch weitere kryptografische Funktionen.
ATECC608B-Datenblatt, Abschnitt Zufallszahlen

Der ATECC608B kann mit seinem internen Zufallszahlengenerator qualitativ hochwertige Zufallszahlen erzeugen. Diese ausgeklügelte Funktion umfasst Runtime-Health-Tests, um sicherzustellen, dass die Werte, welche intern aus einer Rauschquelle generiert werden zum Zeitpunkt der Nutzung ausreichend Entropie enthalten. Der Zufallszahlengenerator ist darauf ausgelegt, die Anforderungen, die in den Dokumenten NIST 800-90A, 800-90B und 800-90C dokumentiert sind, zu erfüllen. Die Zufallszahlen können für jeden Zweck verwendet werden, einschließlich als Teil der kryptografischen Protokolle des Geräts. Denn jede Zufallszahl ist im Wesentlichen einzigartig unter allen Zahlen, die jemals auf diesem oder einem anderen Gerät generiert wurden. Deren Einbeziehung in die Protokollberechnung sorgt dafür, dass Replay-Angriffe (d.h. das erneute Übertragen einer zuvor erfolgreiche Transaktion) fehlschlagen werden.
Natürlich gibt es auch kryptografische Coprozessoren anderer Hersteller wie NXP, IBM, STM, Analog Devices / Maxim oder Infineon. Dessen Crypto-Coprozessoren werden aber ähnlich aufgebaut sein und ähnliche Funktionen bieten.

Mit den heutigen kryptografischen Co-Prozessoren lassen sich also einfach und kostengünstig genügend schnell Zufallszahlen erzeugen. Die historischen, umständlichen Ermittlungsverfahren für Zufallszahlen dürften damit der Vergangenheit angehören.

Quellen, Literaturverweise und weiterführende Links

(1) Schmeh, Klaus: Die Welt der geheimen Zeichen, W3L 2004, S. 105
(2) Die Violine im Cipherbrain-Blog von Klaus Schmeh
(3) H. Wünsche: Zufallszahlen mit Rauschgeneratoren
(4) Digitaler Rauschgenerator im FPGA auf mikrocontroller.net
(5) Christoph Caspari: Widerstand: Rauschen von Widerständen auf elektronikinfo.de
(6) DSP generation of Pink (1/f) Noise, 1999
Bauer, Friedrich L.: Entzifferte Geheimnisse, Springer Verlag 1995, S. 117
Franke, Herbert W.: Die geheime Nachricht, Umschau Verlag 1982, S. 173
Beutelspacher, Albrecht: Kryptologie - Eine Einführung..., Springer Spektrum Verlag 2015, S. 63
Fumy, Walter und Rieß, Hans Peter: Kryptographie: Entwurf, Einsatz und Analyse..., Oldenbourg Verlag 1988, S. 108
Schmeh, Klaus: Kryptografie: Verfahren - Protokolle - Infrastrukturen, dpunkt Verlag, 5. Auflage 2013, iX-Edition, S. 265
Zufallszahlengenerator auf Wikipedia
Rauschgenerator auf Wikipedia Kryptoprozessor auf Wikipedia