Kryptoanalyse

Die Kryptoanalyse (in neueren Publikationen auch Kryptanalyse) bezeichnet im ursprünglichen Sinne Methoden und Techniken, um ohne Kenntnis des Schlüssels oder des Verschlüsselungsverfahrens Informationen aus Geheimtexten zu gewinnen. Diese Informationen können sowohl der verwendete Schlüssel als auch der Originaltext sein. Heutzutage bezeichnet der Begriff Kryptoanalyse allgemeiner die Analyse von kryptographischen Verfahren (nicht nur zur Verschlüsselung) mit dem Ziel, diese entweder zu „brechen“, d. h. ihre Schutzfunktion aufzuheben bzw. zu umgehen, oder ihre Sicherheit nachzuweisen und zu quantifizieren. Kryptoanalyse ist damit das „Gegenstück“ zur Kryptographie. Beide sind Teilgebiete der Kryptologie.

Steganalyse

Analog zur Kryptoanalyse, welche auf die Kryptographie fokussiert ist, kann man die Steganalyse als „Gegenstück“ zur Steganografie verstehen. Im Gegensatz jedoch zur Kryptoanalyse, wo ein kryptografischer Inhalt vorliegt und analysiert bzw. gebrochen werden soll, wird bei der Steganalyse zunächst nur mit der Annahme gearbeitet werden, dass sich in einem Trägermedium eine versteckte Information befindet. Erst wenn diese Annahme erhärtet werden konnte, wird versucht, die eigentlichen Informationen zu extrahieren. Dabei können auch Methoden aus der Kryptoanalyse verwendet werden.

Die Sicherheit der Steganographie beruht darauf, dass Dritte ihre Verwendung nicht bemerken. Selbst wenn sie davon wissen, sollen Dritte den eigentlichen Inhalt nicht im Klartext auslesen können.

Entschlüsselung und Entzifferung In der Kryptologie haben die Begriffe „Entzifferung“ und „Entschlüsselung“ unterschiedliche Bedeutung: Als (befugte) Entschlüsselung bezeichnet man das Verfahren, mit Hilfe des bekannten Schlüssels den Geheimtext wieder in den Klartext zurückzuverwandeln und so die Nachricht lesen zu können. Die (unbefugte) Entzifferung hingegen ist die Kunst, dem Geheimtext ohne Kenntnis des Schlüssels die Nachricht zu entringen. Statt des Verbs entziffern wird in der Kryptanalyse auch der Ausdruck „brechen“ oder umgangssprachlich auch „knacken“ verwendet.

In der Archäologie hingegen, also wenn es um die Analyse einer alten, nicht mehr bekannten Schrift geht, werden die Begriffe Entschlüsselung und Entzifferung oft als Synonyme verwendet.

Methoden der Kryptoanalyse Ein wichtiger Ansatz der Kryptoanalyse ist es, alle verfügbaren Informationen über das untersuchte Verfahren, seine Parameter und die geschützten Daten in die Analyse miteinzubeziehen. Diese Informationen können öffentlich sein, plausiblen Vermutungen entstammen oder gezielt in Erfahrung gebracht werden (z. B. durch Social Engineering). Die Art der verfügbaren Informationen und ihre Kontrolle darüber wird in verschiedene Angriffsszenarien eingeteilt (siehe Modelle und Aussagen zur Sicherheit) und qualifizieren die Relevanz des Angriffes bzw. der Aussage zur Sicherheit.

Bevor mechanische Apparate wie die Enigma oder Computer der Kryptographie ermöglichten, Nachrichten zu Pseudo-Zufallsfolgen zu verwürfeln, war die Statistik die stärkste Waffe, um Nachrichten zu entziffern. Solange ein Mensch die Texte von Hand verschlüsselt, muss der verwendete Algorithmus einfach genug bleiben, um die Nachricht in vertretbarer Zeit fehlerfrei umzusetzen. Diese Verschlüsselungsverfahren sind meist durch die Statistik angreifbar. Mit ihr wird die Häufigkeit bestimmter Zeichen und Zeichenfolgen bestimmt. Mit dem Wissen über die Gesetzmäßigkeiten einer Sprache können Buchstaben und Wörter zugeordnet werden und der Klartext rekonstruiert werden.

Seitdem Computer durch ihre Geschwindigkeit und Präzision die statistischen Bindungen in einem verschlüsselten Text auf fast Null reduzieren, müssen neue Analysetechniken verwendet werden, den Verschlüsselungsalgorithmus aufzudecken, eine Schwachstelle im Algorithmus auszunutzen (wie auch schon die Statistik Schwachstellen nutzte) und den Schlüssel zu rekonstruieren, mit dem die Nachricht verschlüsselt wurde. Dazu werden häufig komplizierte mathematische Theorien und Verfahren angewendet, z. B. aus der Algebra oder der Stochastik.

Nachfolgend einige wichtige Angriffs- und Analysemethoden: Brute-Force-Methode Alle möglichen Schlüssel werden nacheinander durchprobiert. Die Reihenfolge wird gegebenenfalls nach der Wahrscheinlichkeit ausgewählt, falls man Informationen darüber hat, wie der Schlüssel gebildet wurde. Diese Methode ist bei modernen Verschlüsselungsverfahren nur sinnvoll, wenn man von einem schwachen Schlüssel oder einer sehr ungleichen Wahrscheinlichkeitsverteilung bei der Schlüsselwahl ausgehen kann. Schon auf handelsüblichen Computern (Stand 2008) können mehrere Millionen Schlüssel pro Sekunde ausprobiert werden. Wörterbuchangriff Wird angewendet, wenn der Schlüssel aus einem Passwort abgeleitet wurde. Alle Passwörter aus speziell zu diesem Zweck angefertigten Passwortsammlungen werden nacheinander durchprobiert. Die Reihenfolge wird gegebenenfalls nach der Wahrscheinlichkeit ausgewählt. Diese Methode ist bei modernen Verschlüsselungsverfahren nur sinnvoll, wenn von der Verwendung eines relativ schwachen Passwortes ausgegangen werden kann. Auch das Ausprobieren aller denkbaren Wörter ist ohne Weiteres möglich. Bei einem Wortschatz von 50.000 Wörtern pro Sprache können selbst auf handelsüblichen Rechnern dutzende Sprachen innerhalb weniger Sekunden ausprobiert werden. Ein einzelnes Wort als Schlüssel ist daher sehr unsicher. Ebenso können alle möglichen Zeichenfolgen bis zu einer bestimmten Länge probiert werden, die durch Rechenleistung und verfügbare Zeit begrenzt wird. Seitenkanalattacke Der Angreifer kann einen Ver- oder Entschlüsselungsvorgang von außen beobachten und versucht, außer dem Klartext, dem Chiffrat oder dem Schlüssel zunächst auch andere Daten zu erfassen und daraus Informationen über den verwendeten Algorithmus und Schlüssel zu gewinnen. Hierfür kommen zum Beispiel in Frage: die Dauer der Verschlüsselung (Timing Attack), der zeitliche Verlauf des Stromverbrauchs eines Chips (Simple/Differential Power Analysis), Berechnungsfehler aufgrund extremer Umgebungsbedingungen (Differenzielle Fehleranalyse), eine Verzweigungsanalyse (Simple Branch Prediction Analysis) oder die Abstrahlung elektromagnetischer Wellen (TEMPEST-Attack). Lineare Kryptoanalyse Diese Methode wurde 1993 von Mitsuru Matsui veröffentlicht. Das Verfahren basiert darauf, lineare Beziehungen zwischen Klartext, Schlüssel und Geheimtext zu finden, die überzufällig häufig zutreffen. Differenzielle Kryptoanalyse Die differentielle Kryptoanalyse wurde 1991 von Eli Biham und Adi Shamir entwickelt um DES anzugreifen. Dieser Angriffsversuch schlug fehl, da die differenzielle Analyse der NSA bei der Entwicklung von DES bereits bekannt war. Bei der differenziellen Analyse werden Klartextpaare mit gewissen Unterschieden (den Differenzen) verschlüsselt, um aus den Differenzen der Chiffrate den geheimen Schlüssel des symmetrischen Kryptosystems abzuleiten. Man-in-the-middle-Angriff Der Angreifer befindet sich zwischen zwei Kommunikationspartnern und kann alle Nachrichten mithören und sogar verändern oder neue Nachrichten einfügen. Algebraische Angriffsmethoden Falls der kryptografische Algorithmus auf einer geeigneten algebraischen Struktur operiert bzw. durch geeignete algebraischen Operationen dargestellt werden kann, können ggf. spezielle Eigenschaften der algebraischen Struktur ausgenutzt werden, um den Algorithmus erfolgreich anzugreifen. Oft lässt sich das Brechen des Verfahrens auf das Lösen eines Gleichungssystems über der Struktur oder einer aussagenlogischen Formel zurückführen. Solche Angriffe werden vor allem auf asymmetrische Verfahren angewendet, die häufig auf endlichen Gruppen operieren. Aber auch Stromverschlüsselungsverfahren und einige Blockverschlüsselungsverfahren, wie z. B. AES, können algebraisch modelliert und so mehr oder weniger erfolgreich angegriffen werden. Angriffe durch Gitterbasenreduktion Viele kryptographische Verfahren lassen sich angreifen, indem man einen kurzen Vektor in einem bestimmten Gitter ermittelt. Diese Angriffsmethode wird bei Kryptoverfahren, die auf dem Gittern oder dem Rucksackproblem basieren, wie z. B. NTRU oder dem Merkle-Hellman-Kryptosystem, eingesetzt, kann aber auch – in Kombination mit algebraischen Angriffsmethoden – bei anderen asymmetrischen Kryptoverfahren, wie z. B. RSA angewendet werden.

Modelle und Aussagen zur Sicherheit

Der Nachweis der Sicherheit kryptographischer Verfahren kann nur selten strikt, d. h. im Sinne der Informationstheorie geführt werden. Häufiger wird die Sicherheit von Verfahren im Sinne der Komplexitätstheorie nachgewiesen, d. h. sie wird auf mehr oder weniger akzeptierte Annahmen über die Schwierigkeit von Berechnungsproblemen (z. B. NP-vollständige Probleme, Faktorisierung oder diskreten Logarithmus) oder anderer kryptographischer Verfahren zurückgeführt. In manchen Fällen werden auch theoretische Modelle zu Idealisierung von Bestandteilen des Verfahrens (z. B. Random-Oracle-Modell) oder der Möglichkeiten potentieller Angreifer (z. B. generische Algorithmen) zugrunde gelegt; daraus gewonnene Erkenntnisse über die Sicherheit eines Verfahrens sind jedoch immer im Kontext des Modells zu sehen und werden zum Teil kontrovers bewertet.

Bei der Analyse der Sicherheit kryptographischer Verfahren und den daraus resultierenden Aussagen zur Sicherheit werden verschiedene Angriffs- und Sicherheitsmodelle zugrunde gelegt. So hängt die Qualität einer Aussage zur Sicherheit eines Verfahren gegen bestimmte Angreifer von den angenommenen Angriffszielen und dem Angriffsszenario ab.

Ziele Aussagen zur Sicherheit eines kryptographischen Verfahrens beziehen sich in der Regel auf bestimmte Angriffsziele. Die möglichen Ziele hängen von der Art des kryptographischen Verfahrens ab. Für alle kryptographischen Verfahren, die einen geheimen Schlüssel verwenden, ist die Ermittlung des geheimen Schlüssels das weitreichendste Ziel eines Angriffes, da damit die Sicherheit des Verfahrens komplett ausgehebelt wird.

Für Verschlüsselungsverfahren sind weiterhin folgende Angriffsziele relevant:

Entschlüsselung, d. h. die Ermittlung des Klartextes. Der Angreifer muss zu einem Chiffretext und zwei potenziellen Klartexten ermitteln, welches der richtige Klartext ist. Falls dies nicht effizient (d. h. in Polynomialzeit) möglich ist, wird diese Eigenschaft als Semantic Security oder Ciphertext Indistinguishability bezeichnet. Semantic Security wird sowohl für asymmetrische als auch für symmetrischen Kryptoverfahren betrachtet. Nur probabilistische Verschlüsselungsverfahren können diese Eigenschaft besitzen. Der Angreifer versucht, einen Chiffretext so zu verändern, dass der zugehörige neue Klartext, den man bei Entschlüsselung des veränderten Chiffretextes erhalten würde, mit dem ursprünglichen Klartext in einer bestimmten (dem Angreifer bekannten) Relation steht. Zum Beispiel könnte es sein Ziel sein, den Chiffretext so zu verändern, dass eine im Klartext angegebene Zahl (z. B. ein Kaufpreis) sich verringert. Ein Verschlüsselungsverfahren, das gegen solche Angriffe sicher ist, weil ein Angreifer bei einer Manipulation des Chiffretextes keine Kontrolle über die resultierende Veränderung im Klartext besitzt, nennt man Non-Malleable (zu deutsch Nicht Verformbar). Der Angreifer versucht, einen gültigen Chiffretext zu erzeugen, ohne den dazugehörigen Klartext zu kennen. Falls dies nicht effizient (d. h. in Polynomialzeit) möglich ist, wird diese Eigenschaft als Plaintext Awareness bezeichnet. Nur Verschlüsselungsverfahren, bei denen die Chiffretexte eine definierte Struktur (Redundanz) besitzen, können diese Eigenschaft besitzen.