Kryptoanalyse: Unterschied zwischen den Versionen

Keine Bearbeitungszusammenfassung
 
(Eine dazwischenliegende Version von einem anderen Benutzer wird nicht angezeigt)
Zeile 1: Zeile 1:
== Einführung ==
Wie sicher ein Verschlüsselungsverfahren ist, zeigt sich erst, wenn jemand ernsthaft versucht, es zu brechen. Genau das untersucht die Kryptoanalyse.
Die Kryptoanalyse bezeichnet Methoden und Techniken, um Informationen aus [[Kryptographie|verschlüsselten]] Texten zu gewinnen. Diese Informationen können sowohl der verwendete Schlüssel als auch der Originaltext sein. Kryptoanalyse ist damit das „Gegenstück“ zur [[Kryptographie]].


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.
==Definition==
Die '''Kryptoanalyse''' ist die Lehre von den Methoden, mit denen man aus einem Geheimtext ohne Kenntnis des Schlüssels den Klartext oder den Schlüssel gewinnt. Zusammen mit der [[Kryptographie]] bildet sie die Kryptologie.


== Methoden ==
Ein Angriff geht nach dem [[Kryptographie#Prinzip von Kerckhoffs|Prinzip von Kerckhoffs]] davon aus, dass der Angreifer das Verfahren kennt. Geheim ist nur der Schlüssel. Angriffe unterscheiden sich darin, was der Angreifer außerdem weiß:
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.
* '''nur den Geheimtext''' (englisch: ciphertext-only): Der Angreifer hat lediglich mitgelesen.
* '''Klartext und Geheimtext''' (englisch: known-plaintext): Der Angreifer kennt zu einem Teil des Geheimtextes den Klartext.


[[Kryptographie#Klassische_Kryptographie|Klassische 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. Bekannte Verfahren sind das der Kasiski-Test oder der Koinzedenzindex.
==Schlüsselraum==
Der '''Schlüsselraum''' ist die Menge aller Schlüssel, die bei einem Verfahren möglich sind. Seine Größe ist die Anzahl dieser Schlüssel.


Ein heutiger Computer kann etwa 10 Millionen Schlüssel pro Sekunde prüfen. Durch verteilte Systeme wie das von distributed.net sind sogar weit über 100 Milliarden Überprüfungen möglich. Damit sind klassische Verschlüsselungsverfahren im Zeitalter der digitalen Informationsverarbeitung durch einfaches Ausprobieren (Brute-Force) leicht zu knacken.
* Besteht der Schlüssel aus <math>b</math> Bit, enthält der Schlüsselraum <math>2^b</math> Schlüssel.
* Besteht der Schlüssel aus <math>l</math> Buchstaben, enthält der Schlüsselraum <math>26^l</math> Schlüssel.


In [[Kryptographie#Moderne_Kryptographie|modernen Verschlüsselungsverfahren]] spielen statistische Verfahren kaum noch eine Rolle. 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.
Ein großer Schlüsselraum ist notwendig, damit ein Verfahren sicher ist. Er reicht allein aber nicht aus: Die [[Monoalphabetische Substitution|monoalphabetische Substitution]] hat einen riesigen Schlüsselraum und wird trotzdem mit der [[Häufigkeitsanalyse]] in kurzer Zeit gebrochen.


Nachfolgend eine Auswahl vom Angriffs- und Analysemethoden:
==Brute-Force-Angriff==
Bei einem '''Brute-Force-Angriff''' (englisch für „rohe Gewalt“) probiert der Angreifer alle Schlüssel des Schlüsselraums der Reihe nach aus, bis ein sinnvoller Klartext entsteht. Mit genug Zeit gelingt der Angriff bei fast jedem Verfahren. Im ungünstigsten Fall muss der Angreifer alle Schlüssel prüfen, im Durchschnitt die Hälfte. Die Ausnahme ist das [[One-Time-Pad]]: Dort liefert das Durchprobieren jeden denkbaren Klartext und damit keine Information.


* Brute-Force-Methode: Alle möglichen Schlüssel werden nacheinander durchprobiert.
Schutz bietet nur ein Schlüsselraum, der so groß ist, dass das Durchprobieren auch mit den schnellsten Rechnern viel zu lange dauert.
* Wörterbuchangriff: Alle Schlüssel aus speziell zu diesem Zweck angefertigten Passwortsammlungen werden nacheinander durchprobiert.
* 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).
* 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.


== Kopfzeile ==
==Known-Plaintext-Angriff==
Bei einem '''Known-Plaintext-Angriff''' kennt der Angreifer zu einem Stück Geheimtext den zugehörigen Klartext, zum Beispiel eine Anrede oder einen festen Dateianfang. Daraus berechnet er den Schlüssel oder einen Teil davon und versucht, damit den Rest zu entschlüsseln.
 
Besonders gefährdet sind Verfahren, bei denen sich der Schlüssel direkt aus Klartext und Geheimtext ausrechnen lässt und auch für den Rest des Textes gilt, weil er sich wiederholt. Das trifft auf die [[Caesar-Verschlüsselung]], das [[Vigenère-Verfahren]] und die [[XOR-Verschlüsselung]] mit wiederholtem Schlüssel zu. Beim [[One-Time-Pad]] verrät ein bekanntes Stück Klartext dagegen nur den Schlüssel an dieser Stelle.
 
==Wörterbuchangriff==
Bei einem '''Wörterbuchangriff''' probiert der Angreifer nicht alle Möglichkeiten aus, sondern nur wahrscheinliche: Wörter aus Wörterbüchern, Namen, Tastaturmuster und bekannte Passwörter. Menschen wählen selten zufällige Schlüssel, deshalb ist dieser Angriff oft viel schneller als ein Brute-Force-Angriff.
 
Der wichtigste Einsatz ist der Angriff auf Passwörter, die als Hashwerte gespeichert sind (siehe [[Hashfunktion#Passwörter|Hashfunktion]]).
 
==Weitere Angriffe==
* Die [[Häufigkeitsanalyse]] nutzt aus, dass Buchstaben in einer Sprache unterschiedlich oft vorkommen.
* Der [[Kasiski-Test]] und der [[Koinzidenzindex]] ermitteln die Schlüssellänge beim Vigenère-Verfahren.
* Beim [[Man-in-the-Middle-Angriff]] schaltet sich der Angreifer unbemerkt zwischen zwei Partner.
* Angriffe auf das [[RSA-Verfahren]] versuchen, den RSA-Modul in seine Primfaktoren zu zerlegen (siehe [[Primfaktorzerlegung]]).
 
==Beispiele==
===Schlüsselraum und Dauer eines Brute-Force-Angriffs berechnen===
Angenommen, ein Rechner prüft eine Milliarde Schlüssel pro Sekunde. Die Tabelle zeigt, wie lange er im ungünstigsten Fall braucht. Ein Jahr hat rund 31,5 Millionen Sekunden.
 
{| class="wikitable"
! Verfahren !! Schlüssel !! Größe des Schlüsselraums !! Dauer bei einer Milliarde Schlüsseln pro Sekunde
|-
| [[Caesar-Verschlüsselung]] || Verschiebung 0 bis 25 || <math>26</math> || sofort
|-
| [[Vigenère-Verfahren]] mit einem Schlüsselwort aus 6 Buchstaben || 6 Buchstaben || <math>26^6 = 308\,915\,776</math> || 0,309 Sekunden
|-
| Schlüssel aus 56 Bit || 56 Bit || <math>2^{56} \approx 7{,}2 \cdot 10^{16}</math> || etwa 2,3 Jahre
|-
| [[Monoalphabetische Substitution]] || Ersetzungstabelle für 26 Buchstaben || <math>26! \approx 4{,}0 \cdot 10^{26}</math> || etwa <math>1{,}3 \cdot 10^{10}</math> Jahre
|-
| Schlüssel aus 128 Bit || 128 Bit || <math>2^{128} \approx 3{,}4 \cdot 10^{38}</math> || etwa <math>1{,}1 \cdot 10^{22}</math> Jahre
|}
 
Die monoalphabetische Substitution zeigt, dass diese Rechnung nur eine obere Grenze liefert: Mit der Häufigkeitsanalyse gelingt der Angriff trotz des großen Schlüsselraums in Minuten.
 
===Schlüssel aus bekanntem Klartext ermitteln===
Eve fängt diesen Geheimtext ab: <code>DWHHK XKXSE NOADA JQJOI KNCAJ</code>
 
Sie weiß, dass er mit der [[Caesar-Verschlüsselung]] entstanden ist und dass jede Nachricht mit <code>HALLO</code> beginnt. Ein einziges Buchstabenpaar genügt:
* erster Geheimtextbuchstabe <code>D</code> mit dem Wert 3
* erster Klartextbuchstabe <code>H</code> mit dem Wert 7
* Schlüssel: <math>k = (3 - 7) \bmod 26 = -4 \bmod 26 = 22</math>
 
Mit <math>k = 22</math> entschlüsselt Eve die ganze Nachricht: <code>HALLO BOBWI RSEHE NUNSM ORGEN</code>
 
Dasselbe gelingt bei der XOR-Verschlüsselung, siehe [[XOR-Verschlüsselung#Schlüssel aus bekanntem Klartext berechnen|Schlüssel aus bekanntem Klartext berechnen]].
 
===Passenden Angriff auswählen===
{| class="wikitable"
! Lage !! Geeigneter Angriff
|-
| Geheimtext einer Caesar-Verschlüsselung, Schlüssel unbekannt || Brute-Force-Angriff: Der Schlüsselraum ist winzig.
|-
| Langer Geheimtext einer monoalphabetischen Substitution || Häufigkeitsanalyse
|-
| Langer Geheimtext des Vigenère-Verfahrens || Kasiski-Test für die Schlüssellänge, danach Häufigkeitsanalyse je Teiltext
|-
| Geheimtext und ein Stück des Klartextes sind bekannt || Known-Plaintext-Angriff
|-
| Gestohlene Tabelle mit Hashwerten von Passwörtern || Wörterbuchangriff
|-
| Schlüsselaustausch über einen Kanal, den der Angreifer kontrolliert || Man-in-the-Middle-Angriff
|}
 
[[Kategorie:Kryptologie]]
[[Kategorie:AHR I Informatik LK]]