recently read an advertisement for some Windows security software that boasted “incredible security using 160-bit RC4.” Superlatives aside, take claims like this with a grain of salt. Based on the products I’ve looked at, many applications using the RC4 algorithm for encryption are vulnerable to attacks because of two issues:

1. RC4 produces the same key stream for each unique key a user or application provides.
2. RC4 encrypts data one byte at a time.

RC4 itself is not a cryptographically weak algorithm, but some inherent usage errors in many applications that employ RC4 leave the applications vulnerable to attacks. I will discuss these errors and how to rectify them. But before discussing its problems, let’s briefly look at how RC4 works.

How RC4 Works
RC4 is a stream cipher (another example is A5, which is used in GSM cell phones), which means that data usually is encrypted and decrypted one byte at a time. Other ciphers, such as RC2, 3DES, DES, and AES, encrypt and decrypt data in blocks, often 64-bit or 128-bit blocks. RC4 is the default stream cipher included with Crypto API in Windows.

RC4 works like this:

• The user or application provides a key.
• RC4 uses the key to create a stream of random bytes, which are XORed (the mathematical symbol for XOR is ) with the plaintext to yield the ciphertext or XORed with the ciphertext to yield plaintext.

It’s a very simple and fast process indeed.

The Problem
Each unique key derives the same RC4 key stream, and herein lies the problem. If the key is re-used and an attacker gains access to the one ciphertext, he/she can XOR the ciphertext and the plaintext to derive the key stream (provided this attacker knows the plaintext to that ciphertext). From that point on, the attacker can derive any plaintext encrypted with that key.

Actually, the attacker cannot derive all the plaintext of the second message; he/she can derive up to the same number of bytes that he/she knows in the first message. In other words, if you know the first 23 bytes from one message you can derive the first 23 bytes in the second message using this attack method.

If you’re still unsure why this problem exists, remember the following rule regarding XORing data:

P  K  P = K

Where P is a byte of plaintext and K is a byte from the key stream.

A common scenario in which this issue comes up is when two computers communicate using RC4—A with B and B with A—and the data between them uses the same key. In fact, this was one of the issues that led to the Microsoft PPTP fix in 1998. As an example of breaking this chain, SSL/TLS also uses RC4 but does so in a more secure manner. The client and server communicate using RC4 but they do so using two different keys. The client uses one key to encrypt data sent to the server, while the server uses another key to send data to the client.

The Solutions
There are a number of ways to rectify this issue. They include:

• If you are using RC4, never use the same key to encrypt more than one message.
• If you must use the same key (you’d better have a good reason!) then consider using a salt with the key.
• Don’t use a stream cipher. Use a block cipher such as RC2, 3DES, or AES (when available).

There is one more issue about RC4 you should be aware of: RC4 is susceptible to a bit-flipping attack. Because RC4 encrypts data a byte at a time, an attacker can modify one byte of ciphertext and the recipient would not know the data is changed. This is particularly dangerous if the attacker knows the format of a message, but not the message. Imagine that an attacker knows a message is constructed like this:

hh:mm dd-mmm. bbbbbbbbbbbbbbbbbbbbbbbbbbbb

Where:

• hh = hour (using 24-hour clock)
• mm = minutes
• dd = day
• mmm = three-letter month abbreviation
• bbbbb = message body

Imagine the following scenario. Gandalf (a good guy) decides to send a message to Frodo (another good guy), which before RC4 encryption is:

18:00 03-Sep. Meet at Weathertop. Gandalf.

Note: We assume that Gandalf and Frodo have a pre-determined shared key they use to encrypt and decrypt data.

As you can see, Gandalf wants to meet Frodo at Weathertop at 6pm on September 3rd. As an attacker you do not have the plaintext, only the ciphertext. However, you could change one or more of the encrypted bytes in the time and date field and then forward the changed message to Frodo. If you’re lucky, when Frodo decrypts the message the time will not be 18:00, and Frodo won’t make it to Weathertop at the allotted time. This is a great attack, because RC4 does not detect errors! In the case of a block cipher such as DES, a tweak to one bit will change at least 64 bits (the block size) when the data is decrypted, making tampering somewhat evident. In short, bit-flipping is much harder to pull off against a block cipher.

(By the way, if you have no idea who or what Gandalf, Frodo, or Weathertop are, then may I suggest you read J.R.R. Tolkien’s wonderful book, “The Lord of the Rings”.)

You can rectify this problem by using digital signatures or message authentication codes (MAC), but that’s a topic for another day!

RC4 has proven to be a fast and secure encryption method, but usage issues abound—most notably key re-use and bit-flipping attacks. Use the steps outlined in this article to help mitigate these issues: don’t re-use encryption keys and use some form of message authentication technique, such as an HMAC or digital signature to determine that your messages haven’t been altered.