Möglicherweise haben Sie sich, als Sie klein waren, auch einmal mit der Chiffrierung von Nachrichten beschäftigt, um im Schulzimmer oder auf dem Spielplatz mit einem eingeweihten Nachbarn zu kommunizieren, ohne dass Dritte z.B. ihr Lehrer mitlesen konnten – selbst dann, wenn die Nachrichten beim Transport abgefangen wurden.
Der Versand von verschlüsselten Nachrichten über einen unsicheren, für jeden Gegner einsehbaren, Transportkanal hat eine lange Tradition. Bereits die alten Griechen und Römer wandten verschiedene solche Verfahren an, um die Vertraulichkeit ihrer Nachrichten sicherzustellen. Die sogenannte Cäsar-Chiffre basiert z.B. auf einer Rotation des Alphabets um eine bestimmte Anzahl Buchstaben. Eine sehr viel ausgeklügeltere Variante (nahezu beliebige Permutationen des Alphabets anstelle einer einfachen Rotation) dieses Prinzips wurde rund zwei Jahrtausende später von der deutschen Wehrmacht im zweiten Weltkrieg eingesetzt: Enigma. Im digitalen Zeitalter sind beispielsweise der Data-Encryption-Standard (DES) oder asymmetrische Public-Key Verfahren gängige Methoden.
Alle diese Methoden haben gemeinsam, dass mit Hilfe eines definierten Vorgehens eine Nachricht (Klartext) und ein Schlüssel zu einer verschlüsselten Nachricht (Geheimtext) kombiniert werden, diese auf einem unsicheren Kanal (z.B. dem Internet) übermittelt wird und anschliessend wieder mittels eines definierten Vorgehens und einem Schlüssel zum Klartext entschlüsselt wird. Vor der Veröffentlichung des RSA-Kryptosystems 1977 wurde bei allen bekannten Verfahren sowohl vom Empfänger als auch vom Absender derselbe Schlüssel benutzt. Die Verfahren werden deswegen auch heute noch «symmetrische» Verfahren genannt.
Ein symmetrisches Kryptosystem lässt sich grafisch wie folgt zusammenfassen:
Die Kryptographie setzt sich dabei unter anderem auf systematische Art und Weise damit auseinander, welche Garantien solche Systeme unter welchen Annahmen leisten. (Wie einfach oder schwierig ist es z.B. einen Schlüssel aufgrund bekanntem Geheimtext zu erraten, ohne diesen zu kennen? – Ein Problem, welches die Alliierten bei Enigma ganz wesentlich beschäftigt hatte.)
Annahmen und Garantien hin oder her, zwei wesentliche Probleme konnten bis zu grundlegenden Durchbrüchen in der Kryptographie in den 1970er Jahren nicht zufriedenstellend gelöst werden:
- Der verwendete Schlüssel musste (vor dessen erster Verwendung) vom Absender zum Empfänger (oder umgekehrt) übermittelt werden. Dies musste so gestaltet werden, dass der Schlüssel unterwegs von niemandem abgefangen werden konnte. Ansonsten war die eingesetzte Verschlüsselung nutzlos, auch wenn das eigentliche Verfahren noch so stark war.
- Noch viel schlimmer: Absender und Empfänger mussten davon ausgehen können, dass die Gegenpartei den erhaltenen Schlüssel nach Erhalt auch geheim hält, einander also vertrauen. Heutzutage ist die Sache mit dem Vertrauen, kombiniert mit der Anonymität des Internets, bekanntermassen ein schwieriges Thema.
Problem eins wurde 1976 mit dem Diffie-Hellmann Schlüsselaustauschverfahren (DH) gelöst. DH ermöglicht es für zwei Parteien, üblicherweise die berühmt-berüchtigte «Alice» und ihr Freund «Bob» über einen unsicheren Kanal mittels einer definierten Sequenz von Nachrichten einen geheimen Schlüssel auszuhandeln, ohne dass eine Drittpartei, welche jede einzelne dieser Nachrichten mitlesen kann, am Ende des Austausches ebenfalls den Schlüssel von Alice und Bob kennt.
Problem zwei wurde ein Jahr später, 1977, durch die Veröffentlichung des RSA-Kryptosystems gelöst. Das RSA-Kryptosystem erlaubt es, Klartext mit einem Schlüssel (üblicherweise Public-Key genannt) zu verschlüsseln, lässt es aber nicht zu, dass dies mit dem gleichen Schlüssel wieder rückgängig gemacht wird. Für die Entschlüsselung des Geheimtextes wird ein zweiter Schlüssel (üblicherweise Private-Key genannt) benötigt, welcher sich vom ersten unterscheidet. Die folgende Abbildung fasst diese Abläufe zusammen.
Dies eröffnet eine ganze Reihe von Möglichkeiten, ohne die das Internet in seiner heutigen Form nicht das wäre, was es ist (ein weltumfassendes, zu einem Content-Delivery-System verbogenes, Hypertext-Übermittlungmedium – doch dazu in einem anderen Blog-Post mehr).
Ein Blick unter die Haube asymmetrischer Verfahren
Im Unterschied zu pre-70er, symmetrischen Verfahren, welche im Wesentlichen den Klartext mit Hilfe des (symmetrischen) Schlüssels nach einem vorgegebenen Verfahren permutierten, nutzen asymmetrische Verfahren spezielle Eigenschaften der zugrundeliegenden mathematischen Gebilde (sogenannte zyklische Gruppen). Die Asymmetrie der Verfahren folgt dabei gewissermassen aus einer Asymmetrie in den Eigenschaften der zugrundeliegenden mathematischen Konzepte. Konkreter handelt es sich um Rechenoperationen, welche einfach durchzuführen aber nur sehr schwierig wieder umzukehren sind. (Dies passt intuitiv zur Aussage oben, dass die Verschlüsselung einfach, die Entschlüsselung mit dem gleichen Schlüssel aber schwierig/unmöglich ist.) Solche Operationen werden im Zusammenhang der Kryptographie üblicherweise Einweg- oder Falltürfunktionen genannt.
Als ein Beispiel zur Illustration des Prinzips einer Einwegfunktion nehmen wir das Quadrat (Multiplikation mit sich selbst) einer natürlichen Zahl, z.B. 273:
273 * 273 = 74529
Diese Berechnung (also der Hinweg) ist relativ einfach, z.B. durch schriftliche Multiplikation erledigt. Die Rückrichtung scheint aber wesentlich schwieriger: Wenn Sie die Aufgabe bekommen, ohne Taschenrechner die Quadratwurzel aus 74529 zu berechnen, werden Sie damit einen Moment lang beschäftigt sein.
Wie lange Sie für diese Aufgabe benötigen, hängt davon ab, wie geschickt Sie vorgehen: Sie könnten z.B. einfach alle ganzen Zahlen, angefangen bei 1 der Reihe nach quadrieren und dabei prüfen, ob Sie 74529 erhalten. Stilnote erhalten Sie für dieses Vorgehen eine ziemlich schlechte, andererseits müssen Sie wenig bis gar nicht über Ihr gewähltes Vorgehen nachdenken, bevor Sie beginnen können. Etwas geschickter wäre es, nur die ungeraden Zahlen zu prüfen. (Da 74529 ebenfalls ungerade, ist es nicht möglich, dass Sie das Quadrat einer geraden Zahl vor sich haben.) Mit dieser simplen Beobachtung würde sich Ihr Aufwand bereits um etwa die Hälfte reduzieren!
Es geht mir hier nicht darum, ein effizientes Verfahren für die Berechnung von Quadratwurzeln zu entwickeln, sondern aufzuzeigen, welche Auswirkungen Verbesserungen am Vorgehen zum Lösen einer Aufgabe – algorithmische Verbesserungen – haben können.
Komplexitätsklassen und P=NP (oder eben nicht)
Mit der Frage, wie schwierig oder einfach ein bestimmtes Problem durch einen Algorithmus zu lösen ist, beschäftigt sich ein Teilgebiet der theoretischen Informatik: Die Komplexitätstheorie. Dabei werden asymptotische Überlegungen angestellt, das heisst es wird untersucht, was passiert, wie der Aufwand zum Finden einer Lösung mit der «Grösse» der gestellten Aufgabe wächst.
Im Beispiel der Multiplikation oben wäre mit der «Grösse» der Aufgabe die Anzahl Stellen der Eingangszahl – im Beispiel drei Ziffern – gemeint. Es würde also untersucht, wie sich der nötige Rechenaufwand (wie viele Rechenoperationen werden benötigt?) verhält, wenn die Eingangszahlen nicht drei, sondern 100, 1000, 10000 Stellen beinhalten.
Basierend auf Resultaten aus solchen Überlegungen werden Probleme in «Komplexitätsklassen» eingeteilt. Probleme innerhalb einer bestimmten Klasse werden dabei als «ungefähr gleich schwierig» betrachtet, wenn ein Vorgehen aus einer einfacheren Klasse existiert, um die Aufgabenstellungen der schwierigeren Klasse in einander hin- und her zu «übersetzen». (Wenn die Probleme «gross» genug werden, wird der Übersetzungsaufwand im Verhältnis vernachlässigbar klein.) Bei den mathematischen Operationen, welche heute als Falltürfunktionen genutzt werden, wird davon ausgegangen, dass die Bewältigung der Hin- und der Rückrichtung unterschiedlichen Komplexitätsklassen (einer einfachen und einer schwierigen) angehören. Die für die Zwecke der Kryptographie wichtigsten solche Klassen sind die Klassen «P» (einfach) und «NP» (schwierig).
Die genaue Bedeutung dieser Klassen würde den Rahmen dieses Blogposts sprengen. Der Punkt hier ist aber folgender: Es ist nach aktuellem Kenntnisstand unklar, ob nicht ein effizientes, (aktuell noch unbekanntes) Vorgehen existiert, mit Hilfe dessen sich der «Graben» zwischen den beiden Klassen überbrücken lässt, so dass diese letztendlich identisch wären. Es ist also unklar, ob die Rückrichtung, aus der Falltürfunktion heraus, wirklich so schwierig zu bewältigen ist, oder ob nicht vielleicht doch ein effizienter Algorithmus existiert, welcher dies bewerkstelligen könnte.Um die formale Beantwortung dieser Frage dreht sich das berühmte P=NP-Problem, eines der sogenannten Millennium-Probleme für dessen Lösung vom Clay Mathematics Institute ein Preisgeld von 1 Mio. USD ausgesetzt wurde.
Zurück zu RSA und Konsorten
Die mathematischen Operationen, welche bei asymmetrischen Kryptosystemen zum Einsatz kommen, sind komplexer und mindestens so schwierig zu invertieren, wie das Quadrat einer ganzen Zahl. Beispielsweise basiert das RSA-Kryptosystem auf einem mit unserem Beispiel verwandten Problem, nämlich das Produkt aus zwei grossen Primzahlen wieder in diese Primzahlen zu zerlegen, ohne dass die zugehörigen Faktoren vorher bekannt sind.
Ähnlich, wie wir uns vorher durch ein geschicktes Vorgehen Arbeit zum Berechnen der Quadratwurzel gespart haben, werden auch die Algorithmen welche das RSA-Problem (und ähnliche verwandte Probleme) lösen, laufend verbessert. Könnte es also sein, dass ein effizientes Vorgehen zur Umkehr der von RSA genutzten Einwegfunktion existiert? Ja. Kennen wir ein solches Verfahren? Nein. Können wir deshalb darauf schliessen, dass kein solches Verfahren existiert? Ebenfalls nein! Die Sicherheit von asymmetrischen Kryptosystemen basiert also auf der unbewiesenen Annahme, dass die fundamentale Asymmetrie in der Zeitkomplexität des Hin- und des Rückweg einer Einwegfunktion tatsächlich existiert (bzw. die Bewältigung der Hin- und Rückrichtung unterschiedlichen Komplexitätsklassen angehören).
Und nun zurück in die Praxis
Abgesehen von obigen fundamentalen theoretischen Problemchen, tauchen in der Praxis auch immer wieder Fälle auf, in welchen bestimmte Konfigurationen, oder sogar ganze Familien von Kryptoverfahren «pensioniert» werden müssen. Dies beispielsweise, weil neu entwickelte Verfahren, oder zunehmende Rechenleistung, dazu führen, dass bisher als sicher geltende Schlüssellängen nicht mehr die nötige Sicherheit bieten. Es kommt ausserdem vor, dass Parameter der eingesetzten Kryptoverfahren bewusst oder unbewusst auf unsichere Art und Weise gewählt werden, oder Angriffsmethoden bekannt werden, welche ein bestimmtes Verfahren nutzlos machen (Beispielsweise reduziert die Möglichkeit, zum Hash-Algorithmus MD5 sogenannte Kollisionen zu konstruieren, den Nutzen von MD5 zur Integritätsprüfung von Informationen auf ein recht bescheidenes Mass.) Es findet beim Einsatz kryptographischer Verfahren somit also eine Art «Wettrüsten» statt, was in der Hektik des Alltags gerne vergessen wird.
Die Netzwerkspezialisten von United Security Providers beraten Sie gerne zur Wahl der Kryptoparameter und -verfahren in Ihrer Infrastruktur.