Im zweiten Eintrag unserer Krypto-Kolumne wollen wir uns dem wohl bekanntesten Teil der Kryptographie zuwenden: Der Verschlüsselung. Ihr Ziel ist es, Nachrichten so zu verschleiern, dass ihr Inhalt für Außenstehende geheim bleibt und nur bestimmte Empfänger diese Verschleierung wieder rückgängig machen und somit die Nachrichten lesen können.
Mit „Nachrichten“ sind dabei beliebige Datensätze gemeint: E-Mails, Programmcode, Bilder usw. Klingt erstmal nach Spionage, ist aber ganz alltäglich geworden. Ob Sie es glauben oder nicht: Allein beim Aufruf dieses Artikels haben Sie verschlüsselt kommuniziert! Schauen Sie mal die Adresszeile Ihres Browsers an. Sie sollten hier ein kleines Vorhängeschlosssymbol sehen (im Screenshot rot markiert):
Was bedeutet das? Nun, ihr Browser hat, für Sie unbemerkt, einen verschlüsselten Datenaustausch mit dem Server von secuvera durchgeführt.
Der Datenaustausch im Internet ist ein ganz natürliches Beispiel für die Anwendung von Verschlüsselungen. Halten Sie mal ein Auge auf die Adresszeile, während Sie im Internet surfen. Tipp: Bei Websites ohne dieses Vorhängeschloss sollten Sie besser keine privaten Daten von sich eingeben! 😉 Aber Achtung: der Umkehrschluss „Alles ist sicher, wenn ich dieses Symbol sehe“ stimmt leider nur dann, wenn die Websitebetreiber wissen, was sie tun! (und tatsächlich finden wir bei den meisten Penetrationstest genau hier Konfigurationsprobleme)
Aber was passiert da eigentlich? Wie wird ein Text oder eine Website verschlüsselt? Verschlüsselungsverfahren gibt es quasi in zwei „Geschmacksrichtungen“: symmetrische und asymmetrische Verschlüsselung. Schauen wir uns das mal genauer an.
Symmetrische Verschlüsselung
Bei der symmetrischen Verschlüsselung teilen sich der Empfänger (nennen wir ihn Bob) und die Senderin (nennen wir sie Vera) ein gemeinsames Geheimnis, „geheimer Schlüssel“ genannt. Ein solcher geheimer Schlüssel ist häufig nichts anderes als eine zufällige Zeichenkette, etwa „JXSVACUQMYYXOPIF“. Schlüssel sind auf den ersten Blick Passwörtern sehr ähnlich, jedoch müssen sie im Regelfall bestimmte Anforderungen erfüllen. Fast immer müssen sie von einem Schlüsselerzeugungsalgorithmus berechnet werden, eine festgelegte Länge haben und die Kodierung eines bestimmten mathematischen Objekts darstellen.
Folgendes Szenario: Vera und Bob haben bereits einen gemeinsamen geheimen Schlüssel ausgetauscht. Dazu hatten sie sich bereits vor längerer Zeit in echt getroffen und diesen gemeinsam berechnet.
Vera möchte nun eine Nachricht verschlüsselt an Bob senden. Hierzu verwenden sie zwei Algorithmen, einen zum Verschlüsseln und einen zum Entschlüsseln. Die Algorithmen müssen genau aufeinander abgestimmt sein, sodass der Entschlüsselungsalgorithmus wirklich die Verschleierung der Verschlüsselung rückgängig macht.
Vera steckt ihre Nachricht und den geheimen Schlüssel nun in den Verschlüsselungsalgorithmus und schickt dessen Ausgabe („Chiffrat“ genannt) an Bob. Dieser empfängt das Chiffrat. Um zu entschlüsseln verwendet er ebenfalls den geheimen Schlüssel und steckt seinerseits diesen und das Chiffrat in den Entschlüsselungsalgorithmus. Die Ausgabe ist dann wieder die ursprüngliche Nachricht.
Schauen wir uns als konkretes Beispiel ein einfaches, historisches Verfahren an: Die Cäsar-Verschlüsselung (so genannt, weil sie vom römischen Kaiser Julias Cäsar verwendet wurde). Der geheime Schlüssel ist hier einfach nur ein einziger Buchstabe, etwa „E“.
Um eine Nachricht zu verschlüsseln, bestimmen wir zuerst die Position des Schlüssels im Alphabet – hier also 5. Wollen wir nun das Wort „SECUVERA“ verschlüsseln, so gehen wir Buchstabe für Buchstabe vor: Wir nehmen den jeweiligen Buchstaben und verschieben ihn um 5 Positionen im Alphabet. Aus „S“ wird „X“, aus „E“ wird „J“, aus „V“ wird „A“ (am Ende des Alphabets fangen wir einfach wieder von vorne an) usw.
Als Chiffrat erhalten wir also „XJHZAJWF“. Um es zu entschlüsseln gehen wir umgekehrt vor und verschieben die Buchstaben nun „rückwärts“ um 5 Positionen im Alphabet. Aus „X“ wird wieder „S“ und so weiter.
Aus heutiger Sicht ist dieses Verfahren natürlich völlig unsicher. Selbst mit Stift und Papier hat man in Windeseile den richtigen Schlüssel bestimmt. Man muss – je nach Alphabet – ja nur um die 26 mögliche Schlüssel durchprobieren. Dennoch findet dieses Verfahren heutzutage immer mal wieder Anwendung, etwa bei der Implementierung von Paywalls bei namhaften Nachrichtenportalen.
Das Cäsar-Verfahren verdeutlicht eins von zwei Grundprinzipien von symmetrischen Verschlüsselungsverfahren, nämlich die Substitution von Zeichen:
- Substitution: Man vertausche die Zeichen des Texts mit einem anderen Zeichen. So wie bei der Cäsar-Verschlüsselung mit Schlüssel „E“ aus einem „C“ ein „H“ wurde.
Das zweite Grundprinzip, welches häufig in symmetrischen Verfahren angewendet wird, ist die Permutation:
- Permutation: Man verschiebe die Zeichen der Nachricht an eine andere Stelle nach einer fest vorgegebenen Regel. Eine Permutation von „SECUVERA“ ist etwa „VECREAUS“ (der erste Buchstabe „S“ wurde an die letzte Stelle verschoben oder transponiert etc.). Man erstellt quasi ein Anagramm des Texts.
Selbst moderne symmetrischen Verschlüsselungsverfahren, wie der Advanced Encryption Standard (AES), basieren im Kern auf genau diesen zwei Techniken. Die geschickte Verknüpfung dieser scheinbar simplen Schritte hat sich als wahres Erfolgsrezept in der Geschichte der symmetrischen Kryptographie herausgestellt. Natürlich werden sie in viel komplexerer Art und Weise verwendet, als beim Cäsar-Verfahren und mit weiteren Techniken verknüpft, aber die Grundzutaten sind genau diese. Man bildet komplizierte Netzwerke aus diesen simplen Bausteinen, kombiniert sie geschickt und wendet sie nicht nur einmal, sondern sehr häufig hintereinander an.
Asymmetrische Verschlüsselung
So weit, so gut. Was ist jetzt mit der „asymmetrischen Geschmacksrichtung“? Schauen wir besseren Verständnis das Schlüsselaustauschproblem von symmetrischen Verfahren an. Wie einigen sich Senderin und Empfänger auf einen geheimen Schlüssel?
In unserem Beispiel haben sich Vera und Bob irgendwann mal „in echt“ getroffen, um den Schlüssel auszutauschen. Aber bereits beim simplen Surfen im Internet stellt das ein echtes Problem dar. Wer will beispielsweise beim Online-Shopping erstmal in die Innenstadt gehen müssen, um mit einem Verkäufer einen Schlüssel auszutauschen?
Lange Zeit konnte dieses Problem tatsächlich nur durch solche „Echt-Welt-Treffen“ gelöst werden. Mittlerweile gibt es aber eine Reihe kryptographischer Schlüsselaustauschverfahren, die dieses Problem für uns lösen (ein solches wurde übrigens auch verwendet, als sie diesen Artikel aufgerufen haben).
Eine ganz besonders elegante Lösung ist die asymmetrische Verschlüsselung. Hier gibt es nicht nur einen, sondern zwei Schlüssel. Ein Schlüssel wird zum Verschlüsseln und der andere zum Entschlüsseln verwendet. Der Clou: Der Schlüssel zum Verschlüsseln muss nicht geheim gehalten werden, sondern kann ohne Sicherheitseinbuße öffentlich bereitgestellt werden, weshalb er auch „öffentlicher Schlüssel“ genannt wird (und die asymmetrische Verschlüsselung häufig als „Public-Key Verschlüsselung“ bezeichnet wird). Der Schlüssel zum Verschlüsseln muss aber weiterhin geheim gehalten werden – und darf nur dem Empfänger bekannt sein. Es gibt also weiterhin einen geheimen Schlüssel.
Möchte Vera also mithilfe eines asymmetrischen Verfahrens eine Nachricht sicher an Bob verschicken, so verschlüsselt sie die Nachricht mit Bobs öffentlichem Schlüssel und Bob kann dieses Chiffrat wiederum mit seinem geheimen Schlüssel entschlüsseln.
Die Idee der asymmetrischen Verschlüsselung wurde 1976 von Whitfield Diffie und Martin E. Hellman auf die Welt losgelassen, was einer der bahnbrechendsten Momente in der Geschichte der Kryptographie war. Zuerst dachte man, solche Verfahren können nicht existieren. Auch, da Diffie und Hellman kein solches Verfahren präsentieren konnten. Die Forderung, dass man mit dem öffentlichen Schlüssel verschlüsseln kann, ohne aber den geheimen Schlüssel daraus ableiten zu können, erschien zu paradox.
Jedoch waren Ronald Rivest, Adi Shamir und Leonard Adleman fasziniert von der Idee und konnten 1977 das erste öffentlich bekannte asymmetrische Verschlüsselungsverfahren vorweisen. Dieses wurde als RSA-Verfahren bekannt und gehört zu den auch heute noch wichtigsten Verschlüsselungsverfahren (in modifizierten Varianten mit einigen Verbesserungen).
Alle asymmetrische Verfahren haben eins gemeinsam: sie basieren auf uns häufig ungewohnten und komplizierten mathematischen Operationen. Die komplexe Verwandtschaft der beiden Schlüssel ist ein Hauptgrund dafür.
Dennoch möchte ich gerne ein Beispiel besprechen, nämlich eine einfache* Version des Elgamal-Verschlüsselungsverfahrens. Dazu brauchen wir zwei Grundzutaten:
- Primzahlen: Primzahlen sind solche Zahlen, die nur durch 1 und sich selbst teilbar sind. Beispielsweise 5, 7, 31 oder auch 7901.
- Modulo: Modulo berechnet den Rest einer Division von zwei Ganzzahlen. Beispielsweise wäre 7 mod 3 = 1, da 7 gleich 2 * 3 mit Rest 1 ist. Vielen von Ihnen ist diese Operation vermutlich vom Programmieren her geläufig.
Im Folgenden rechnen wir immer modulo einer Primzahl P. Nehmen wir für das Beispiel P = 31. In „echt“ wählt man hier natürlich viel größere Zahlen. Das Bundesamt für Sicherheit in der Informationstechnik empfiehlt aktuell Zahlen mit mindestens 2000, besser jedoch 3000 Bit. Nur zur Verdeutlichung: Das sind Zahlen mit über 600 Stellen!
Zusätzlich brauchen wir eine zufällige Zahl zwischen 1 und der Primzahl, die wir„g“ nennen. Nehmen wir dafür g = 7.
Im Folgenden wird es etwas mathematisch – daher hier eine Übersichtsgrafik über das Verfahren. Werfen Sie während des Lesens der nächsten Abschnitte am besten immer wieder einen Blick hierauf, um einen besseren Überblick zu erhalten. Zusätzlich werden wir die Variablen in der Grafik im Laufe des Beispiels immer weiter mit den konkreten Zahlen füllen.
Mit P und g kann Bob wie folgt die Schlüssel berechnen:
- Geheimer Schlüssel: Bob wählt eine zufällige Zahl x zwischen 2 und P, für das Beispiel x = 2.
- Öffentlicher Schlüssel: Bob exponenziert g mit dem geheimen Schlüssel modulo der Primzahl. Hier also g² = 7² = 49 mod 31 = 18. Insgesamt ist der öffentliche Schlüssel also (P, g, gˣ) = (31, 7, 18). Wir schicken also auch die verwendete Primzahl P und g mit.
Den öffentlichen Schlüssel kann Bob unverschlüsselt an Vera schicken oder in einem öffentlich zugänglichen Schlüsselverzeichnis ablegen. Um zu verschlüsseln muss Vera folgenden Algorithmus befolgen:
- Sie muss ihre Nachricht als eine Zahl zwischen 1 und 31 kodieren. Das wirkt auf den ersten Blick befremdlich, ist aber kein Problem, da digitale Daten sowieso nichts anderes als Binärzahlen sind. P = 31 ist dafür eine sehr kleine Obergrenze, in echt würde man natürlich größere Zahlen verwenden, um entsprechend große Dateien kodieren zu können.
- Nehmen wir an, dass Vera die „Nachricht“ M = 11 verschlüsseln möchte.
- Vera wählt eine zufällige Zahl zwischen 1 und P, etwa y = 4 und berechnet gʸ = 7⁴ = 14 mod 31.
- Vera nimmt gˣ aus dem öffentlichen Schlüssel und berechnet (gˣ) ʸ = 18⁴ = 10 mod 31
- Als letzten Schritt berechnet Vera (gˣ) ʸ * M = 10 * 11 mod 31 = 17.
- Das komplette Chiffrat besteht aus zwei Teilen: (gʸ, (gˣ) ʸ * M) = (14, 17).
Was ist hier nun passiert? Im Prinzip hat Vera ihre Nachricht bloß auf (etwas ungewohnte) Art und Weise mit der Zahl gˣʸ multipliziert. Diese Multiplikation muss Bob jetzt rückgängig machen.
Aber wie? Erstmal muss Bob ebenfalls gˣʸ berechnen. Die Zahl y kennt er zwar nicht, aber – im Gegensatz zu Vera und allen anderen – kennt er den geheimen Schlüssel und dieser ist x! Die Zahl gʸ kriegt Bob praktischerweise im Chiffrat mitgeliefert. Er geht also folgendermaßen vor:
- Entnehme gʸ aus dem Chiffrat und berechne mithilfe des geheimen Schlüssels (gʸ) ˣ = gˣʸ = 10 mod 31.
- Als nächstes muss Bob eine Zahl a finden, sodass a * gˣʸ = a * 10 = 1 mod 31. Er muss also quasi „1 / gˣʸ“ berechnen, bloß modulo P. Im konkreten Fall ist die gesuchte Zahl die 28, denn 10 * 28 = 280 = 9 * 31 + 1 und damit 10 * 28 = 1 mod 31. (Normales Teilen, wie wir es gewohnt sind, funktioniert hier übrigens aufgrund der Modulo-Rechnung nicht. Aber es gibt Algorithmen, die diesen Schritt effizient berechnen können)
- Bob nimmt den zweiten Teil des Chiffrats, also die 17. Wir erinnern uns, dass 17 = 10 * M mod 31. Nun rechnet Bob a * 17 = 28 * 10 * M = 1 * M = M mod 31.
Und damit hat Bob nun die Nachricht M = 11 von Alice entschlüsselt. Puh! Das war gar nicht mal so einfach. 😊 Die Sicherheit dieses Verfahrens hängt übrigens eng damit zusammen, dass nach aktuellem Forschungsstand kein effizienter Algorithmus bekannt ist, der modulo P aus gˣ das x berechnen kann. Dieses mathematische Problem ist als „Diskreter Logarithmus“ bekannt.
Fakt ist leider, dass asymmetrische Verfahren aufgrund ihrer komplexen Mathematik wesentlich ineffizienter zu berechnen sind, als symmetrische Verfahren. Auch wenn beispielsweise die Operationen des Elgamal-Verfahrens relativ simpel erscheinen, so müssen doch ständig riesige Zahlen zufällig gewählt und vergleichsweise teure Modulo-Rechenoperationen durchgeführt werden.
Trotz ihrer Eleganz sind asymmetrische Verfahren also nicht für alle Probleme die richtige Lösung. Ein Paradebeispiel ist aber die Verschlüsselung von E-Mails – die öffentlichen Schlüssel der secuvera MitarbeiterInnen dafür finden sie übrigens auf dieser Seite.
Welche Geschmacksrichtung darf’s denn sein? (Oder: Symmetrisch vs. Asymmetrisch)
Welche Art der Verschlüsselung sollte man jetzt verwenden? Nun, das kommt auf den Anwendungsfall und die zur Verfügung stehenden Verfahren und Technologien an. Symmetrische Verfahren bieten den großen Vorteil, dass sie ziemlich schnell zu berechnen sind. Asymmetrische Verfahren sind aufgrund der komplexen Mathematik leider sehr viel langsamer, lösen aber das Schlüsselaustauschproblem.
Eine häufige Lösung: Man kombiniert einfach beides. Man verwendet erstmal ein asymmetrisches Verfahren, um ein Geheimnis auszutauschen und verwendet dieses Geheimnis hinterher als geheimen Schlüssel für ein symmetrisches Verfahren, um den richtigen Datenaustausch abzusichern. „The best of both worlds“, sozusagen: Das Schlüsselaustauschproblem ist gelöst und wir profitieren von der schnellen Berechenbarkeit des symmetrischen Verfahrens.
Aber warum ist das jetzt alles sicher? Und was muss ich alles geheim halten?
Die erste Frage möchte ich etwas nach hinten verschieben, denn sie verdient einen eigenen Beitrag. Festzuhalten sei aber schonmal, dass die Länge der Schlüssel eine entscheidende Rolle spielt. Das ist auch sehr einfach einzusehen: Ist der Schlüssel sehr kurz, so kann ein Computer einfach alle möglichen Schlüssel ausprobieren (Brute Force). Aber die Schlüssellänge ist nicht der einzige Faktor. Und ein Verschlüsslungsverfahren ist nicht erst dann unsicher, wenn es einfach ist, den geheimen Schlüssel zu bestimmen. Aktuelle Informationen zu empfehlenswerten Schlüssellängen und Verschlüsselungsverfahren gibt übrigens die technische Richtlinie 02102 vom BSI.
Die zweite Frage kann etwas leichter beantwortet werden: Ausschließlich der geheime Schlüssel muss geheim gehalten werden (und die zu sichernden Daten, natürlich!). Aufmerksamen LeserInnen wird aufgefallen sein, dass ich niemals davon gesprochen habe, dass die Verfahren geheim gehalten werden müssen. Ganz im Gegenteil. Die Verfahren selbst können und sollten öffentlich bekannt sein. Warum „sollten“? Nun, auch das verdient einen eigenen Artikel.
Im nächsten Blog-Eintrag wollen wir uns aber erstmal um die Frage kümmern, warum Verschlüsselungsverfahren eigentlich sicher sind.
/Dr. Björn Kaidel
*: Das führt für einen Blog-Eintrag eigentlich zu weit, aber bitte implementieren Sie das Elgamal-Verfahren nicht so, wie hier dargestellt. Die hier präsentierte Variante hat zwar den Vorteil, dass sie noch relativ verständlich ist, aber leider ist sie nicht zu 100% sicher. Zwar lässt sich nach aktuellem Stand der Forschung der geheime Schlüssel nicht berechnen, es ist aber möglich, Rückschlüsse über den Inhalt von Chiffraten zu ziehen. Für eine wirklich sichere Implementierung muss man ein kleines bisschen tiefer in die mathematische Trickkiste greifen.