Rechnernetze

Schwäche in RC4

Die bisher aufgezeigten Schwächen haben dazu geführt, dass die Verschlüsselung durch WEP als unsicher eingestuft wurde. Endgültig diskreditiert wurde WEP jedoch im August 2001, als eine Schwäche im RC4 Algorithmus entdeckt wird [FMS01], die einen passiven Angriff auf WEP ermöglicht, welcher unabhängig von der Länge des verwendeten Schlüssels und Initialisierungsvektors funktioniert. Eine bestätigte Umsetzung dieser Schwäche gab es bereits eine Woche später [SIR01] und kurz darauf ebenfalls zwei öffentlich zugängliche Programme, nämlich WEPCrack [RD03] und Airsnort [SJB03].

Der Angriff von Fluhrer, Mantin und Shamir (Fluhrer et al.) setzt voraus, dass der für RC4 verwendete Schlüssel aus einem geheimen Teil und einem für den Angreifer sichtbaren Teil, welcher als Initialisierungsvektor oder kurz IV bezeichnet wird, zusammengesetzt ist. Zusätzlich muss es für den Angreifer möglich sein, das erste Byte des von RC4 erzeugten Schlüsselstroms zu erlangen. Beide Voraussetzungen sind in WEP erfüllt. Die Ermittlung des ersten Bytes des Schlüsselstroms ist möglich, weil für das Versenden von Daten in IEEE 802.11 Netzen ein LLC/SNAP Kopf verwendet wird, dessen erstes Byte stets den Wert AA (hexadezimal) bzw. 170 (dezimal) enthält (vgl. Abschnitt 2.1.1). Durch Verknüpfung mittels exklusivem Oder des ersten verschlüsselten Byte mit diesem Wert erhält man das erste Byte des Schlüsselstroms. Abbildung 14 veranschaulicht diesen Zusammenhang.

Für das Verständnis des Fluhrer et al. Angriffs ist eine genauere Betrachtung des RC4-Algorithmus nötig, dessen Quelltext in Abbildung 15 zu sehen ist. Bevor eine detaillierte Vorstellung erfolgt, wird zunächst ein kurzer überblick über den Ablauf gegeben. 

Der erste Schritt ist die Wahl von geeigneten Initialisierungsvektoren, welche auch als schwach bezeichnet werden. Unter der Voraussetzung, dass alle Bytes des RC4-Schlüssels K bis zum gesuchten bekannt sind, ist es dann möglich die Erzeugung der initialen Permutation nachzuvollziehen, bis zu dem Schritt, an dem das gesuchte Byte des RC4-Schlüssels verwendet wird. Sind in diesem Schritt bestimmte Bedingungen nicht erfüllt, was sich nachprüfen lässt und nur mit sehr geringer Wahrscheinlichkeit der Fall ist, so wird der ausgewählte Initialisierungsvektor verworfen und von vorne begonnen. Ansonsten kann nun die Auswertung beginnen. Mit einer Wahrscheinlichkeit von ungefähr 5% werden im weiteren Verlauf die für die Ausgabe des ersten Byte des Schlüsselstroms Z relevanten Einträge von S nicht mehr verändert, was als "Resolved Condition" bezeichnet wird. Da das erste Byte des Schlüsselstroms bekannt ist, bleibt dann die einzige Unbekannte in der Gleichung für die Ausgabe des ersten Byte das gesuchte Byte des RC4-Schlüssels. Da die relevanten Einträge in S nur mit einer Wahrscheinlichkeit von 5% nicht verändert werden und nur in diesem Fall das Ergebnis korrekt ist, ist die Untersuchung von ungefähr 60 schwachen Initialisierungsvektoren für die Erlangung eines Schlüsselbyte nötig. 

Für die detaillierte Vorstellung ist es nun nötig formale Bezeichnungen einzuführen. Der für WEP verwendete RC4-Schlüssel K mit der Länge ` setzt sich aus einem 3 Byte langen Initialisierungsvektor (K[0],K[1],K[2]) und dem geheimen WEP-Schlüssel (K[3], ...,K[`-1]) zusammen. Für die Gewinnung eines Byte des geheimen WEP-Schlüssels K[B], mit 3 < B < l - 1, müssen zunächst schwache Initialisierungsvektoren gewählt werden. Hierfür muss folgendes gelten, wobei Si[a] das Element mit dem Index a der Permutation S nach dem Schleifendurchlauf i kennzeichnet:

Für die Erfüllung dieser Bedingungen sind unter anderem Initialisierungsvektoren der Form (B,N - 1,H) geeignet, wobei B das gesuchte Byte des Schlüssels ist, N die Länge von S darstellt und H einen beliebigen Wert haben kann, der jedoch bekannt sein muss. 

Inwieweit das Verhalten bei der Erzeugung der initialen Permutation mit Initialisierungsvektoren dieser Form nachvollzogen werden kann, soll nun gezeigt werden. Abbildung 16 zeigt die Werte des RC4-Schlüssels und der Permutation S in Schlüsselschritten.

Im Schritt i = 0 erhält j aufgrund des RC4-Schlüssels den Wert B und die Werte an den Positionen 0 und B werden getauscht. Im nächsten Schritt ist i = 1 und j erhält seinen alten Wert plus S0[1] = 1 plus K[1] = N -1. Damit bleibt der Wert von j aufgrund der Anweisung "mod N", welche wegen der Länge von S nötig ist, wie im vorhergehenden Schritt.

Im darauf folgenden Schritt mit i = 2 wird j um H + 2 erhöht, was für jeden Initialisierungsvektor zu einem individuellen Verhalten führt. Unter der Voraussetzung, dass die Werte des RC4-Schlüssels bis einschließlich K[B - 1] bekannt sind, kann die Erzeugung der initialen Permutation jedoch bis zum Schritt B - 1 nachvollzogen werden. Wurde der Wert von S[0] oder S[1] zwischendurch verändert, so wird der Initialisierungsvektor verworfen und mit einem anderen von vorne begonnen.

Im nächsten Schritt i = B liegt eine sogenannte "Resolved Condition" vor. Dies bedeutet, dass in einem Schritt k  1 die drei Werte, von denen die Ausgabe des ersten Byte des Schlüsselstroms abhängt, nämlich U = Sk[1], V = Sk[U] und W = Sk[U + V ], mit einer Wahrscheinlichkeit von ungefähr 5% in den folgenden Schritten an keiner Vertausch-Operation mehr teilnehmen (vgl. Abbildung 17).

Wie diese Werte in Schritt i = B aussehen, wird nun näher betrachtet. Zunächst einmal wird j um K[B]+SB-1[i] erhöht und es findet die Vertausch-Operation statt. Das Ergebnis ist wiederum in Abbildung 16 zu sehen. Es ergibt sich:

Die Ausgabe SB[B] geht aus der Vertausch-Operation in diesem Schritt hervor und ist in der Permutation des vorhergehenden Schrittes wie folgt zu finden:

Der Angreifer kennt die Permutation SB-1 und den Wert von jB-1. Zusätzlich kennt er nach Voraussetzung den Wert von SB[B], welches das erste Byte des Schlüsselstroms ist. Damit kennt er ebenfalls seinen Ort in SB-1, da jeder Wert in S aufgrund der Initialisierung und der ausschließlichen Manipulation durch Vertausch-Operationen nur einmal vorkommt. Dies ist der Wert jB. Durch die Kenntnis dieser Werte, führt folgende Umformung zum gesuchten Byte des Schlüssels:

Mit ist hierbei die Stelle in S_t gemeint, an welcher der Wert M auftritt.

Aufgrund der "Resolved Condition" beträgt die Wahrscheinlichkeit, dass das auf diese Weise ermittelte Byte des Schlüssels korrekt ist, ungefähr 5%. Eine Untersuchung von 60 Initialisierungsvektoren ist nötig, um eine Erfolgswahrscheinlichkeit von mehr als 50% zu erhalten.