cryptography

Mehrfache Verwendung eines One-Time-Pads

Posted on 12 June 2012

In diesem Artikel soll dargestellt werden, wie sich die mehrfache Verwendung desselben Schlüssels auf die Sicherheit eines One-Time-Pads auswirkt.

Das One-Time-Pad

Das One-Time-Pad (OTP) ist ein einfaches Verschlüsselungsverfahren, das perfekte Sicherheit bietet und nicht gebrochen werden kann, auch nicht mit der gesamten weltweiten Rechenkraft. Perfekte Sicherheit bedeutet, dass der Geheimtext keine zusätzlichen Informationen über den Klartext liefert. (Es erfüllt auch das Shannon Theorem, das besagt, dass der Schlüsselraum größer oder gleich dem Nachrichtenraum sein muss.)

Der Schlüssel beim One-Time-Pad weist die gleiche Länge wie der Klartext auf. Der Schlüssel muss absolut zufällig generiert worden sein (normale Zufallszahlengeneratoren sind hierfür nicht ausreichend). Der Schlüssel muss geheim bleiben (nur Sender und Empfänger dürfen ihn kennen) und darf nie (auch nicht teilweise) wiederverwendet werden. Nach dem Einsatz muss der Schlüssel sicher vernichtet werden.

Beim Verschlüsseln wird der Klartext mit dem Schlüssel (der die gleiche Länge wie der Klartext besitzt) Exklusiv-Oder-verknüpft (XOR) und ergibt den Geheimtext. Dieser Geheimtext wird dem Empfänger übermittelt. Zum Entschlüsseln nimmt der Empfänger den erhaltenen Geheimtext und verknüpft ihn per Exklusiv-Oder (XOR) mit dem Schlüssel. Der Empfänger erhält so den Klartext.

Mehrfache Verwendung des Schlüssels

Im nachfolgenden Beispiel wird gezeigt, wie sich die mehrfache Verwendung eines Schlüssels katastrophal auf die Sicherheit auswirkt und wie so eine Verschlüsselung gebrochen werden kann. Dabei ist der Klartext der 14 Nachrichten ein um Umlaute reduzierter Auszug aus Faust I von Johann Wolfgang von Goethe:

  1. So gib mir auch die Zeiten wieder,
  2. Da ich noch selbst im Werden war,
  3. Da sich ein Quell gedrangter Lieder
  4. Ununterbrochen neu gebar,
  5. Da Nebel mir die Welt verhullten,
  6. Die Knospe Wunder noch versprach,
  7. Da ich die tausend Blumen brach,
  8. Die alle Taler reichlich fullten.
  9. Ich hatte nichts und doch genug:
  10. Den Drang nach Wahrheit und die Lust am Trug.
  11. Gib ungebandigt jene Triebe,
  12. Das tiefe, schmerzenvolle Gluck,
  13. Des Hasses Kraft, die Macht der Liebe,
  14. Gib meine Jugend mir zuruck!

Jede Zeile ist dabei eine unabhängige Nachricht, die jeweils mit demselben Schlüssel codiert wurde.

Dies ist der Schlüssel in Hexadezimaldarstellung (er ist 45 Bytes lang, genauso lang wie Nachricht 10, die längste der 14 Nachrichten):

07 05 B6 2E E1 D4 7F 89 8F D7 02 C1 64 BD E6 FF ED 77 6C 1E E2 07 8E 77 E8 91 59 A9 FE 68 51 95 BF F3 13 4E 0A A1 B0 1E 89 FA 14 11 F7

Zur Verschlüsselung werden alle 14 Nachrichten mit dem gleichen Schlüssel Exklusiv-Oder-verknüpft (XOR, ⊕): ci = mi ⊕ k, für i = 1, 2, …, 14. ci ist der Geheimtext mit der Nummer i, mi ist der Klartext mit der Nummer i, k ist der Schlüssel.

Das Ergebnis sind folgende Geheimtexte:

  1. 54 6A 96 49 88 B6 5F E4 E6 A5 22 A0 11 DE 8E DF 89 1E 09 3E B8 62 E7 03 8D FF 79 DE 97 0D 35 F0 CD DF
  2. 43 64 96 47 82 BC 5F E7 E0 B4 6A E1 17 D8 8A 9D 9E 03 4C 77 8F 27 D9 12 9A F5 3C C7 DE 1F 30 E7 93
  3. 43 64 96 5D 88 B7 17 A9 EA BE 6C E1 35 C8 83 93 81 57 0B 7B 86 75 EF 19 8F E5 3C DB DE 24 38 F0 DB 96 61
  4. 52 6B C3 40 95 B1 0D EB FD B8 61 A9 01 D3 C6 91 88 02 4C 79 87 65 EF 05 C4
  5. 43 64 96 60 84 B6 1A E5 AF BA 6B B3 44 D9 8F 9A CD 20 09 72 96 27 F8 12 9A F9 2C C5 92 1C 34 FB 93
  6. 43 6C D3 0E AA BA 10 FA FF B2 22 96 11 D3 82 9A 9F 57 02 71 81 6F AE 01 8D E3 2A D9 8C 09 32 FD 93
  7. 43 64 96 47 82 BC 5F ED E6 B2 22 B5 05 C8 95 9A 83 13 4C 5C 8E 72 E3 12 86 B1 3B DB 9F 0B 39 B9
  8. 43 6C D3 0E 80 B8 13 EC AF 83 63 AD 01 CF C6 8D 88 1E 0F 76 8E 6E ED 1F C8 F7 2C C5 92 1C 34 FB 91
  9. 4E 66 DE 0E 89 B5 0B FD EA F7 6C A8 07 D5 92 8C CD 02 02 7A C2 63 E1 14 80 B1 3E CC 90 1D 36 AF
  10. 43 60 D8 0E A5 A6 1E E7 E8 F7 6C A0 07 D5 C6 A8 8C 1F 1E 76 87 6E FA 57 9D FF 3D 89 9A 01 34 B5 F3 86 60 3A 2A C0 DD 3E DD 88 61 76 D9
  11. 40 6C D4 0E 94 BA 18 EC ED B6 6C A5 0D DA 92 DF 87 12 02 7B C2 53 FC 1E 8D F3 3C 85
  12. 43 64 C5 0E 95 BD 1A EF EA FB 22 B2 07 D5 8B 9A 9F 0D 09 70 94 68 E2 1B 8D B1 1E C5 8B B 3A B9
  13. 43 60 C5 0E A9 B5 0C FA EA A4 22 8A 16 DC 80 8B C1 57 08 77 87 27 C3 16 8B F9 2D 89 9A 0D 23 B5 F3 9A 76 2C 6F 8D
  14. 40 6C D4 0E 8C B1 16 E7 EA F7 48 B4 03 D8 88 9B CD 1A 05 6C C2 7D FB 5 9D F2 32 88

Schon ein erster kurzer Blick auf die 14 Geheimtexte verrät einem Kryptoanalysten zahlreiche Informationen.

rot: Hier handelt es sich viermal um dasselbe Wort oder den selben Wortteil. Da das Wort am Satzanfang steht, ist das erste Zeichen wahrscheinlich ein Großbuchstabe, vermutlich ein D oder S. Jedoch folgen nach dem Wort insgesamt drei verschiedene Zeichen (47, 5D, 60), so dass das Zeichen 96 vermutlich ein Leerzeichen ist.
grün: In 8 von 14 Sätzen erscheint dieses Zeichen an dieser Stelle. Höchstwahrscheinlich handelt es sich um ein Leerzeichen oder den Buchstaben e (siehe Liste der häufigsten Buchstaben).
blau: In 5 von 14 Sätzen erscheint dieses Zeichen an dieser Stelle. Höchstwahrscheinlich handelt es sich um ein Leerzeichen oder den Buchstaben e (siehe Liste der häufigsten Buchstaben).
rosa: Hier handelt es sich um dasselbe Wort oder den selben Wortteil.

Weiters kann man davon ausgehen, dass am Beginn einer Nachricht immer ein Großbuchstabe und am Ende einer Nachricht ein Satzzeichen steht.

In Phase 2 der Kryptoanalyse, macht sich der Angreifer die mathematische Tatsache zu Nutze, dass ci ⊕ cj = (mi ⊕ k) ⊕ (mj ⊕ k) = (mi ⊕ mj) ⊕ (k ⊕ k) = mi ⊕ mj.

Beispielsweise nimmt er das 0E, von dem er annimmt, dass es sich um ein Leerzeichen handelt, und XOR-verknüpft es mit 49 aus dem ersten Geheimtext an der gleichen Position 4. 0E ⊕ 49 = 47. Der ASCII-Code für das Leerzeichen ist 20 und dieses XOR-verknüpft er mit 47: 47 ⊕ 20 = 67. 67 ist der ASCII-Code für das Zeichen g, was auch korrekt ist, wenn wir im Original-Klartext weiter oben nachsehen. Diesen Vorgang wiederholt er für die anderen Zeichen.

Auch kann der Angreifer versuchen, analog wie oben statt nur eines Zeichens die häufigsten Wörter der deutschen Sprache an beliebiger Stelle einzusetzen und dann zu prüfen, ob der andere Geheimtext an derselben Stelle einen Sinn ergibt. Falls nicht, rückt er eine Position weiter und versucht dasselbe erneut. Zum Beispiel die Artikel ” der “, ” die ” und ” das ” haben eine Länge von fünf Zeichen (jeweils mit Leerzeichen vor und nach dem Wort). Wenn er die korrekte Position eines Artikels findet, erhält er gleich fünf Zeichen des anderen Klartextes. Damit kann er oftmals weitere Teile vor und nach dieser Zeichengruppe erraten. Diese neuen Zeichen kann er nun wiederum mit anderen Geheimtexten per Exklusiv-Oder verknüpfen und erhält dann wieder neue Zeichen oder Zeichengruppen. Es ist nur eine Frage der Zeit, bis der Angreifer alle 14 Nachrichten im Klartext in seinen Händen hält.

Bereits an diesem sehr einfachen Beispiel kann man sehen, dass die Kryptoanalyse ein iterativer und langwieriger Prozess ist, der viel Genauigkeit und Fleiß erfordert.

In der Praxis

Dieses Beispiel sollte in erster Linie verdeutlichen, dass der Schlüssel eines One-Time-Pads niemals (auch nicht teilweise!) wiederverwendet werden darf. Der Schlüssel muss sofort nach der Verwendung sicher und spurlos vernichtet werden. Wird diese Regel eingehalten und wird der Schlüssel absolut zufällig erzeugt, dann bietet das One-Time-Pad perfekte Sicherheit und kann nicht gebrochen werden.

In der Vergangenheit wurde aber genau dieser Fehler bereits mehrfach begangen. Ein bekanntes Beispiel sind die Lorenz-Verschlüsselungsmaschinen aus dem Zweiten Weltkrieg. Hier wurde von den Deutschen eine verschlüsselte Nachricht gesendet, die beim Empfänger jedoch nicht fehlerfrei angekommen ist, und sie wurde ein zweites Mal mit demselben Schlüssel chiffriert versendet. Jedoch hat der Schreiber aus Bequemlichkeit beim zweiten Mal einige Abkürzungen verwendet (z.B. Nr. statt Nummer) und dadurch wurde der Text verändert. Die Briten konnten beide Geheimtexte abfangen und anhand dieser Texte den Chiffriercode knacken und die Maschine sogar nachbauen.

Ein weiteres bekanntes historisches Beispiel ist das Venona-Projekt aus dem Kalten Krieg.

FEATURED TAGS
ai cryptography f-sharp r