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 <span style="color: #f00;">00 00 00 04</span> |
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 <span style="color: #f00;">8F 9B 62 04</span> |
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 <span style="color: #f00;">04 04 04 04</span> |
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.
C1, C2, C3 sind die drei Geheimtextblöcke der verschlüsselten Nachricht und sind dem Angreifer bekannt; M1, M2, M3 die drei Klartextblöcke der Nachricht und sind geheim. Wie wir aus obiger Abbildung erkennen können, gilt C2 = E(C1 ⊕ M2), wobei E die Verschlüsselungsfunktion darstellt. Beispiel:
| 7D 3E 47 50 64 7A 20 65 | = M<sub>2</sub>| 3A 80 4D 2A 88 5F 3D 9E | = C<sub>1</sub>| 47 BE 0A 7A EC 25 1D FB | = C<sub>1</sub> ⊕ M<sub>2</sub>| 73 9C 1F 2A DA 1D 2E AA | = C<sub>2</sub> = E(C<sub>1</sub> ⊕ M<sub>2</sub>)
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 M2 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 M2 verwendet. Der Angreifer ersetzt das letzte Byte in C1 (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 | = C<sub>1</sub>
wird| 3A 80 4D 2A 88 5F 3D <span style="color: #f00;">BF</span> | = C'<sub>1</sub>
Der Angreifer schickt dann die drei Blöcke IV, C’1, C2 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 M2 = D(C2) ⊕ C1), wobei D die Entschlüsselungsfunktion darstellt. Der Server entschlüsselt C2 und erhält für das letzte Byte von C2 (AA) den Wert FB (siehe oben). FB wird nun mit dem letzten Byte von C’1 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 M2 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 C1 durch das Ergebnis von 9E ⊕ 65 ⊕ 01 = FA.
Aus| 3A 80 4D 2A 88 5F 3D 9E | = C<sub>1</sub>
wird| 3A 80 4D 2A 88 5F 3D <span style="color: #f00;">FA</span> | = C'<sub>1</sub>
Wiederum sendet der Angreifer die drei Blöcke IV, C’1, C2 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 C2 und erhält für das letzte Byte von C2 (AA) den Wert FB (siehe oben). FB wird nun mit dem letzten Byte von C’1 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 M2 hat tatsächlich den Wert 65. Der Angreifer weiß nun, dass das letzte Byte in M2 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 M2 kennt, widmet er sich dem vorletzten Byte. Der Angreifer ersetzt das vorletzte Byte in C1 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 | = C<sub>1</sub>
wird| 3A 80 4D 2A 88 5F <span style="color: #f00;">1F F9</span> | = C'<sub>1</sub>
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 M2 ermitteln konnte. Der Angreifer kennt damit alle Bytes des Blocks M2. Diese Vorgehensweise wiederholt er nun mit den beiden restlichen Blöcken M1 (mit Hilfe des bekannten IV) und M3 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…