[Chaos CD]
[Datenschleuder] [71]    Security Problems with ARCfour
[Gescannte Version] [ -- ] [ ++ ] [Suchen]  

 

Security Problems with ARCfour

by Rüdiger Weis <ruedi@cryptolabs.org>

RC4 is a fast software stream cipher designed by Ron Rivest. It is widely used e.g. in the Netscape browsers (SSL), Lotus Notes and included in many cryptographic libraries. RC4 has variable key-length.

RC4 has been published anonymously (thanks to an anonymous writer on the Cypherpunk mailing list). Because RC4 is a trademark we should call it ARCfour.

Since there is no official publication we give a short description of the algorithm http:\\www.cryptolabs.org\arcfour\.

The Algorithm uses a S-box S[0],...,S[255] which contains a key dependant permutation of {0,...,255} and two counters i and j. For the initialization we use another 256 byte array K[0],...,K[255]. We fill this array by repeating the key bits. Than we initialize the 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;
To generate a key stream byte we do following: 
		i:=(i+1) MOD 256; 
		j:=(j+S[i]) MOD 256;    
		Swap(S[i],S[j]);    
		K:=S[(S[i]+S[j]) MOD 256];
That's all.

So we can e.g. use export restricted signatures like: 
 #!/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];}
Thanks to Adam Back and Malcolm Beattie.

Ok now, but that's basically just screwing around, and of course, we all know, that 40bit strong RC4 (such as used in older browsers) is not such a good idea anyway, so what's new?

Well, the cryptographic feeling says: Ron Rivest ist probably the best designer of symmetrical ciphers, but can crypto be so easy and elegant?

There have been some attacks against RC4 (e.g. Golic, Eurocrypt 97) and statistical observations (e.g. Paul Crowley, http://www.cluefactory.org.uk/paul/, pretty cool home-page!-), but until recently no real problems have surfaced. Until recently...

On the Fast Software Encryption 2000 in New York a ''Statistical Analysis of the Alleged RC4 Keystream Generator'' by Scott R. Fluhrer and David A. McGreW (Cisco) has been presented. They show a socalled distinguire attack which needs only 2^{30.8} byte. That's less than 2 GB.

What is a distinguire attack?

Somebody gives you a sequence of bits and you have to answer whether these bits are truly random bits, or the result of a stream cipher.

Why is this a good indicator oft the security of an algorithm? Because if an attacker can break a cipher, she can answer the question quite easily. If, on the other hand she does't know whether some bits are random or a cipher output, she has no hook to attack at all.

And think of a scenario using a steganographic filesystem. It is not a nice idea to think the friendly government employees with the rubber-hoses have an indication that there are cryptographic bits of information in your wonderful random looking 'SETI' data.

Do not use ARCFour!

RC4 is patented, trademarked, not published. The free crypto community is just starting to understand RC4 and now there is no margin of security left! So let's switch to better and free algorithms.

Netscape Users: Switch off anything except Triple DES in Configure SSL v.2. and Configure SSL menu. (Click Lock, Click Navigator, Click Configure SSL v.2 and Click Configure SSL v.3)

If there is no item for Triple DES, ask your BoH, install a new version with strong cryptography (meanwhile downloadable from Netscape directly) or use Fortify (http://www.fortify.net/).

Developers: Additionally to the security problems, there is an open question regarding patents, trade secrets etc. We have very strong, fast and free ciphers. E.g. Blowfish, or the AES candidates Twofish, Serpent (not really fast) and Rijndael (use at least 13 rounds). I think Blowfish is the most secure 64-bit cipher, anyway. If you need a stream cipher just use the Outer Feedback Mode (OFB). <tom>

 

  [Chaos CD]
[Datenschleuder] [71]    Security Problems with ARCfour
[Gescannte Version] [ -- ] [ ++ ] [Suchen]