Web walk: RC4 encryption

Tuesday 29 June 2004

I found an implementation of a random number generator today, and the comments said it was using the RC4 algorithm, not to encrypt, but just as a source of randomness. I was intrigued.

RC4 is a symmetric encryption algorithm developed by RSA Security. A key is used to initialize a random number generator. The output of the generator is XOR-ed with the cleartext to produce the cipher. The strength of the cipher is dependent on the “strength” of the randomness, that is, how hard it is to predict what the next random byte will be. (The name is because it was the fourth Rivest Cipher).

The algorithm was proprietary until it was leaked in 1994. Since then, it has been subjected to a great deal of analysis, some of it quite abstruse.

The analysis shows certain subtle weaknesses in RC4. Others have tried to create new similar algorithms without the same weaknesses. For example, Bob Jenkins created ISAAC. Until the mathematicians have spent a decade poring over ISAAC output, there’s really no way to know if it has other unidentified weaknesses.

By the way: Bob Jenkin’s web site is full of all sorts of other interesting stuff, including hashing, perpetual motion machines, and jenny, the combinatorial testing tool I mentioned last month.

Comments

[gravatar]
Mark Eichin 9:52 PM on 29 Jun 2004

Any cryptographic function can be used as a prng; the trick is that people then try to use that prng as keying material, which is "cheating" or rather cryptographically unsound. It's a fine way to get "statistically random" output, where predictability isn't a concern. Also, the leaked rc4 was called "arcfour" for a number of years: "Alleged" rc4 :-)

[gravatar]
Holger 8:58 AM on 1 Jul 2004

Using a cipher to generate pseudo-random numbers is actually considered good practice. The X9.17 standard used DES I believe (it might even allow others; I don't have it handy here).

[gravatar]
Damien Katz 4:41 PM on 2 Jul 2004

Abstruse? Maybe that should be your word of the day.

Add a comment:

Ignore this:
Leave this empty:
Name is required. Either email or web are required. Email won't be displayed and I won't spam you. Your web site won't be indexed by search engines.
Don't put anything here:
Leave this empty:
URLs auto-link and some tags are allowed: <a><b><i><p><br><pre>.