Dies ist eine alte Version des Dokuments!
Das One-Time-Pad ist ein symmetrisches Verschlüsselungsverfahren, das als informationstheoretisch sicher1) bewiesen ist. Diese Eigenschaft besagt, dass die Verschlüsselung - bei korrekter Verwendung - selbst mit unendlicher Rechenleistung nicht geknackt werden kann.
Die Verschlüsselung und Entschlüsselung mittels One-Time-Pad ist relativ simpel. Eine Klartext-Nachricht M wird über ein exklusives Oder mit einem Schlüssel K verknüpft und erzeugt so den verschlüsselten Ciphertext C. In Kurzschreibweise bedeutet das C = M ⊕ K.
Nun wollen wir den Text „proggen.org“ (M) verschlüsseln. Den Schlüssel K dafür wählen wir dabei komplett zufällig, er muss nichtmals aus druckbaren Zeichen bestehen. Die Byte-Werte sind deshalb als hexadezimale Zahlen angegeben.
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
---|---|---|---|---|---|---|---|---|---|---|---|
M (ASCII) | p | r | o | g | g | e | n | . | o | r | g |
M (Hex) | 0x70 | 0x72 | 0x6f | 0x67 | 0x67 | 0x65 | 0x6e | 0x2e | 0x6f | 0x72 | 0x67 |
⊕ | |||||||||||
K | 0x21 | 0xff | 0x12 | 0x7c | 0x00 | 0xa9 | 0x30 | 0x54 | 0xb3 | 0x96 | 0xbf |
= | |||||||||||
C | 0x51 | 0x8d | 0x7d | 0x1b | 0x67 | 0xcc | 0x5e | 0x7a | 0xdc | 0xe4 | 0xd8 |
Ohne den Schlüssel zu kennen, liefert der Ciphertext C keinerlei Informationen über die Klartext-Nachricht!
Um den Text wieder zu entschlüsseln wird das Verfahren einfach auf den Kopf gestellt, also M = C ⊕ K.
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
---|---|---|---|---|---|---|---|---|---|---|---|
C | 0x51 | 0x8d | 0x7d | 0x1b | 0x67 | 0xcc | 0x5e | 0x7a | 0xdc | 0xe4 | 0xd8 |
⊕ | |||||||||||
K | 0x21 | 0xff | 0x12 | 0x7c | 0x00 | 0xa9 | 0x30 | 0x54 | 0xb3 | 0x96 | 0xbf |
= | |||||||||||
M (Hex) | 0x70 | 0x72 | 0x6f | 0x67 | 0x67 | 0x65 | 0x6e | 0x2e | 0x6f | 0x72 | 0x67 |
M (ASCII) | p | r | o | g | g | e | n | . | o | r | g |
Nun können wir auch zeigen wieso ein Bruteforce-Angriff nicht möglich ist. Zu jeder möglichen Klartext-Nachricht gibt es nämlich einen Schlüssel der sie aus dem Ciphertext erzeugt. Nochmals obiges Beispiel, jedoch mit falschem Schlüssel:
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
---|---|---|---|---|---|---|---|---|---|---|---|
C | 0x51 | 0x8d | 0x7d | 0x1b | 0x67 | 0xcc | 0x5e | 0x7a | 0xdc | 0xe4 | 0xd8 |
⊕ | |||||||||||
K | 0x21 | 0xff | 0x4d | 0x7c | 0x00 | 0xff | 0x30 | 0x54 | 0xec | 0x96 | 0xbf |
= | |||||||||||
M (Hex) | 0x70 | 0x72 | 0x30 | 0x67 | 0x67 | 0x33 | 0x6e | 0x2e | 0x30 | 0x72 | 0x67 |
M (ASCII) | p | r | 0 | g | g | 3 | n | . | 0 | r | g |
Wir haben hier also eine plausible, teilweise sogar korrekte, aber trotzdem insgesamt falsche Nachricht entschlüsselt.
Hinweis:
Die allgemeine Definition des One-Time-Pads sieht eine zeichenweise Modulo-Addition von Klartext und Schlüssel innerhalb des Alphabets vor, ähnlich wie es bei der Cäsar-Chiffre der Fall ist. Da dies bei binären Daten aber genau einem exklusiven Oder entspricht, beschränken wir uns hier auf diesen Fall.
Um tatsächlich als informationstheoretisch sicher zu gelten, werden folgende Bedingungen an den Schlüssel gestellt:
Sobald nur eine einzige dieser Bedingungen verletzt wird, geht diese Eigenschaft verloren und Entschlüsselungs-Angriffe sind möglich!
Hier kommen wir auch zum großen Problem des One-Time-Pads. Beide Parteien müssen den verwendeten Schlüssel kennen. Dessen Übertragung stellt deshalb vor allem bei großen Datenmengen ein ganz neues Problem dar. Deshalb spielt das One-Time-Pad in der Praxis auch eine relativ geringe Rolle.
Wird auch nur eine Bedingung des One-Time-Pads verletzt, entstehen verschiedene Angriffsmöglichkeiten.
Pseudo-Zufallszahlengeneratoren wechseln auf Basis eines Seeds ihren internen Zustand und produzieren aufgrund eines deterministischen Berechnungsverfahren „Zufallszahlen“. Kann man den internen Zustand des Zufallszahlengenerators zurückrechnen, können alle folgenden Zufallszahlen - und damit der restliche Schlüssel - ebenfalls deterministisch berechnet werden. Auch wenn die Zahl der möglichen Werte für den Seed theoretisch sehr groß ist, kann man diese in vielen Fällen stark einschränken.
Beispiel:
Geht man von einem 64-bit Unix-Timestamp als Seed aus, können die möglichen Werte von 264 (18.446.744.073.709.551.616) auf ca. 235 (31.536.000.000) eingeschränkt werden, sofern man das korrekte Jahr errät. Noch immer eine schwierige, jedoch lösbare Aufgabe für moderne Rechner.
Moderne Programmiersprachen bieten oft Klassen oder Bibliotheken zur Generierung von kryptografisch sicheren Zufallszahlen, wie etwa random_device
in C++11 oder java.security.SecureRandom
in Java. Bei der Implementierung von sicherheitskritischen Anwendungen sollte man sich aber auf jeden Fall über die interne Funktionsweise des Generators informieren.
Wird der gleiche Schlüssel mehrere (n) Male verwendet, spricht man von einem n-Time-Pad. Nun stellen wir die Gleichungen für die Verschlüsselung von 2 Nachrichten mit dem selben Schlüssel auf:
C1 = M1 ⊕ K
C2 = M2 ⊕ K
Kombiniert man nun die beiden verschlüsselten Texte:
C1 ⊕ C2
erhält man als Formel:
(M1 ⊕ K) ⊕ (M2 ⊕ K)
Da das exklusive Oder kommutativ ist, kann die Gleichung folgendermaßen umgeformt werden:
(K ⊕ K) ⊕ (M1 ⊕ M2)
Jede beliebige Zahl die über ein exklusives Oder mit sich selbst verbunden wird ergibt 0 (x ⊕ x = 0), daher:
(0) ⊕ (M1 ⊕ M2)
Nach kurzer Überlegung erkennt man auch, dass jede beliebige Zahl die über ein exklusives Oder mit 0 verbunden ist, wieder die gleiche Zahl ergibt (x ⊕ 0 = x):
(M1 ⊕ M2)
Der geheime Schlüssel ist komplett aus der Gleichung verschwunden!
Errät man nun einen Teil einer Klartext-Nachricht, kann durch ein weiteres exklusives Oder und den gleichen Rechenregeln wie zuvor die jeweils andere ebenfalls teilweise entschlüsselt werden:
(M1 ⊕ M2) ⊕ M1
Löst man obige Gleichung auf, bleibt die entschlüsselte Nachricht M2 übrig. Erhält man für M2 plausiblen Inhalt, weist dies auf einen korrekten Versuch hin. Hat man mehrere Nachrichten zur Entschlüsselung bzw. Validierung, erleichtert dies den Vorgang natürlich enorm.
Um das n-Time-Pad zu knacken geht man also folgendermaßen vor:
Je größer die entschlüsselten Teile der Nachrichten, desto leichter fällt es natürlich auf den restlichen Inhalt zu schließen.
Tipp zum Erraten des Inhalts:
Bei komplett unbekannten Inhalt kann das Raten sehr mühsam sein. Abhilfe schaffen allgemeine Wörter wie z.B. „ und “ und „ oder “ bzw. in Englisch „ and “ und vor allem „ the “. Die Leerzeichen vor und nach den Wörtern sind beabsichtigt und liefern den Inhalt der anderen Nachrichten an diesen Stellen „gratis“ mit!
Bei genügend großen n kann auch eine Frequenzanalyse angewendet werden, bei der über die Häufigkeit der Hex-Bytes an einer Stelle und der Häufigkeit von Buchstaben in einer Sprache auf den Inhalt geschlossen wird.
Ist der zu verschlüsselnde Text länger als der Schlüssel selbst und wird der Schlüssel dann wieder von Beginn verwendet, degeneriert das One-Time-Pad zur Vigenère-Cipher mit all ihren Schwächen und praktisch den gleichen Angriffsmöglichkeiten wie das n-Time-Pad.