Tag: cryptography

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, ⊕): c_i = m_i ⊕ k, für i = 1, 2, …, 14. c_i ist der Geheimtext mit der Nummer i, m_i 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 c_i ⊕ c_j = (m_i ⊕ k) ⊕ (m_j ⊕ k) = (m_i ⊕ m_j) ⊕ (k ⊕ k) = m_i ⊕ m_j.

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.

Das Padding-Orakel wird für einen Seitenkanalangriff verwendet, bei dem der Geheimtext vollständig entschlüsselt werden kann. Funktionsweise, Angriff und Abwehr werden in diesem Artikel anhand eines konkreten Beispiels verständlich dargestellt.

Was ist Padding?

Blockchiffre-Verfahren wie AES und 3DES arbeiten mit einer bestimmen Blockgröße. Beispielsweise beträgt die Blockgröße bei AES 128 Bit und bei 3DES 64 Bit. Zu verschlüsselnde Nachrichten werden dabei in mehrere Blöcke aufgeteilt und jeder Block wird dann einzeln verschlüsselt. Wenn der letzte Block einer Nachricht nun kürzer ist als die jeweilige Blockgröße des Chiffrierers, so muss die Lücke aufgefüllt werden, damit der gesamte Block verschlüsselt werden kann. Dieses Auffüllen nennt man Padding. Auch wenn eine Nachricht oder der letzte Block einer Nachricht genauso lang ist wie die Blockgröße, findet ein Padding statt. Es wird dann einfach ein neuer vollständiger Block an die Nachricht als Padding angehängt. Ein Padding findet also unabhängig von der Nachrichtenlänge grundsätzlich immer statt. (Es gibt Methoden wie Ciphertext Stealing und den CTR-Modus von Blockchiffrierern, die ein Padding überflüssig machen. Die meisten Verschlüsselungsanwendungen in der Praxis arbeiten jedoch im CBC-Modus mit Padding wie in diesem Artikel beschrieben.)

Welche Padding-Methoden gibt es?

Beim Padding nach dem ANSI X.923 Standard werden die fehlenden Bytes mit Nullwerten (0) aufgefüllt und das letzte Byte enthält die Gesamtlänge des Paddings. Bei einer Blocklänge von acht Bytes (64 Bits) ergibt sich folgendes Beispiel, wenn der letzte Block mit vier Bytes aufgefüllt werden muss:

| 90 72 94 DF 00 00 00 04 |

Der ISO 10126 Standard sieht vor, dass die fehlenden Bytes mit Zufallswerten aufgefüllt werden sollen und das letzte Byte die Gesamtlänge des Paddings angeben soll. In unserem Beispiel mit vier Bytes als Padding sieht das dann so aus:

| 90 72 94 DF 8F 9B 62 04 |

Beim Padding nach dem PKCS7 Standard werden alle fehlenden Bytes mit der Gesamtlänge des Paddings aufgefüllt. D.h., wenn sieben Bytes fehlen, werden diese Bytes mit dem Wert 7 aufgefüllt; wenn drei Bytes fehlen, mit dem Wert 3 usw. In unserem Beispiel daher:

| 90 72 94 DF 04 04 04 04 |

Der Angriff

Bei der folgenden Darstellung des Angriffs mittels des Padding-Orakels sind Kenntnisse über die logische XOR-Funktion (Exklusives Oder, Symbol: ⊕) und die Funktionsweise eines CBC-Blockchiffrierers zum Verständnis erforderlich.

Bei dem Angriff mittels des Padding-Orakels handelt es sich um einen sogenannten Chosen Ciphertext Attack. Zum Gelingen benötigt dieser Angriff auf der Gegenseite einen Service, der eine (direkte oder indirekte) Rückmeldung gibt, ob das Padding des verschlüsselten Geheimtextes korrekt war oder nicht. Bei der Gegenseite kann es sich beispielsweise um einen Internet- oder lokalen Netzwerk-Server handeln, der verschlüsselte Anfragen bearbeiten soll.  Dass diese Annahmen nicht realitätsfremd sind, werden wir im letzten Abschnitt dieses Artikels sehen.

Die Funktionsweise eines CBC-Blockchiffrierers ist in der folgenden Abbildung dargestellt (Blockgröße acht Bytes, die zu verschlüsselnde Nachricht inkl. Padding wurde auf drei Blöcke aufgeteilt):

Wichtig ist zu erkennen, dass jeder Klartextblock (Plaintext) vor dem Verschlüsseln mit dem Initialisierungsvektor (IV) bzw. dem im vorherigen Schritt erzeugten Geheimtextblock (Ciphertext) per XOR verknüpft wird.

Der Angreifer ist im Besitz eines verschlüsselten Geheimtextes (einschließlich des zufällig erstellten IV, der in der Regel mitgesendet wird) und möchte die Nachricht entschlüsseln.

C₁, C₂, C₃ sind die drei Geheimtextblöcke der verschlüsselten Nachricht und sind dem Angreifer bekannt; M₁, M₂, M₃ die drei Klartextblöcke der Nachricht und sind geheim. Wie wir aus obiger Abbildung erkennen können, gilt C₂ = E(C₁ ⊕ M₂), wobei E die Verschlüsselungsfunktion darstellt. Beispiel:

| 7D 3E 47 50 64 7A 20 65 | = M2
| 3A 80 4D 2A 88 5F 3D 9E | = C1
| 47 BE 0A 7A EC 25 1D FB | = C1 ⊕ M2
| 73 9C 1F 2A DA 1D 2E AA | = C2 = E(C1 ⊕ M2)

In unserem Beispiel arbeitet das Verschlüsselungssystem mit Padding nach dem PKCS7-Standard, d.h. gültige Paddings wären 01 oder 02 02 oder 03 03 03 usw.

Der Angreifer möchte nun M₂ in Erfahrung bringen. Der Angreifer arbeitet sich bei diesem Angriff immer vom letzten Byte zum ersten vor. Da das häufigste Zeichen in deutschen Texten das Leerzeichen ist, wird das Leerzeichen (ASCII-Code 20) als erste Annahme für das letzte Byte von M₂ verwendet. Der Angreifer ersetzt das letzte Byte in C₁ (nämlich 9E) durch das Ergebnis von 9E ⊕ 20 ⊕ 01 = BF. Der Wert 20 steht dabei für das Leerzeichen und der Wert 01 für ein Padding mit der Länge 1.

Aus
| 3A 80 4D 2A 88 5F 3D 9E | = C1
wird
| 3A 80 4D 2A 88 5F 3D BF | = C'1

Der Angreifer schickt dann die drei Blöcke IV, C’₁, C₂ an den Server, der den manipulierten Geheimtext entschlüsselt, das Padding auf Gültigkeit überprüft und abhängig davon eine Akzeptanz- oder Fehlermeldung an den Angreifer zurückgibt. Wie wir aus obiger Abbildung erkennen können, gilt M₂ = D(C₂) ⊕ C₁), wobei D die Entschlüsselungsfunktion darstellt. Der Server entschlüsselt C₂ und erhält für das letzte Byte von C₂ (AA) den Wert FB (siehe oben). FB wird nun mit dem letzten Byte von C’₁ per Xor verknüpft und ergibt FB ⊕ BF = 44. Dies ist kein gültiger Padding-Wert, da der Wert größer ist als die Blocklänge. Der Server gibt also eine Fehlermeldung zurück, das Padding ist ungültig.

In unserem Beispiel hatte der Angreifer Pech, denn das letzte Byte von M₂ besitzt tatsächlich den Wert 65 (siehe oben) und nicht 20 wie vermutet. Als nächstes probiert es der Angreifer mit dem zweithäufigsten Zeichen, dem Buchstaben e. Der ASCII-Code für e lautet 65. Der Angreifer ersetzt das letzte Byte in C₁ durch das Ergebnis von 9E ⊕ 65 ⊕ 01 = FA.

Aus
| 3A 80 4D 2A 88 5F 3D 9E | = C1
wird
| 3A 80 4D 2A 88 5F 3D FA | = C'1

Wiederum sendet der Angreifer die drei Blöcke IV, C’₁, C₂ an den Server, der den manipulierten Geheimtext entschlüsselt, das Padding auf Gültigkeit überprüft und abhängig davon eine Akzeptanz- oder Fehlermeldung an den Angreifer zurückgibt. Der Server entschlüsselt C₂ und erhält für das letzte Byte von C₂ (AA) den Wert FB (siehe oben). FB wird nun mit dem letzten Byte von C’₁ per Xor verknüpft und ergibt FB ⊕ FA = 01. Dies ist ein gültiger Padding-Wert, nämlich ein Padding der Länge 1, genauso wie es der Angreifer beabsichtigt hatte. Der Server antwortet also, dass das Padding gültig war und der Geheimtext akzeptiert wurde.

Dieses Mal hatte der Angreifer Glück, das letzte Byte von M₂ hat tatsächlich den Wert 65. Der Angreifer weiß nun, dass das letzte Byte in M₂ den Wert 65 (d.h., Buchstabe e) hat!

Hätte der Angreifer diesmal auch keinen Erfolg gehabt, hätte er alle möglichen Werte für das letzte Byte bis zum Erfolg durchprobiert (insgesamt 256 mögliche Werte, 00 bis FF).

Da der Angreifer nun das letzte Byte der Nachricht M₂ kennt, widmet er sich dem vorletzten Byte. Der Angreifer ersetzt das vorletzte Byte in C₁ durch das Ergebnis von 3D ⊕ 20 ⊕ 02 = 1F. Das letzte Byte wird durch 9E ⊕ 65 ⊕ 02 = F9. Die beiden Werte 02 stehen für das Padding mit der Länge 2.

Aus
| 3A 80 4D 2A 88 5F 3D 9E | = C1
wird
| 3A 80 4D 2A 88 5F 1F F9 | = C'1

Dieser Vorgang wird solange wiederholt, bis der Angreifer auch den korrekten Wert für das vorletzte Byte kennt. Dann geht er über zum drittletzten Byte usw., bis er schließlich auch das erste Byte von M₂ ermitteln konnte. Der Angreifer kennt damit alle Bytes des Blocks M₂. Diese Vorgehensweise wiederholt er nun mit den beiden restlichen Blöcken M₁ (mit Hilfe des bekannten IV) und M₃ der Nachricht und kann so in relativ kurzer Zeit den kompletten Geheimtext entschlüsseln.

Sollte der IV dem Angreifer nicht bekannt sein, so kann er trotzdem alle Blöcke bis auf den ersten entschlüsseln.

(Eine alternative Vorgehensweise besteht darin, die Werte nicht nach einer Häufigkeitsverteilung sondern zufällig auszuwählen. Die Wahrscheinlichkeit, dass dann der erste Versuch richtig ist, beträgt 1/256. Im Durchschnitt wird der Angreifer pro zu erratendem Byte 256/2 = 128 Versuche benötigen. Bei einer Blocklänge von 8 Bytes ergeben das durchschnittlich 8*128 = 1.024 Versuche pro Block. Dieser Angriff ist folglich sehr effizient.)

Das Padding-Orakel in der Praxis

Nachdem wir nun in der Theorie und anhand eines Beispiels verstanden haben, wie der Angriff funktioniert, stellt sich die Frage, ob er denn auch in der Praxis möglich ist bzw. schon durchgeführt wurde. Die Antwort lautet ja. Es gibt sogar im Internet ein Tool, das genau so einen Angriff durchführt.

Beim Padding-Orakel handelt es sich um eine Seitenkanalattacke (Side Channel Attack). Der Erfolg dieses Angriffs hängt davon ab, ob die entschlüsselnde Instanz (z.B. ein Internet-Server) in direkter oder indirekter Form eine Rückmeldung über die Gültigkeit des Paddings zurückgibt. Die Internet-Protokolle SSL/TLS und IPSec sind grundsätzlich empfänglich für diesen Angriff. Ein sehr schönes Beispiel eines Timing Attacks, der das Padding-Orakel benutzt, gibt Brice Canvel in Password Interception in a SSL/TLS Channel.

Wie können Angriffe dieser Form verhindert werden? Durch Verwendung des CTR- statt des CBC-Modus bei Blockchiffrierern (im CTR-Modus findet kein Padding statt) oder durch das Erstellen und Mitsenden eines Message Authentication Codes (MAC) von der verschlüsselten Nachricht. Ebenfalls sollten entschlüsselnde Instanzen keine Rückmeldungen über Erfolg oder Fehler eines Entschlüsselungsvorganges geben, was allerdings in der Realität nicht immer möglich sein wird.

Weiterführende Literatur:
Serge Vaudenay: Security Flaws Induced by CBC Padding Applications to SSL, IPSEC, WTLS…