Security Problems of ARCfour

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 depended 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 by

  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 that's funny stuff and we're knowing that 40 bit RC4 like in the
old browsers are not a good idea, but 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 since some days
there is a real problem.
-----------------------

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 distinguire attack which needs only 2^{30.8} byte.
That is less than 2 GB.


What is a distinguire attack?
---------------------------

Somebody give you a sequence of bits an You have to answer if these
bits are real random bits, or the result of a stream cipher.

Why is this a good indicator oft he security of an algorithm?
If an attacker can break a cipher she can manage the distinguishing
question, very easily.
If she does not know if 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 if You think the friendly government employees
with the rubber-hoses have an indication that there are cryptographic
informations 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 an 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 the is no item for Triple DES ask Your BoH, install a new version with
strong cryptography (since some week down loadable from Netscape
directly) or use Fortify (http://www.fortify.net/).

Developer:
Additionally to the security problems there is an open question
regarding patents trade secrets and so on.
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).

Ruediger Weis <ruedi@cryptolabs.org>