Warum und wie Zufallszahlengeneratoren das Mitlesen von Daten ermöglichen

Leser fragen – Danisch antwortet. [Update: Rechenfehler. Einer hat aufgepasst.]

Kannst Du mal kurz erklären oder wenigstens einen Link zu einer Erklärung setzen, warum Zufallszahlengeneratoren das Mitlesen von Daten ermöglichen.

Aber ja.

Ich stelle es mal etwas vereinfacht vor. (Zahlenbeispiele so gewählt, damit ich was zum erklären habe, eben nur Beispiele.)

Die Sache ist die. Es gibt so verschiedene Bereiche der IT-Sicherheit. Systemsicherheit. Beweissicherheit. Verfügbarkeit/Beweissicherheit. Organisatorische Sicherheit. Datensicherheit.

Kryptographie gehört zur Datensicherheit. Da geht es also nicht darum, dass irgendein Zugriffsmechanismus den Zugang erlaubt oder nicht (=Systemsicherheit), oder der Angreifer gar nicht erst an die Datenübertragung rankommt (=organisatorische Sicherheit), sondern dass die Daten selbst so transformiert und dargestellt werden, dass sie selbst sicher gegen Angriffe sind (Mitlesen, Fälschen, Wiederholen und sowas alles). Tote, wehrlose Daten.

Damit hat man nun aber ein Problem.

Der befugte Empfänger soll die Daten lesen können.

Der unbefugte Empfänger (=Angreifer) hat aus besagten Gründen den vollen Zugriff auf die geschützten Daten, weil er nicht durch einen Zugangsmechanismus oder eine räumliche Trennung davon abgehalten wird. Typischer Fall: Kommunikation durch das Internet. Was ich in meiner Wohnung mache, kann ich noch durch Firewalls und so weiter kontrollieren, und notfalls auch eine direkte Leitung zum Nachbarn legen, wenn ich mit dem was will, aber in dem Moment, wo ich mit Leuten über das Internet kommuniziere, etwa ihnen eine Mail schicke oder diese Webseite hier präsentiere, muss ich notgedrungen durch „Feindesland”, und stehe damit vor dem Problem, dass der Angreifer die Daten genauso lesen – unter Umständen auch verändern oder ganz fälschen – kann.

Wie also schafft man es unter diesen Bedingungen, dass zwei auch dann, wenn sie das gleiche tun, nämlich die übertragenen Daten zu sehen, trotzdem unterschiedliches können, nämlich einer die Daten verstehen kann und der andere nicht.

Das geht mittels eines Geheimnisses. Wenn der befugte Empfänger weiß, wie er die Daten umrechnen kann, der Angreifer aber nicht, gelingt der Unterschied. Der eine kann was, der andere kann es nicht.

Und weil man das alles sehr mathematisch treibt, ist dieses Geheimnis eine sehr lange Zahl. Oder eine Folge von Bits (Nullen und Einsen). Was zwar fast, aber nicht ganz das Gleiche ist.

Und weil dieses Geheimnis erlaubt, die Daten zu lesen, sie zu „entschlüsseln”, nennt man so ein Geheimnis in den meisten Fällen „Schlüssel”.

Wer den Schlüssel kennt, der kann die Daten lesen. Wer ihn nicht kennt, der kann die Daten (hoffentlich) nicht mitlesen. Darauf kann man sich aber aus zwei Hauptgründen nicht immer so verlassen:

• Wenn das Verfahren, mit dem man die Daten verschlüsselt, Fehler hat, Schwächen aufweist, kann der Angreifer daraus vielleicht den Schlüssel herausfummeln oder ohne Schlüssel auskommen. Das darf natürlich nicht sein.

• Selbst wenn das Verfahren gut ist, könnte der Angreifer ja einfach alle Schlüssel, die es geben kann, mal ausprobieren, welcher davon passt.

Um das mit dem Ausprobieren aller Schlüssel zu verstehen, darf man einem Denkfehler nicht unterliegen: Wenn man sich an einer Webseite dreimal mit dem falschen Passwort anmelden will, kann die einfach dicht machen, damit man nicht rumprobieren kann. Das ist aber Systemsicherheit, da läuft hinten ein Programm, das mitzählen und reagieren kann. Das haben wir hier nicht. Der Angreifer ist im Besitz der verschlüsselten Daten und kann auf seinem eigenen Rechner damit anstellen, was er so will. Und einfach durch Ausprobieren versuchen, welcher Schlüssel passt.

Genau so funktionierte in den 90er Jahren das Kryptoexportverbot der USA. Da durften Verschlüsselungen nur 40 Bit Schlüssellänge haben. Und mit 40 Bit kann man eben nur 2⁴⁰=1099511627776 verschiedene Schlüssel machen. Das hört sich nach viel an, ist es aber nicht. Für Computer ist das sogar ganz wenig. Das können die ganz schnell ausprobieren, welcher dieser 1099511627776 Schlüssel passt. Selbst DES mit 56 Bit war da zu schwach.

Deshalb sagt man, dass man ganz viele Bits und ganz lange Schlüssel braucht, damit es so viele mögliche Schlüssel gibt, dass der Angreifer die niemals alle durchprobieren kann.

Deshalb verwendet man bei symmetrischen Chiffren, die als Schlüssel eine beliebige Bitfolge haben, mindestens 128 Bit Schlüssellänge, weil man damit gleich viel mehr mögliche Schlüssel hat. Nicht etwa dreimal soviel, weil 3*40=120, sondern ganz viel mehr, weil jedes einzelne Bit mehr jeweils eine Verdopplung bedeutet. Schon drei Bit mehr sind jeweils eine Verachtfachung. Und 2¹²⁸ = 340282366920938463463374607431768211456. Das hört sich schon viel besser als 1099511627776 an, weil man da abschätzen kann, dass es solche Computer eigentlich nicht geben kann, die die alle durchprobieren. Rein vorsichtshalber verwendet man aber heute noch längere Schlüssel. 192 oder 256 Bit.

Etwas schwieriger sieht es bei den Asymetrischen Verfahren aus, weil die ihre Geheimnisse als Zahl interpretieren und sie für Exponentialrechnung oder diskreten Logarithmus verwenden, und das Primzahlen sein müssen, das geht nicht mit jeder, weshalb da große Abstände zwischen den Zahlen sind, und man da ja dann auch rechnen kann. Deshalb nimmt man da Zahlen mit mindestens 2048 Bit.

Manchmal muss man solche Zahlen nur einmal finden, wenn man einen längerfristig benutzten Private/Public-Key hat. Und manchmal auch ganz oft. Weil manche Protokolle es erfordern, bei jeder Übertragung, beispielsweise jeder Webseite, einen Verbindungsschlüssel neu auszuhandeln oder irgendeine Zufallszahl mit einzustricken, damit es einmalig ist.

Das Riesenproblem

Nun steht man vor einem Problem:

Woher kommen solche Zahlen, die nur den befugten Kommunikationsteilnehmern, aber nicht dem Angreifer bekannt sind?

Der Punkt ist nämlich der, dass Computer so präzise arbeiten, dass dasselbe Programm auch immer dieselben Ergebnisse ausspuckt, wenn man es immer wieder oder sogar auf verschiedenen Computern laufen lässt. Man sagt: Der Computer arbeitet deterministisch. Weil von vornherein feststeht, was raus kommt.

Oder anders gesagt: Man kann eigentlich nichts rechnen, was der Angreifer nicht genauso rechnen kann, wenn er einen identischen Computer, dasselbe Program, dieselben Parameter hat. Man kann mit einem Computer eigentlich keine Geheimnisse finden und deshalb keine Schlüssel erzeugen, egal ob nun die langfristigen wie public/private key, die mittelfristigen wie secret key, oder die kurzfristigen wie Sitzungsschlüssel. Es ist ein zentrales Problem der Kryptographie, eines der wichtigsten, dass man mit Computern eigentlich keine Geheimnisse finden kann, weil der Computer nichts rechnen kann, was ein zweiter nicht genauso rechnen würde.

Oder etwas trockener gesagt: Ein deterministischer Computer kann keine geheimen Zahlen finden, weil ein zweiter Computer das exakt wiederholen könnte und dieselben Zahlen fände.

Das mag sich jetzt etwas unwirklich anhören, denn wer hat schon zwei wirklich identische Computer. Aber das passiert öfters, als man so denkt, weil ja auch nicht alles für das Finden von Zahlen relevant ist. Und weil wir uns ja gerne fertige Betriebssystem-Images runterziehen, in der Cloud Systeme aus dem gleichen Images erzeugen, alle dieselben Linux-Distributionen mit denselben Kerneln verwenden, ist dieses Problem gar nicht so abwegig.

Es ist ein sehr schweres Problem, auf einem Computer Zufallszahlen zu finden, die kryptographisch gut sind, die also ein zweiter Computer nicht ebenso nachrechnen könnte.

Zum Vergleich: Bei anderen Anwendungen, beispielsweise beim Raytracing, braucht man das Gegenteil, nämlich reproduzierbare Zufallszahlen, damit die Wolken und die Meereswellen im nächsten Bild an derselben Stelle sind und nicht einfach im Bild herumspringen. Es gibt ganz unterschiedliche Anforderungen für Zufallszahlen, die kryptographischen haben Anforderungen, die ein Computer eigentlich gar nicht erfüllen kann.

Man versucht der Sache auf zwei Arten Herr zu werden.

Zum einen verwendet man Pseudozufallszahlengeneratoren. Das sind Algorithmen, die eben versuchen, das Beste aus dem zu machen, was an Zufall da ist den ein zweiter Rechner nicht identisch nachvollziehen kann. Mausbewegungen. Zeitabstände zwischen den Tastendrücken auf der Tastatur. Und solches Zeug, weil man auf einem zweiten Rechner Maus und Tastatur nicht identisch bewegen kann. Das rührt man da alles mit rein und hofft dann, dass der Pseudozufallszahlengenerator daraus etwas macht, was möglichst durcheinander und für andere Rechner nicht reproduzierbar ist. Wer schon mal Schlüssel mit der ein oder anderen Software generiert hat, hat das vielleicht schon erlebt, dass die Software sagt, man solle mal die Maus herumschieben oder irgendwas auf der Tastatur eingeben. Damit füttert man den Pseudozufallszahlengenerator mit Zufall.

Und die andere Methode sind echte Zufallszahlengeneratoren, die man in Hardware baut. Beispielsweise irgendwelche Zählrohre wie im Geigerzähler, die den Einschlag irgendwelcher Teilchen aus dem Weltraum messen. Oder Dioden, die in Sperrichtung an der Durchbruchgrenze arbeiten und dabei erbärmlich rauschen – genau das, was man hier braucht, weil das nämlich auch zufällig ist und durch kleinste Unregelmäßigkeiten und Temperaturunterschiede beeinflusst wird. Manche Prozessoren haben sowas eingebaut. Mache Kryptomodule, die als USB-Stick daherkommen, haben sowas. Wer in seinem Rechner ein TPM hat, ein Trusted Platform Module, der hat auch sowas. Und sogar der kleine Billig-Computer Raspberry Pi hat sowas. Weil der nämlich genau das Problem hat, dass viele ihn mit identischer Software betreiben, die sie als Image runterladen, der dann auch keine Hardwareuhr hat, und damit im Prinzip sämtliche Raspberry Pis dieser Welt auf dieselben Zufallszahlen kämen, etwa wenn sie beim ersten Boot ihre SSH-Schlüssel erzeugen. Und dann alle die gleichen hätten. Deshalb hat der Raspberry zwar keine Uhr, aber dafür einen physikalischen Zufallszahlengenerator.

Und damit hat der Computer dann aus der einen oder der anderen (am besten aus beiden, je mehr, desto besser) Quellen „frischen Zufall”, den ein zweiter nicht nachrechnen kann. Damit erzeugt man dann die Schlüssel, die so beschaffen sein müssen, dass ein zweiter nicht draufkommt.

Die Sauerei

Schafft es der Angreifer aber, einem einen schlechten Zufallszahlengenerator unterzujubeln, dann sieht man schlecht aus, weil man dann keine guten Schlüssel erzeugen kann. Wenn beispielsweise der Algorithmus faul ist. Oder die Physik eben doch keine wirklich zufälligen Zahlen erzeugt. Es hat mal jemand nachgewiesen, dass man den Generator in einem Prozessor durch Dotierung manipulieren kann. Selbst wenn man die Leitungen und Transistoren des Prozessors unter dem Elektronenmikroskop prüfen würde, könnte man die Manipulation nicht entdecken.

Wenn diese faule Quelle für Zufallszahlen also nun nicht so zufällig ist, wie man denkt, wenn sie sich etwa wiederholt, oder man aus den einmal bekannten Zufallszahlen, die sie ausgibt, errechnen kann, welche Zahlen sie als nächstes ausgeben wird, dann hat man ein Riesenproblem.

Wenn beispielsweise der Zufallszahlengenerator seine Ausgabe nach 2⁴⁰-Bit einfach wiederholt, egal was an Futter reinkommt, es also nur 2⁴⁰ verschiedene Zustände und Ausgaben gibt, dann kann der Computer daraus auch nur höchstens 2⁴⁰=1099511627776 verschiedene Schlüssel erzeugen, selbst wenn man glaubt, einen 128-Bit-Schlüssel mit 340282366920938463463374607431768211456 Möglichkeiten zu verwenden.

Man hat also eine – vermeintlich – sichere Chiffre mit 128 Bit Schlüsselraum, der Computer kann aber nur 2⁴⁰ und nicht 2¹²⁸ verschiedene Schlüssel erzeugen, wenn der Zufallszahlengenerator nur 2⁴⁰ verschiedene Ausgaben kennt. Die anderen 2¹²⁸-2⁴⁰ Schlüssel kann man nie erzeugen. Weil ein deterministisches Programm, für das es nur 2⁴⁰ Eingaben gibt, auch nur höchstens 2⁴⁰ verschiedene Ausgaben erzeugen kann.

Man kann sich das so vorstellen: Stellt Euch vor, Ihr seid Koch. Und sollt nun in Abhängigkeit vom Datum immer ein anderes Menü kochen, die Speisekarte möglichst „divers” halten. Habt aber selbst keine Uhr, keine Anzeige, sondern seid darauf angewiesen, dass Euch jemand das Datum sagt, zu dem Ihr das Menü festlegen soll.

Sagt Euch jetzt jemand Tag und Monat, gibt es 365 Möglichkeiten, und Ihr könnt 365 verschiedene Menüs und Rezepte anbieten.

Sagt Euch aber einer immer nur den Wochentag, also nur 7 verschiedene Eingaben, kann’s auch nur 7 verschiedene Menüs geben, weil es Montags eben Bockwurst gibt, Dienstags Schnitzel, Mittwochs Kartoffelsuppe. Dann gibt es nur 7 verschiedene Menüs, weil’s am nächsten Montag wieder Bockwurst gibt. Und den Montag drauf. Und so fort. Und so oft, wie es in der Analogie Bockwurst gibt, gibt es im Computer dann dieselben Schlüssel.

Und dann sieht der Schlüssel zwar so aus, als gäbe es 340282366920938463463374607431768211456 verschiedene Schlüssel, weil 128 Bit lang, tatsächlich kann der Computer aber nur 1099511627776 davon „finden”, wenn der Zufallszahlengenerator faul ist.

Und wenn ein Angreifer das weiß, dann kann er den Schlüssel leicht brechen, weil er nur 1099511627776 und nicht 340282366920938463463374607431768211456 Schlüssel ausprobieren muss. Ersteres geht, letzteres nicht.

Man glaubt also, man verwendet einen starken Verschlüsselungsalgorithmus, schwächt ihn aber, weil der Computer nur eine kleine Zahl von Schlüsseln finden und benutzen kann. Gegenüber dem Angreifer, der weiß, was schief läuft, benimmt sich der starke Algorithmus also wie ein schwacher.

Die Gemeinheit daran ist: der ganze Rest der Verschlüsselungssoftware, die Chiffren, die Implementierung, können alle völlig tadelos und sicher sein und jeder Überprüfung standhalten. Es nutzt einem alles nichts, wenn man keine gute Zufallsquelle hat, die einem erlaubt, auch wirklich alle Schlüssel zu finden und zu erzeugen.

Solche Zufallsquellen sind aber sehr schwer zu verstehen und auf Qualität zu prüfen. Dafür gibt es einige dreckige Methoden, sie zu manipulieren.

Und deshalb ist es ein effektiver und nur sehr schwer abzuwehrender Angriff, jemandem einen faulen Zufallszahlengenerator unterzujubeln, der faule Zufallszahlen ausspuckt. Dann nutzt einem der ganze Rest an toller Software nicht mehr viel.

Und genau sowas ist bei den Linux-Distributionen Debian und Ubuntu 2008 mal passiert. Angeblich ein Versehen. Man hatte am Paket openssl irgendwas herumgepatcht, dabei aber einen Fehler gemacht, und damit dafür gesorgt, dass die Schlüssel vorhersagbar und alle schwach waren. Eben weil man den Zufallszahlengenerator vermurkst hatte.

Update: Ein Leser hat aufgepasst und einen Rechenfehler entdeckt.

Denkfehler meinerseits. Wollte nämlich erst schreiben, dass es Systeme gibt, die einen Teil des Schlüssels für den Staat freilegen, so dass der noch 40 Bit brechen muss, und dachte erst an den Clipper-Chip, hatte aber nochmal nachgesehen, der war’s nicht. Dessen LEAF legte den vollen Schlüssel (80 Bit) offen. Weil mir das nicht mehr einfiel, wo das war, dass alle bis auf 40 Bit offengelegt werden, hatte ich es wieder rausgenommen, aber die Rechnung dummerweise drinstehen gelassen.

Wenn man nämlich von 128 Bit Schlüssel nur 40 Bit echten Zufall hat, also statt 2¹²⁸ nur 2⁴⁰ Schlüssel hat, rechnet man nicht wie bei einer Teilschlüsseloffenlegung, sondern subtrahiert einfach. Es sind als nicht, wie ich fälschlich geschrieben hatte, 2⁸⁸ Schlüssel, die man nicht erreicht (Denkfehler von der Teil-Offenlegung 128-40=88), sondern 2¹²⁸-2⁴⁰, also immer noch rund 2¹²⁸ Schlüssel, die man nicht erreicht.

Da hat einer gut aufgepasst. Danke!