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

→ Hauptartikel: 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

→ Hauptartikel: Sicherheitseigenschaften kryptografischer Verfahren

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.

Bei digitalen Signaturen und Message Authentication Codes (MAC) betrachtet man üblicherweise das Ziel, eine Signatur bzw. einen MAC zu einer neuen Nachricht zu erzeugen. Falls die Nachricht beliebig sein kann, nennt man dies Existential Forgery. Falls es möglich sein muss, die Nachricht frei zu wählen, wird dies als Selective Forgery bezeichnet.

Angriffsszenarien

In der Forschung wird Kryptoanalyse heute meistens angewendet auf Verfahren, deren Spezifikation bekannt ist. Dies entspricht Kerckhoffs’ Prinzip, wonach die Sicherheit eines Verfahrens nur auf der Geheimhaltung des Schlüssels beruhen sollte. Die Geheimhaltung des Algorithmus (Security through obscurity) verhindert eine Analyse durch die Fachwelt und wird daher heute als eher kontraproduktiv für die Sicherheit angesehen. Geheime kryptographische Verfahren wurden in der Vergangenheit wiederholt aufgedeckt, analysiert und gebrochen (z. B. bei GSM, Mifare-Karten oder der Verschlüsselung kommerzieller DVDs). Geheime Verfahren werden heute seltener eingesetzt, vorwiegend im militärischen Bereich und für den Schutz von Verschlusssachen (z. B. Chiasmus oder Libelle), sowie in geschlossenen kommerziellen Systemen, wie z. B. beim Pay-TV, bei der Zutrittskontrolle (z. B. Mifare) oder der Digitalen Rechteverwaltung.

Man unterscheidet verschiedene Angriffsszenarien auf ein Verschlüsselungssystem (nach Stärke geordnet):

Ciphertext Only

Manchmal wird dieses Szenario auch als Known Ciphertext bezeichnet. Der Angreifer kennt einen oder mehrere Geheimtexte und versucht mit deren Hilfe, auf den Klartext beziehungsweise den Schlüssel zu schließen. Darüber hinaus besitzt er jedoch, im Gegensatz zu den nachfolgenden Fällen, keine weiteren Informationen.

Probable Plaintext (wahrscheinlicher Klartext)

Der Angreifer besitzt Geheimtext und hat Grund zu der Annahme, dass dieser bestimmte Wortgruppen oder markante Wörter enthält, mit denen eine Analyse versucht werden kann. Die bekannten Wörter werden als Crib bezeichnet.

So konnte etwa die Enigma mit einem anfänglichen Wissen geknackt werden, dass am Anfang zweimal der Schlüssel für den Rest der Nachricht (verschlüsselt mit einem unbekannten Tagesschlüssel) und anschließend das Datum und der Wetterbericht gesendet wurde. Man konnte damit den Tagesschlüssel rekonstruieren. Diese Methode wird auch Mustersuche genannt.

Known Plaintext (bekannter Klartext)

Der Angreifer besitzt Geheimtext(e) und die/den zugehörigen Klartext(e) (Crib). Beide werden benutzt, um den Schlüssel zu ermitteln.

Ein aktuelles Beispiel ist die Mitte 2006 veröffentlichte Verbesserung eines seit 2001 bekannten Angriffes auf das Wired Equivalent Privacy (WEP) Protokoll, das zur Authentisierung und Verschlüsselung von Wireless LAN eingesetzt wird. Der optimierte Angriff nutzt aus, dass Teile der verschlüsselten Nachricht – die Header des 802.11-Protokolls – vorhersagbar sind.

Chosen Plaintext (selbst gewählter Klartext)

Hierbei kann der Angreifer (Kryptoanalytiker) die zu verschlüsselnden Klartexte frei wählen und hat Zugang zu den entsprechenden Geheimtexten. Gegenüber dem Angriff mit bekanntem Klartext hat diese Variante den Vorteil, dass der Angreifer gezielt den Klartext variieren und die dadurch entstehenden Veränderungen im Geheimtext analysieren kann. Typischerweise schiebt der Angreifer dem Opfer die zu verschlüsselnden Nachrichten so unter, dass dem Opfer die Selektion durch eine andere Person nicht bewusst wird.

Eine besonders mächtiges Angriffsszenario ist die adaptive chosen plaintext attack. Bei dieser kann der Angreifer jeweils die bisher erhaltenen Kryptotexte analysieren und je nach Ergebnis einen neuen Klartext zum Verschlüsseln wählen (daher „adaptive“).

Das ist das minimale Szenario bei asymmetrischer Verschlüsselung. Da der Verschlüsselungsschlüssel öffentlich ist, kann der Angreifer nach Belieben Nachrichten verschlüsseln.

Chosen Ciphertext (selbst gewählter Geheimtext)

Der Angreifer hat temporär die Möglichkeit, Geheimtexte seiner Wahl zu entschlüsseln. Dies kann durch Zugriff auf ein Hardwaresystem durch einen Einbruch geschehen; es fallen jedoch auch der Zugriff auf unvorhergesehene Nebeneffekte, wie verschiedene Fehlermeldungen nach erfolgreicher bzw. erfolgloser Entschlüsselung darunter. Ein Beispiel dafür ist Bleichenbachers Angriff auf PKCS#1.

Bei einigen Kryptosystemen, etwa bei Rabin, ist er dann in der Lage, aus den gewonnenen Datenpaaren den geheimen Schlüssel zu ermitteln, mit dem die Geheimtexte verschlüsselt waren.

→ Hauptartikel: Chosen-Ciphertext-Angriff

Adaptively Chosen Ciphertext (adaptiv selbst gewählter Geheimtext)

Ähnlich zum vorhergehenden Angriff, allerdings hat der Angreifer längere Zeit Zugang zum System und kann nach jeder Analyse gezielt einen neuen Kryptotext zum Entschlüsseln wählen.

Chosen Text (selbst gewählter Text)

Kombination aus Chosen Plaintext und Chosen Ciphertext.

Adaptive Chosen Text (adaptiv selbst gewählter Text)

Kombination aus Adaptive Chosen Plaintext und Adaptive Chosen Ciphertext.

Bekannte Projekte

Bekanntes Projekt der Kryptoanalyse war die Entschlüsselung des deutschen Funkverkehrs im Zweiten Weltkrieg, siehe

• Kryptanalyse der Enigma
• Kryptanalyse der Lorenz-Maschine

Siehe auch

• Crib
• Depth (Kryptologie)
• Kiss (Kryptologie)
• Rubber-hose cryptanalysis

Literatur

• David Kahn: The Codebreakers: The Comprehensive History of Secret Communication from Ancient Times to the Internet ISBN 978-0-684-83130-5
• Edgar Allan Poe: Der Goldkäfer (Erzählung von 1843, in der eine Geheimschrift systematisch entschlüsselt wird)
• Klaus Schmeh: Codeknacker gegen Codemacher. Die faszinierende Geschichte der Verschlüsselung. Verlag: W3l; 2. Auflage, 2007, ISBN 978-3-937137-89-6
• Simon Singh: Geheime Botschaften. ISBN 3-423-33071-6
• Douglas R. Stinson: Cryptography - Theory and Practice. ISBN 1-58488-206-9
• A. J. Menezes, P. C. van Oorschot und S. A. Vanstone: Handbook of Applied Cryptography
• Mark Stamp und Richard M. Low: Applied Cryptanalysis: Breaking Ciphers in the Real World, 2007, Wiley-Interscience

Weblinks

• Überblick und Geschichte der Kryptologie
• Kryptographische Begriffe
• CrypTool − Open-Source-Programm für Kryptographie und Kryptoanalyse