RC4

Was RC4 ist und wie es grundsätzlich funktioniert

RC4, auch ARC4 oder Arcfour genannt, ist eine Stromverschlüsselung. Sie wurde in Standards und Verfahren wie HTTPS, SSH 1, WEP und WPA eingesetzt. Entwickelt wurde RC4 1987 von Ronald L. Rivest; RC4 ist eine Marke von RSA Security. Der Algorithmus wurde zunächst geheim gehalten. 1994 wurde sein Quelltext anonym auf einer Mailingliste veröffentlicht. Um eine Markenrechtsverletzung zu vermeiden, wurden die Bezeichnungen ARC4 („Alleged RC4“) und Arcfour verwendet.

Bei einer Stromverschlüsselung wird aus einem Schlüssel eine Zufallsfolge, der Schlüsselstrom, erzeugt. Der Klartext wird Bit für Bit mit dieser Folge durch Addition modulo 2, also eine XOR-Verknüpfung, verbunden. Das Ergebnis ist der Schlüsseltext. Zum Entschlüsseln wird derselbe Algorithmus verwendet: Der Schlüsseltext wird erneut mit derselben Zufallsfolge per XOR verknüpft, wodurch der Klartext wieder entsteht.

Kernstück ist eine S-Box. Sie ist eine Permutation oder Vertauschung der Byte-Werte 0 bis 255. Zunächst wird sie aus dem geheimen Schlüssel berechnet; anschließend erzeugt sie den Schlüsselstrom. Nach jedem Berechnungsschritt werden zwei Werte der S-Box vertauscht. Der Schlüssel darf nur einmal verwendet werden, weil die Sicherheit davon abhängt, dass sich der Schlüsselstrom nicht wiederholt.

Für die Besetzung der S-Box und die Werte zweier weiterer Variablen gibt es etwa 2^{1684} Möglichkeiten. Das entspräche einer Schlüssellänge von 210 Zeichen (1684/8). Nach dem Geburtstagsparadoxon sind jedoch bereits Schlüssel mit etwa 105 Zeichen zu erwarten, die identische Permutationen der S-Box erzeugen. Außerdem ist bekannt, dass zwei aneinandergehängte identische Texte bis zu 128 Bytes zur gleichen S-Box-Permutation führen können wie der ursprüngliche Text. Dadurch können auch sehr kurze Schlüssel dieselbe Verschlüsselungsfolge erzeugen. RC4 ist einfach auf praktisch jeder Hard- und Software zu implementieren und effizient berechenbar.

Im WEP wurde der einmalige Schlüssel durch das Zusammensetzen eines festen geheimen Schlüssels und eines Session Key gebildet. Dadurch konnte der feste geheime Schlüssel abgeleitet werden. Wird der Schlüssel dagegen mit einer Hashfunktion quasi zufällig gewählt, kann RC4 weiterhin als sicher betrachtet werden. Bei Microsoft-Windows-Systemen in einer NT-Domäne wurde ein Anmeldepasswort nach vorheriger Schlüsselaushandlung per RC4-HMAC verschlüsselt und in einem Kerberos-Frame an den Server übertragen; die Aushandlung erfolgte während der Meldung „Netzwerkverbindungen werden vorbereitet“.

Aufbau und Ablauf des Algorithmus

Die S-Box hat bei einem Byte-Alphabet die Größe 256 und wird zunächst als identische Abbildung angelegt: S[i] = i für i = 0 bis 255. Danach wird sie mit dem Schlüssel k der Länge L Byte gemischt. Der Schlüssel besteht laut Pseudo-Code aus 5 bis 256 Byte. Zunächst gilt j = 0. Für i von 0 bis 255 wird berechnet:

j = (j + s[i] + k[i mod L]) mod 256

Anschließend werden s[i] und s[j] vertauscht. Dieses Verfahren ist die Initialisierung der S-Box.

Zur Erzeugung des Schlüsselstroms werden i und j wieder auf 0 gesetzt. Für jedes Klartextbyte n von 0 bis X − 1 geschieht Folgendes: i wird um 1 erhöht und modulo 256 gerechnet; danach wird j um s[i] erhöht und ebenfalls modulo 256 gerechnet. Dann werden s[i] und s[j] vertauscht. Die nächste Zufallszahl wird aus der S-Box an der Position

(s[i] + s[j]) mod 256

entnommen. Formal lautet sie s[(s[i] + s[j]) mod 256]. Diese Zufallszahl wird mit dem n-ten Klartextbyte per XOR verknüpft und als schl[n] gespeichert:

schl[n] = zufallszahl XOR klar[n]

Die Ausgabe hängt somit vom aktuellen Zustand der S-Box sowie von i und j ab. Die Werte i und j werden bei jedem Schritt verändert, und die S-Box wird fortlaufend umgeordnet.

Sicherheitsprobleme und Verbot in TLS

RC4 bietet wie jede Stromchiffre keinen Integritätsschutz. Verändert ein Angreifer ein Bit des verschlüsselten Textes, verändert sich dadurch auch dasselbe Bit des Klartextes.

Der erste praktische Angriff auf RC4 gelang Scott Fluhrer, Itsik Mantin und Adi Shamir im Jahr 2001. RSA Security empfahl daraufhin, die ersten 256 Bytes beziehungsweise eine Runde des Schlüsselstroms zu verwerfen. Andreas Klein verbesserte den Angriff jedoch so, dass er auch danach noch funktionierte, und empfahl, die Ausgabe der ersten 12 Runden zu verwerfen.

Anfang 2013 wurde ein Angriffsszenario von AlFardan, Bernstein, Paterson, Poettering und Schuldt vorgeschlagen. Es nutzt statistische Auffälligkeiten im von RC4 erzeugten Datenstrom aus, um eine Nachricht zu entziffern, die über mehrere RC4-verschlüsselte TLS-Verbindungen übertragen wird. 2015 zeigten Mathy Vanhoef und Frank Piessens einen praktisch durchführbaren Angriff; dabei konnten Magic-Cookies innerhalb von 52 Stunden entziffert werden.

Jacob Appelbaum vertrat die Ansicht, dass die NSA RC4 in Echtzeit brechen könne. Bruce Schneier bezeichnete diese Vermutung als plausibel. Die Europäische Agentur für Netz- und Informationssicherheit empfiehlt, RC4 durch Rabbit oder Snow 3G zu ersetzen. Auch das Bundesamt für Sicherheit in der Informationstechnik rät von RC4 ab. Die Deutsche Finanzagentur verwendet RC4 beispielsweise seit November 2013 nicht mehr.

Mit RFC 7465 verbot die Internet Engineering Task Force im Februar 2015 den Einsatz von RC4 in TLS. Begründet wurde dies damit, dass die Zahl der für einen erfolgreichen Angriff nötigen Versuche in der Praxis zu klein geworden war und RC4 keine ausreichend hohe Sicherheit für TLS-Sitzungen mehr bot.

Die Weiterentwicklung Spritz

Am 27. Oktober 2014 stellten Ronald L. Rivest und Jacob C. N. Schuldt Spritz als verbesserte Variante von RC4 vor. Spritz dient auch als Grundlage einer kryptographischen Hashfunktion. Die Variante erreicht jedoch nicht die Geschwindigkeit von RC4: Sie ist etwa halb so schnell wie RC4 und außerdem langsamer als die Blockchiffre Advanced Encryption Standard im Counter Mode. Auch die Schlüsselberechnung dauert länger.

Bei RC4 werden pro Ausgabeschritt i erhöht, j um S[i] erweitert, S[i] und S[j] vertauscht und anschließend z = S[S[i] + S[j]] ausgegeben. Spritz verwendet dagegen die Schritte i = i + w, j = k + S[j + S[i]], k = i + k + S[j], danach den Tausch von S[i] und S[j] sowie die Ausgabe z = S[j + S[i + S[z + k]]]. Die Additionen erfolgen modulo N.

Der Parameter w ist teilerfremd zu N; N bezeichnet die Größe des Arrays S und beträgt meist 256. Nach N Iterationen hat i deshalb jeden Wert von 0 bis N − 1 genau einmal angenommen. Jeder Wert in S wurde dadurch mindestens einmal mit einer zufällig gewählten Position vertauscht.