Chosen-plaintext attack

Die Kryptoanalyse (in neueren Publikationen auch: Kryptanalyse) bezeichnet im ursprünglichen Sinne das Studium von Methoden und Techniken, um Informationen aus verschlüsselten Texten 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. Diese Methode ist auch bei modernen Verschlüsselungsverfahren sinnvoll, wenn von der Verwendung eines relativ schwachen Passwortes ausgegangen werden kann. Schon auf handelsüblichen Computern (Stand 2008) können ohne Weiteres mehrere Millionen Schlüssel pro Sekunde ausprobiert werden.

• Wörterbuchangriff: Alle Schlüssel aus speziell zu diesem Zweck angefertigten Passwortsammlungen werden nacheinander durchprobiert. Die Reihenfolge wird gegebenenfalls nach der Wahrscheinlichkeit ausgewählt. Diese Methode ist auch bei modernen Verschlüsselungsverfahren sinnvoll, wenn von der Verwendung eines relativ einfachen Passwortes ausgegangen werden kann.

Auch das Ausprobieren aller denkbaren Wörter ist ohne Weiteres möglich. Bei einem aktiven 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.

• Seitenkanalattacke: Der Angreifer 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 (Differential Fault Analysis), 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 auf der linearen Annäherung an den wahrscheinlichsten Schlüssel zum Brechen von Blockverschlüsselungsverfahren.

• Differenzielle Kryptoanalyse: (siehe ebenda)

• Man-in-the-middle-Angriff: (siehe ebenda)

• SAT-Angriff: Der Verschlüsselungsalgorithmus wird auf eine SAT-Instanz reduziert, dann werden die 1-literalen Klauseln für den Klartext und den Ciphertext hinzugefügt. Anschließend wird die Instanz mit einem SAT-Solver gelöst und die Werte für die Key-Bits extrahiert.

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 zurückgeführt (z. B. NP-vollständige Probleme, Faktorisierung oder diskreten Logarithmus). 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 kontrovers diskutiert.

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 dem angenommenen Angriffszielen und dem Angriffsszenario ab.

Ziele

Aussagen zur Sicherheit eines kryptographischen Verfahrens beziehen sich in der Regel auf ein bestimmtes Ziel. 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, da damit die Sicherheit das Verfahren komplett ausgehebelt wird.

Für Verschlüsselungsverfahren sind weiterhin folgende Ziele 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 bezeichnet. Semantic Security wird nur für asymmetrische 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 auf Verfahren angewendet, deren Spezifikation bekannt sind. 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, vorwiegend im militärischen und nachrichtendienstlichen Bereich, sowie in geschlossenen kommerziellen Systemen, wie z. B beim Pay-TV oder der Digitalen Rechteverwaltung eingesetzt.

Man unterscheidet verschiedene Angriffsszenarien auf ein Kryptosystem:

Ciphertext Only

Manchmal wird diese Methode 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.

Probable Plaintext

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

Der Angreifer besitzt Geheimtext(e) und die/den zugehörigen Klartext(e). 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.

Angriff mit frei wählbarem Klartext (chosen-plaintext attack)

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.

So wurden z. B. im Zweiten Weltkrieg von der britischen Royal Navy gezielt Minenfelder verlegt, die den Angriff mit frei wählbarem Klartext ermöglichten. Die deutsche Aufklärung übermittelte die Daten der Minenfelder (Position, Größe, Verlegungszeit) verschlüsselt und per Funk an ihr Hauptquartier. Indem die Parameter der Minenfelder bei jeder neuen Verlegung leicht variiert wurden, gaben die Briten dem deutschen Militär den Klartext ihrer Meldungen vor. Die verschlüsselten Nachrichten wurden abgehört und konnten mit den bekannten Klardaten verglichen werden.

Eine besonders mächtiges Angriffsszenario ist die Adaptively Chosen Plaintext Attacke. 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“).

Angriff mit frei wählbarem Geheimtext (chosen-ciphertext attack)

(siehe ebenda)

Adaptive Chosen Ciphertext

Ä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

Kombination aus Chosen Plaintext und Chosen Ciphertext.

Adaptive Chosen Text

Kombination aus Adaptive Chosen Plaintext und Adaptive Chosen Ciphertext.

Siehe auch

• Kryptologie
• CrypTool Weltweit verbreitetste Lernsoftware zum Thema Kryptographie und Kryptoanalyse, mit der etliche der oben genannten Analyseverfahren ausprobiert werden können. Enthält umfangreiche Online-Hilfe, Open-Source.

Literatur

• David Kahn: The Codebreakers: The Comprehensive History of Secret Communication from Ancient Times to the Internet ISBN 978-0684831305
• 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-3937137896
• Simon Singh: Geheime Botschaften. ISBN 3-423-33071-6
• Bernhard Esslinger: "CrypTool-Skript: Kryptographie und Mathematik", 200 Seiten, Englische Version, Teil des freien Open-Source-Paketes CrypTool (siehe http://www.cryptool.org).
• 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 Anwendungen der Kryptologie (mit CrypTool); PDF; 3,8 MB
• Überblick und Geschichte der Kryptologie
• Kryptographie mit Anwendungen PDF; 1,4 MB
• Kryptographische Grundlagen und Terminologie PDF; 0,2 MB
• Kryptographische Begriffe
• Kryptographische Terminologie PDF; 0,2 MB
• Kryptographie von Tomy Imboden PDF; 0,8 MB