RC4

RC4, ARC4 oder Arcfour ist eine Stromverschlüsselung, die mit Standards wie HTTPS, SSH 1 und WEP bzw. WPA weite Verbreitung gefunden hat.

RC4 (Ron's Code 4) wurde 1987 von Ronald L. Rivest entwickelt, ist eine Marke von RSA Security und offiziell geheim (Security by Obscurity). ARC4 (Alleged RC4) oder Arcfour geht auf eine anonyme Veröffentlichung von Quelltext im Jahr 1994 zurück und ist Open Source.

Beschreibung

Eine Zufallsfolge wird aus einem nur einmalig zu verwendenden Schlüssel erzeugt. Der Klartext wird Bit für Bit per XOR mit der Zufallsfolge verknüpft, um die Daten zu verschlüsseln.

Der Zufallsgenerator verwendet eine so genannte S-Box, eine zufällig gewählte Permutation oder Substitution der Zahlen 0 bis 255. Die S-Box wird in einem ersten Schritt aus dem geheimen Schlüssel berechnet und anschließend zur Berechnung der Zufallsfolge verwendet. Nach jedem Berechnungsschritt werden zwei Werte der S-Box vertauscht.

Die Sicherheit eines solchen Verfahrens ist nur gewährleistet, wenn sich die Zufallsfolge nicht wiederholt. Daher darf der Schlüssel bzw. das Passwort nur einmalig verwendet werden. Für die Besetzung der S-Box und die Werte zweier weiterer Variablen gibt es ca. 2¹⁶⁸⁴ Möglichkeiten, was einer Schlüssellänge von 210 (1684/8) Zeichen entsprechen würde. Nach dem Geburtstagsparadoxon ist zu erwarten, dass es Schlüssel mit einer Schlüssellänge von ((1684/2)/8) 105 Zeichen gibt, die identische Permutationen der S-Box erzeugen. Bekannt sind mittlerweile mindestens zwei 24 Zeichen (192 Bit) lange Schlüssel, die zur gleichen Permutation der S-Box führen. Damit gibt es zwei verschiedene Schlüssel, die zur gleichen Verschlüsselungsfolge führen.

Der Algorithmus ist sehr einfach mit praktisch jeder Hard- und Software zu implementieren und sehr effizient berechenbar. Die Verarbeitungsgeschwindigkeit des DES ist selbst in kleinsten Mikrocontrollern meist ausreichend. Der Schlüssel beim DES und anderen Blockchiffren wie dem AES (CBC-Mode) kann im Gegensatz zum RC4 auch mehrfach verwendet werden. Vergleichbare Stromchiffren wie SEAL sind vergleichbar schnell und gelten als sicher.

Im WEP wurde der einmalige Schlüssel durch einfaches Zusammensetzen eines festen geheimen Schlüssels und eines Session Key bestimmt. In diesem Fall ist es jedoch möglich, den festen geheimen Schlüssel abzuleiten. Falls der Schlüssel mit einer Hash-Funktion quasi zufällig gewählt wird, kann der RC4 aber weiterhin als sicher betrachtet werden.

Bei Microsoft-Windows-Systemen, welche an eine NT-Domäne angebunden sind, wird das Anmeldepasswort, welches der Benutzer in der GINA-Oberfläche eingibt, nach vorangegangener Aushandlung eines Schlüssels per RC4-HMAC verschlüsselt und durch einen Kerberos-Frame an den Server übertragen. Die Aushandlung des Schlüssels findet während der Meldung „Netzwerkverbindungen werden vorbereitet“ statt.

Algorithmus

Die Nachschlagephase von RC4 bei einem Alphabet der Größe eines Bytes. Das Ausgabebyte wird von den Werten $S[i]$ und $S[j]$ ausgewählt, diese werden addiert modulo 256 gerechnet.

Kern des Verfahrens ist die so genannte S-Box, eine zufällige Vertauschung oder Permutation des Standard-Alphabets (Byte-Werte 0-255). Mittels der S-Box wird eine Zufallsfolge erzeugt, die Bit für Bit durch Addition modulo 2, auch XOR-Verknüpfung genannt, mit dem Nachrichtenstrom verknüpft wird. Die S-Box wird zunächst als identische Abbildung vorbesetzt, so dass $S[i] = i$ für i=0 bis 255 gilt.

Die initiale Belegung der S-Box kann mit dem folgenden Pseudo-Code beschrieben werden. Die S-Box wird dabei aus dem Schlüssel $k$ der Länge $L$ Byte berechnet:

 k[]: gegebene Schlüssel-Zeichenfolge der Länge 5 bis 256 Byte
 L := Länge des Schlüssels in Byte
 s[]: Byte-Vektor der Länge 256
 Für i = 0 bis 255
   s[i] := i
 j := 0
 Für i = 0 bis 255
   j := (j + s[i] + k[i mod L]) mod 256
   vertausche s[i] mit s[j]

Die anschließende Berechnung der Zufallsfolge erfolgt analog:

 klar[]: gegebene Klartext-Zeichenfolge der Länge X
 schl[]: Vektor zum Abspeichern des Schlüsseltextes
 i := 0
 j := 0
 Für n = 0 bis X-1
   i := (i + 1) mod 256
   j := (j + s[i]) mod 256
   vertausche s[i] mit s[j]
   zufallszahl := s[(s[i] + s[j]) mod 256]
   schl[n] := zufallszahl XOR klar[n]

Zum Entschlüsseln verwendet man den gleichen Algorithmus, wobei der Schlüsseltext anstelle des Klartextes eingegeben wird. Zwei XOR-Verknüpfungen mit derselben Zufallszahl heben sich gegenseitig auf, und als Ausgabe entsteht wieder der Klartext.

Nennenswerte Schwächen des Verfahrens liegen allein in der Initialisierung der S-Box begründet. Bei einer zufällig gewählten S-Box als Ausgangspunkt der Berechnung ist das Verfahren trotz seiner Einfachheit gegenwärtig (Jan. 2011) praktisch nicht zu knacken.

Sicherheit

Wie jede Stromchiffre bietet auch RC4 keinen Integritätsschutz. Wenn ein Angreifer ein Bit einer verschlüsselten Nachricht ändert, so ändert er damit auch das gleiche Bit des Klartextes.

Der erste praktische Angriff auf die RC4-Chiffre gelang Scott Fluhrer, Itsik Mantin und Adi Shamir im Jahr 2001. RSA Security empfahl daraufhin, die ersten 256 Bytes des Schlüsselstroms zu verwerfen. Andreas Klein verbesserte den Angriff, so dass er auch dann funktioniert, wenn die ersten 256 Byte verworfen werden. Er empfahl, die Ausgabe der ersten 12 Runden zu verwerfen.

Weblinks

• Implementierung in Python
• Überblick über Arbeiten bezüglich der Sicherheit von RC4, englisch
• Original-Post im Usenet des damals noch geheimen RC4-Algorithmus, englisch
• Weaknesses in the Key Scheduling Algorithm of RC4 von Scott Fluhrer, Itsik Mantin, und Adi Shamir, englisch (PDF-Datei; 297 kB)
• RSA Security Response to Weaknesses in Key Scheduling Algorithm of RC4
• A Stream Cipher Encryption Algorithm "Arcfour" (Internet Engineering Task Force Network Working Group 1997)
• RFC 4345 Improved Arcfour Modes for the Secure Shell (SSH) Transport Layer Protocol