Der RC4 Stromciffrier

RC4 ist ein schneller Streamchiffrierer , das 1987 von Ron Rivest, einem Miterfinder des RSA-Verfahrens, entwickelt wurde. Im Gegensatz zu den weitverbreiteten Blockchiffrierern (wie z.B IDEA, DES, RC5), die immer einen ganzen Block (in der Regel 64 Bit) des Klartextes verschlüsseln, arbeiten die Stomchiffrierer (Streamchipher) auf der Bitebene.

Da die RSA Data Security Inc den Algorithmus geheim hielt, gab es bis vor kurzem keine verläßlichen Sicherheitsabschätzungen. Im September 1994 wurde jedoch auf der Mailingliste der Cypherpunks anonym ein Quellcode veröffentlicht, welcher sich nach ausführlichen Tests mit offiziellen RC4-Implementierungen als voll kompatibel herausstellte.

Der Algorithmus ist sehr kompakt und 5-10 mal schneller, als das weitverbreitete DES. Aus diesen Gründen findet RC4 vielen "echtzeit"-orientierten Systemen, wie beispielsweise Mobilfunk (Cellular Digital Packet Data), SSH (Secure SHell) oder den Dateiverschlüsselungsprogrammen SecurePC und Cryptext, Anwendung. Aber auch Netscape (SSL), Lotus (Notes), Apple(AOCE) und Oracle (Secure SQL) vertrauen auf RC4.

RC4 besitzt eine variable Schlüssellänge von bis zu 2048 Bits. Der Algorithmus läßt sich überraschend einfach beschreiben. RC4 arbeitet im OFB-Modus (output-feedback-mode). Der Schlüsselstrom ist völlig unabhängig vom Klartext. Daher darf der gleiche Schlüssel nicht mehrfach benutzt werden. Die Verschlüsselung geschieht indem ein Klartextbyte mit einen Schlüsselstrombyte XOR verknüpft wird. Die Entschlüsselung funktioniert analog. 

P = Klartextbyte (Plaintext-Byte),
K = Schlüsselstrombyte(Key-Byte)
C= Verschlüsseltebyte (Chiphretext-Byte)

Verschlüsselung:
   
       C = P XOR K

Entschlüsselung:

 C XOR K = (P XOR K) XOR K 
         =  P XOR (K XOR K)
         = P XOR 0 
         = P

Das Verfahren verwendet eine S-Box S[0],...,S[255] die eine schlüsselabhängige Permutation der Zahlen {0,...,255} enthält und zwei Zähler i und j. Daneben wird zur Initialisierung ein weiteres 256 Bytes großes Array K[0],...,K[255] verwendet, das durch einfaches wiederholtes Eintragen des Schlüssels gefüllt wird.

Initialisierung der S-Box

 FOR i:= 0 TO 255 DO S[i]:=i;
 j:=0;
 FOR i:= 0 TO 255 DO
     BEGIN
        j:=(j+S[i]+K[i]) MOD 256;
        Swap(S[i],S[j])
     END;

Die Erzeugung des Schlüsselstrom-Bytes K

 i:=(i+1) MOD 256;
 j:=(j+S[i]) MOD 256;
 Swap(S[i],S[j]);
 K:=S[(S[i]+S[j]) MOD 256];

Die S-Box verändert sich nur langsam. Jedoch wird durch den Zähler i garantiert, daß sich jeder Eintrag ändert, der Zähler j sorgt für die Auswahl eines "zufälligen" Elementes. Das ist schon alles! Kein Wunder, daß versierte PEARL Hacker, wie Adam Back und Malcolm Beattie den ganzen Algorithmus in drei Zeilen quetschen konnten. 

#!/usr/local/bin/perl -0777-- -export-a-crypto-system-sig-RC4-3-lines-PERL
@k=unpack('C*',pack('H*',shift));for(@t=@s=0..255){$y=($k[$_%@k]+$s[$x=$_
]+$y)%256;&S;}$x=$y=0;for(unpack('C*',<>)){$x++;$y=($s[$x%=256]+$y)%256;
&S;print pack(C,$_^=$s[($s[$x]+$s[$y])%256]);}sub S{@s[$x,$y]=@s[$y,$x];}

Der Source ist erst zu kurz bekannt, um eine verläßliche Sicherheitsaussage machen zu können. Durch die S-Box und die beiden Zähler können theoretisch 256!*2562 (ca 21700)verschiedene Zustände angenommen werden. Laut RSADSI ist RC4 resistent gegen die beiden in der wissenschaftlichen Literatur als am gefährlichsten geltenden Angriffe, lineare und differentielle Kryptoanalyse und besitzt keine Zyklen kleiner 10100. Für die Schlüssellänge von 40 Bit gibt es eine Exportgenehmigung der US-Regierung. Daß eine Schlüssellänge von 40 Bit, wie sie auch in der Exportversion von Netscape verwendet wird, nicht nur für Geheimdienste leicht zu knacken ist, konnte gleich mehrfach demonstriert werden. So knacken am 15. August 1995 um Adam Back (England), Erik Young (Australien) und David Byers (Schweden) um 10:43 eine 40Bit-RC4 verschlüsselte Netscape-Sitzung. Ebenso am selben Tag um 12:23 Damien Doligez (Frankreich). Doliguez benutzte nach eigenen Angaben hierfür 8 Tage eine Rechenleistung, die einem Netzwerk von 40-50 Pentium-PCs entspricht. Diese Ergebnisse zeigen allerdings keine Schwäche von RC4 auf, da nur der mit 240 viel zu kleine Schlüsselraum einfach mittels brute force durchsucht wurde. Laut Netscape werden zum Entschlüsseln einer RC4-verschlüsselten Nachricht mit einem 40 Bit Schlüssel 64 MIPS-Jahre benötigt. Für eine mit der "US-amerikanischen" Schlüssellänge von 128-Bit verschlüsselte SSL-Sitzung sei dies um den Faktor 288 schwerer und damit faktisch unmöglich.

Weiter Informationen den Source-Code und viele Links findet man unter: http://www.informatik.uni-mannheim.de/~rweis/rgp/rc4/

Rüdiger Weis < ruedi@fim1.informatik.uni-mannheim.de > PGP-Key