The RC4 stream cipher

Today I will continue my crypto-101 series with the very popular stream cipher RC4 (Ron’s code 4 by Ronald L. Rivest). I want to say at the very beginning that RC4 is not regarded as secure anymore as by today’s standards. If you plan on using a stream cipher in your own application, please refrain from using RC4. The insecurity of RC4 wasn’t something that popped out over night. First suspicions were uttered already in 1997, until 2000 several theoretical weaknesses were discovered. In 2001/2002 Fluhrer, Mantin and Shamir presented the first practical attacks, see http://www.wisdom.weizmann.ac.il/~itsik/RC4/rc4.html for an overview. In principle RC4 should have been decared dead by then. The final nail in the coffin was the attack suggested by 2013 AlFardan, Bernstein, Paterson, Poettering und Schuldt, see http://www.isg.rhul.ac.uk/tls. Nowadays, RC4 should be regarded as a classical cipher. Something that you learn about, but should never use it in practice. The brutal reality however is that RC4 is still used in many professional areas like wireless encryption (WEP and WPA) and online banking. If you are using Firefox and want to find out if website is using RC4 to protect the communication, just click on the padlock symbol left of the https:// in the address bar, then click on “More Information” and look at the section “Technical Details”. If you encounter “RC4” there, you should be alarmed.

I do not really understand why people keep using RC4. Maybe because it is a true stream cipher and one doesn’t have to worry about block modi and padding. Or because it has such a simple implementation, as we will see below.

Encryption with RC4 is based on the idea to generate a sequence of pseudo-random bytes. XORing these with the plaintext gives the ciphertext. The generation of the pseudo-random random bytes is derived from a key and works as follows: one starts with byte array containing 256 elements (sometimes called sBox). At the beginning each element is initialized with its position, i.e. the zeroth element is set to zero, the first element is set to one, etc. After that the following monkey business

rc4_scheduleis applied for i = 0,\dots 255 where k is the key of length L. j is initialized with 0 and updated each round by adding s[i] + k[i\%L] to it. The addition is done modulo 256. Then s[i] is swapped with s[j]. OK, that was the preparatory stuff.

Now, to encrypt a message m one declares two variables i and j at the beginning and initializes them with zero. To encrypt the n-th character of m one increases i by one (again modulo 256) and j by s[i+1] (also modulo 256). Then one exchanges s[i] with s[j]. The next random byte is then s[s[i]+s[j]] and that will be XORed with m[n] to yield the cipher c[n]. Let’s draw a diagram of the algorithm:

rc4_stream

Since RC4 is comparatively easy to program, I will give a C++ implementation (the code is more or less self-explanatory)

#include <iostream>
#include <iomanip> 

#define swap(v1, v2, temp) temp = v1, v1 = v2, v2 = temp;

using namespace std;

inline void generateRC4SBox(uint8_t s[256] /*=sbox*/, const uint8_t* key, int keylength)
{
    for(int i = 0; i < 256; i++)
        s[i] = i;

    uint8_t j = 0, swap;

    for(int i = 0; i < 256; i++)
    {
        j += s[i] + key[i % keylength]; //The addition is in fact modulo 256
        swap(s[i], s[j], swap); //Exchange s[i] and s[j]
    }
}

inline void RC4(const uint8_t* message, uint8_t* cipher, int start, int stop, uint8_t s[256] /*=sbox*/)
{
    uint8_t i = 0, j = 0, swap;

    for(int n = start; n < stop; n++)
    {
        j += s[++i]; //Note that i is effectively increased by one before the rest is evaluated
        swap(s[i], s[j], swap); //Exchange s[i] and s[j]
        if(message && cipher)
            cipher[n] = s[(uint8_t)(s[i]+s[j])]^message[n]; //Cast inside [..] is needed!
    }
}

int main(int, char**)
{
    const uint8_t *key = (uint8_t *)"66OlSO8L7KoW44awcg2xHJ9X1FbOoF4z", *message = (uint8_t *)"Plaintext";
    const int key_length = 32, message_length = 9; //I do not include terminating 0 character. One might as well include it.
    uint8_t sbox[256], *cipher = new uint8_t[message_length];

    cout<<"RC4 ENCRYPTION"<<endl<<endl<<"preparing sbox (key scheduling) with password \""<<key<<"\"..."<<endl;
    generateRC4SBox(sbox, key, key_length);

    cout<<"skipping first 4096 bytes and encrypting..."<<endl<<endl;
    RC4(0, 0, 0, 4096, sbox); //"Fast forward by 4096 bytes" = "encrypt nonexistent data"
    RC4(message, cipher, 0, message_length, sbox); // The actual encryption is done here.

    cout<<"MESSAGE: "; for(int n = 0; n < message_length; n++) cout<<hex<<setw(2)<<(int)message[n]<<' '; cout<<" (=\""<<message<<"\")"<<endl;
    cout<<"CIPHER:  "; for(int n = 0; n < message_length; n++) cout<<hex<<setw(2)<<(int) cipher[n]<<' '; cout<<endl;

    delete[] cipher; //Standard cleanup for data allocated on the heap
    cipher = 0;

    return 0;
}

Note that due all additions/overflows for the variables of type uint8_t are modulo 256 as required. Also in line 45 I conservatively skip the first 4096 pseudo-random bytes, which is kind of a “hotfix” for some of the weaknesses of RC4. Some people would call that “RC4-drop-4096” or something like that. For the key I used the often quoted high-entropy “66OlSO8L7KoW44awcg2xHJ9X1FbOoF4z” as an example. The expected output is

$ RC4 ENCRYPTION

preparing sbox (key scheduling) with password "66OlSO8L7KoW44awcg2xHJ9X1FbOoF4z"...
skipping first 4096 bytes and encrypting...

MESSAGE: 50 6c 61 69 6e 74 65 78 74  (="Plaintext")
CIPHER:  6b fb 93 e2 20 f2 3b b1 8f

As I have already mentioned, the neat thing about RC4 encryption is it’s easy implementation. The core logic is 27 lines or so and the shortest I now (apart from one-time-pads ;), hehe). But it’s elegance doesn’t save you from it’s insecurities.

As a take-home advice, I suggest to disable RC4 in your webbrowser. In firefox you can search for “RC4” in about:config and set all variables to false. Btw if you want to use my pictures in your presentation, book, homework assignment, …, just contact me. I am experimenting with tikz/pgf a lot and can provide you with vector graphics ;).

Advertisements

About goobypl5

pizza baker, autodidact, particle physicist
This entry was posted in Encryption, Programming, Security and tagged , , , , , , , , . Bookmark the permalink.

Share your thoughts

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s