Beweisbare Sicherheit in der Kryptographie

Nachdem ich es schon länger in dieser Krypto-Kolumne verspreche, ist es endlich an der Zeit, die Frage zu beantworten, warum Verschlüsselungsverfahren eigentlich sicher sind.

Lange Zeit glich dieses Thema einem Katz-und-Maus-Spiel: Verfahren waren nur „sicher“, weil man davon ausging, dass sie es sind, da niemand einen Angriff kannte. Nachdem dann doch ein effizienter Angriff bekannt wurde, versuchte man das Verfahren zu reparieren oder gleich ein neues zu entwerfen… und das Spiel ging von vorne los.

Teilweise ist das heute immer noch so. Für viele Verfahren, wie etwa dem AES Verschlüsselungsverfahren oder den SHA-Hashfunktionen, gibt es eigentlich keine endgültigen Sicherheitsgarantien.

Verstehen Sie mich bitte nicht falsch. Ich will nicht sagen, dass diese Verfahren schlecht oder unsicher sind. Ganz im Gegenteil. Sie wurden von führenden Experten entworfen, halten seit Jahren oder sogar Jahrzehnten jeglichen Angriffsversuchen stand und es gibt keinen Grund zur Vermutung, dass sie unsicher sind. Dennoch könnten hier riesige Sicherheitslücken klaffen, die wir nur deswegen nicht kennen, weil die richtigen Angriffstechniken noch nicht gefunden wurden. Beispielsweise war genau das bei den verbreiteten Verfahren RC4 und MD5 der Fall und sie können nicht mehr als sicher angesehen werden.

Zufriedenstellend war und ist dieser „Das Verfahren ist sicher, weil wir aktuell keinen Angriff darauf kennen“-Ansatz also nicht. In der modernen Kryptographie verfolgt man daher nun den Weg, die Sicherheit der Verfahren mathematisch zu beweisen. D.h. man nimmt nicht nur an, dass ein Verfahren sicher ist, sondern weißt formal nach, dass es tatsächlich die gewünschten Sicherheitseigenschaften besitzt.

Eine unumgängliche Voraussetzung dafür ist es, genau zu definieren, was „Sicherheit“ im konkreten Fall bedeutet. Diese Frage wurde im letzten Beitrag für Verschlüsselungsverfahren beleuchtet und einige mögliche Sicherheitsmodelle besprochen.

Nachdem man das Sicherheitsmodell festgelegt hat, muss man nun beweisen, dass das Verfahren auch tatsächlich dessen Anforderungen erfüllt. Man beweist, dass es keinen plausiblen Angriff gibt, der das Verfahren im Sinne des Sicherheitsmodells brechen kann.

Hierbei verfolgt man zwei unterschiedliche Ansätze:

1. Informationstheoretische Sicherheit
2. Komplexitätstheoretische Sicherheit

Hinter diesen sperrigen Begriffen verbergen sich zwei verschiedene Ansichten darüber, wie „perfekt“ die Sicherheit sein soll.

Informationstheoretische Sicherheit

Bei der informationstheoretischen Sicherheit fordert man, dass es tatsächlich unmöglich sein soll, das Verfahren zu brechen.  Man verlangt Sicherheit gegen alle denkbaren Angriffe, selbst gegen ineffiziente und unplausible Angriffe, wie etwa solche, die potentiell unbeschränkte Laufzeit benötigen.

Dies wirkt auf den ersten Blick wie eine unmögliche Forderung, aber tatsächlich ist diese Art von Sicherheit erreichbar.

Erinnern Sie sich noch an das Cäsar-Verschlüsselungsverfahren? Kurze Erinnerung: Der geheime Schlüssel ist ein einziger Buchstabe und man verschiebt die Buchstaben des Klartextes abhängig von der Position des Schlüssels im Alphabet. Soll der Klartext „SECUVERA“ mit dem Schlüssel „E“ verschlüsselt werden, so wird jeder Buchstabe um 5 Positionen im Alphabet verschoben, da „E“ der 5. Buchstabe im Alphabet ist. Aus „S“ wird „X“, aus „E“ wird „J“, aus „V“ wird „A“ (am Ende des Alphabets fangen wir einfach wieder von vorne an) usw. – das Ergebnis ist das Chiffrat „XJHZAJWF“.

Der so genannte „One-Time-Pad“ funktioniert sehr ähnlich:

• Der geheime Schlüssel ist eine zufällige Buchstabenkette, die genau so lang ist, wie der Klartext.
• Jeder Buchstabe des Klartexts wird mit dem entsprechenden Buchstaben im Schlüssel „cäsar-verschlüsselt“.
• Die Entschlüsselung funktioniert dann analog und man „cäsar-entschlüsselt“ jeden Buchstaben des Chiffrats mit dem jeweiligen Buchstaben des Schlüssels.

Angenommen, wir wollen das Wort „APFEL“ mit dem Schlüssel „BHTIU“ verschlüsseln. Dann gehen wir folgendermaßen vor:

• Der erste Buchstabe „A“ des Klartexts wird mit dem ersten Buchstaben „B“ des Schlüssels zu „C“ verschlüsselt.
• Der zweite Buchstabe „P“ des Klartexts wird mit dem zweiten Buchstaben „H“ des Schlüssels zu „X“ verschlüsselt.

Und so weiter: „F“ mit „T“ zu „Z“, „E“ mit „I“ zu „N“ und „L“ mit „U“ zu „G“. Das Chiffrat ist damit „CXZNG“.

Dieses Verfahren ist trotz seiner Einfachheit informationstheoretisch sicher, wenn man folgende Bedingungen beachtet: Der Schlüssel …

• … muss tatsächlich genau so lang sein, wie der Klartext.
• … muss echt zufällig sein.
• … darf nur ein einziges Mal zum Verschlüsseln verwendet werden.

Hält man sich an diese Regeln, so kann das Verfahren nicht gebrochen werden. Dies wurde von Claude Shannon bereits 1949 bewiesen, lange bevor man z.B. überhaupt an Public-Key Kryptographie dachte.

Den formalen Beweis können wir an dieser Stelle natürlich nicht im Detail durchgehen, aber es gibt einige sehr intuitive Argumente dafür:

Die Einschränkung, dass der Schlüssel nur ein einziges Mal verwendet wird, schließt viele „raffinierte“ Angriffstechniken aus. Beispielsweise sind nicht einmal Known-Plaintext-Angriffe möglich, da eben nur ein einziges Klartext-Chiffrat-Paar existiert.

Der eigentliche Clou ist aber: jedes Chiffrat kann zu jedem Klartext der gleichen Länge entschlüsselt werden. Oder anders gesagt, es gibt für jeden Klartext einen Schlüssel, sodass das Chiffrat damit zu diesem Klartext entschlüsselt wird.

Zurück zum Beispiel: Dort hatten wir Wort „APFEL“ zu „CXZNG“ verschlüsselt. Probieren wir mal ein paar andere Schlüssel beim Entschlüsseln aus:

• Der Schlüssel „PWLGR“ entschlüsselt „CXZNG“ zum Klartext „MANGO“.
• Der Schlüssel „AOHZB“ liefert als Klartext „BIRNE“.
• Der Schlüssel „VCHCB“ liefert als Klartext „GURKE“.
• Und so weiter… für jeden Klartext, der aus fünf Buchstaben besteht, können wir einen passenden Schlüssel finden.

Somit führt selbst das Durchprobieren aller Schlüssel (Brute-Force-Angriff) nicht zum Ziel. Der Angreifer wird eine riesige Menge an möglichen Klartexten zur Auswahl haben. Da der Schlüssel nur ein einziges Mal verwendet wird, hat er auch keinen Kontext zur Verfügung, aus dem er weitere Informationen ziehen könnte, um den richtigen Klartext zu bestimmen. Da der Schlüssel echt zufällig gezogen wurde, ist jeder Klartext gleich wahrscheinlich. Somit ist es ihm nicht möglich zu sagen, welcher Klartext der richtige Inhalt des Chiffrats ist.

Dieser extrem hohe Grad an Sicherheit bringt aber einige Nachteile mit sich:

• Für jeden Klartext muss ein neuer Schlüssel echt zufällig erstellt werden. Allein das ist schon rechenintensiv, aber der Schlüssel muss auch noch zwischen den beiden Kommunikationspartnern ausgetauscht werden.
• Der Schlüssel muss genau so lang sein, wie der Klartext. Stellen Sie sich mal vor, sie wollen eine 1 TB Festplatte verschlüsseln. Dann brauchen sie erstmal eine zweite 1 TB Festplatte, um den Schlüssel überhaupt speichern zu können.
• Jeder Schlüssel darf nur exakt einmal verwendet werden. Sobald der gleiche Schlüssel auch nur zwei Mal verwendet wird, kann das Verfahren erfolgreich durch statistische Methoden angegriffen werden.

Diese Nachteile sorgen dafür, dass der One-Time-Pad nur in wenigen Situationen wirklich plausibel einsetzbar ist. Eine der wenigen praktischen Anwendungen fand das Verfahren beim „roten Telefon“ zwischen den USA und der Sowjetunion im kalten Krieg.

Leider konnte Claude Shannon auch beweisen, dass diese Nachteile nicht speziell den One-Time-Pad betreffen. Jedes informationstheoretisch sichere Verschlüsselungsverfahren weißt diese Nachteile auf. Für bestimmte Verfahrenstypen ist informationstheoretische Sicherheit sogar unerreichbar. Das gilt beispielsweise für alle Arten von Public-Key Kryptographie, da sich aus dem Public Key immer mit einem Brute-Force Angriff der geheime Schlüssel berechnen lässt.

Komplexitätstheoretische Sicherheit

Aufgrund der Nachteile des informationstheoretischen Ansatzes musste man einen weiteren Weg finden: Man erlaubt, dass es möglicherweise Angriffstechniken gibt, die erfolgreich das Verfahren brechen, fordert aber, dass deren Erfolgswahrscheinlichkeit vernachlässigbar klein ist oder die Angriffe eben nicht plausibel sind, weil sie nicht effizient durchgeführt werden können.

Ein Beispiel ist der Brute-Force-Angriff: Es ist wie gesagt möglich, jedes Public-Key Verfahren dadurch zu brechen. Wählt man aber den Schlüssel groß genug, so ist der Angriff nicht mehr plausibel durchführbar.

Ein komplexitätstheoretischer Sicherheitsbeweis hier sagt also nicht aus, dass es unmöglich ist, das Verfahren zu brechen, sondern dass alle möglichen Angriffe entweder nicht in plausibler Zeit ausgeführt werden können oder aber eine vernachlässigbar kleine Erfolgswahrscheinlichkeit haben. Gegen alle anderen Angriffe bietet das Verfahren den gewünschten Schutz (nach Sicherheitsmodell!). Damit hat man dann insbesondere gezeigt, dass es keine effizienten Angriffe gibt.

Als Wegbereiter dieses Ansatzes gilt das Papier „Probabilistic Encryption“ von Goldwasser und Micali von 1984, die dieses Vorgehen erstmalig für Verschlüsselungsverfahren bis in die Tiefe beleuchteten.

Für diese Sicherheitsbeweise verwendet man Erkenntnisse aus der Komplexitätstheorie. Die Komplexitätstheorie beschäftigt sich damit, wie schwer es ist, Berechnungsprobleme zu lösen und untersucht die Zusammenhänge zwischen den Problemen. Genauso einen Zusammenhang zwischen einem schwierigen Berechnungsproblem und der Sicherheit des Krypto-Verfahrens weißt man durch Sicherheitsbeweise nach.

Dazu beweist man: Wenn es einen Angriff auf das Verschlüsselungsverfahren gibt, dann kann dieser verwendet werden, um ein schwieriges Berechnungsproblem zu lösen. Da das Berechnungsproblem aber schwierig ist und nicht effizient gelöst werden kann, muss folglich auch der Angriff ineffizient sein. Die Beweistechnik ist als „Reduktion“ bekannt: Man „reduziert“ die Sicherheit des Verschlüsselungsverfahrens auf die Schwierigkeit eines Berechnungsproblems.

Ein in der Kryptographie häufig dafür verwendetes Problem ist das Faktorisierungsproblem: Jede positive ganze Zahl kann als Multiplikation von Primzahlen dargestellt werden. Primzahlen sind die Zahlen, die nur durch die 1 und sich selbst teilbar sein. Ein paar Beispiele: 6 = 2 * 3, 15 = 3 * 5, 2.625 = 3 * 5 * 5 * 5 * 7 usw.
Diese Primzahlen, die multipliziert die eigentliche Zahl ergeben, werden Primfaktoren genannt. Die Primfaktoren von 15 sind also 3 und 5. Das Berechnungsproblem ist nun: Gegeben eine natürliche Zahl, berechne die Primfaktoren dieser Zahl.

Das mag vergleichsweise simpel klingen, aber bis heute kennt man kein gutes und effizientes Lösungsverfahren. Die Sicherheit einer Vielzahl von kryptographischen Verfahren basiert auf diesem und ähnlichen Problemen.

Ein großes Problem an diesem Ansatz kann ich aber nicht verschweigen: Wir wissen nicht, ob es überhaupt schwierige Berechnungsprobleme gibt. Vielleicht gibt es für jedes Problem einen effizienten Algorithmus, den wir nur (noch) nicht kennen. Tatsächlich ist das eine der größten ungelösten und schwierigsten Forschungsfragen der theoretischen Informatik (vielleicht haben Sie ja schonmal vom „P vs. NP Problem“ gehört?).

Was bedeutet das für den Ansatz der „beweisbaren Sicherheit“? Die informationstheoretische Sicherheit ist davon nicht betroffen (aber wie gesagt praktisch meist nicht einsetzbar). Bezüglich der komplexitätstheoretischen Sicherheit müssen sich KryptographInnen nach aktuellem Forschungsstand aber leider weiterhin auf Annahmen verlassen.

Das gilt auch für das Faktorisierungsproblem. Niemand weiß, ob es tatsächlich schwierig ist, Zahlen zu faktorisieren. Neue Forschungsergebnisse in Sachen Quantencomputer bieten hier sogar Grund zur Sorge (ein Thema für einen anderen Beitrag).

In gewisser Weiße sind wir wieder beim Anfang angekommen und müssen uns auf Annahmen verlassen. Das klingt jetzt vermutlich enttäuschend, aber dennoch bietet dieser Ansatz einige große Vorteile:

• Im Gegensatz zum „historischen Vorgehen“ kann man die Annahmen genau benennen. Man weiß exakt unter welchen Bedingungen das Verfahren sicher ist und auf was man sich verlässt.
• Durch die präzisen Definitionen der Sicherheitsmodelle weiß man genau, welche Sicherheitseigenschaften geboten werden (und welche nicht!).
• Die verwendeten Berechnungsprobleme sind nicht nur für KryptographInnen interessant, sondern auch für ForscherInnen aus der Informatik, Mathematik und weitere Gebieten. Die Annahmen werden somit von mehr ForscherInnen untersucht, als es bei einem einzelnen Verschlüsselungsverfahren jemals der Fall sein würde. Das Faktorisierungsproblem wird beispielsweise schon seit Jahrtausenden erforscht. Das untermauert einerseits die Glaubwürdigkeit der Annahme und sorgt andererseits dafür, dass die Sicherheit von kryptographischen Verfahren kein „Exotenproblem“ ist. Diese Annahmen sind somit auch realistischer als die alten Annahmen vom Typ „Das Verfahren ist sicher, weil wir keine Angriffe darauf kennen“.
• Der komplette Ansatz der beweisbaren Sicherheit hat dafür gesorgt, dass Zusammenhänge in der Kryptographie wesentlich klarer wurden und das Verfahren besser miteinander verglichen werden können.

Es spricht also vieles dafür, diesen Ansatz zu verfolgen. Natürlich gibt es aber auch Gegenargumente. Die kryptographische Forschung wurde dadurch wesentlich komplexer, aber auch tiefgehender. Unter den strengen mathematischen Forderungen litt die Effizienz der Verfahren stark, aber gerade hier gab es sehr große Fortschritte.

Ein großes Problem ist aber, dass auf der Jagd nach Verfahren mit immer mehr Zusatzeigenschaften leider auch Annahmen eingeführt wurden, für die es wenige bis keine Begründungen gibt (und auf die das „Interessant für viele Fachgebiete“ Argument auch nicht zutrifft). Teilweise wurden Verfahren unter Annahmen als sicher „bewiesen“, die man wenig später widerlegen konnte. Bei einigen dieser Verfahren fand man dann auch effiziente Angriffe. Als Außenstehender ist es schier unmöglich, hier den Überblick zu behalten. Umso wichtiger ist es, dass man sich bei der Wahl der Krypto-Verfahren auf Expertenrat verlässt.

Das Drumherum

Eins darf man auch nicht aus den Augen verlassen: Sicherheitsbeweise beziehen sich nur auf die Verfahren an sich. Sie machen keinerlei Aussage darüber, ob sie richtig implementiert werden, ob sichere Hardware verwendet wird, ob die Schlüssel tatsächlich ordentlich berechnet und gespeichert werden oder ob eine guter Zufallszahlengenerator verwendet wird. Sie bieten auch keinen Schutz dagegen, dass übereifrige „Verbesserungen“ der Verfahren zu schwerwiegenden Sicherheitsproblemen führen. Unter anderem deswegen sollte man wann immer nur möglich gut untersuchte und erprobte Krypto-Standardbibliotheken verwenden.

Trotz der Probleme und Gegenargumente war der Schritt hin zur beweisbaren Sicherheit ein riesiger Fortschritt für die Kryptographie und gilt als de-facto Standard. Die positiven Seiten und Effekte überwiegen deutlich. Und wer weiß, vielleicht werden neue Erkenntnisse in der Komplexitätstheorie eines Tages dafür sorgen, dass wir uns nicht mehr auf Annahmen verlassen müssen.

/Dr. Björn Kaidel

PS: Häufig liest man über das sehr bekannte RSA-Verschlüsselungsverfahren Sätze wie „Da man nicht effizient faktorisieren kann, ist das RSA Verfahren sicher“. Tatsächlich wissen wir nach aktuellem Stand der Forschung aber nicht, ob das stimmt. Fakt ist: Könnte man effizient faktorisieren, so wäre auch das RSA Verfahren gebrochen. Es ist aber immer noch unklar, ob es nicht auch andere Möglichkeiten gibt, dass RSA Verfahren zu brechen. Oder etwas formaler: Es ist bisher niemandem gelungen, die Sicherheit des RSA Verfahrens auf das Faktorisierungsproblem zu reduzieren.