As previously mentioned, RC4 is an encryption algorithm used to scramble data so completely that it would take years to decipher using current technology. What makes RC4 so powerful is its speed and strength. To analyze RC4, we must first begin with some definitions.

Algorithm

An algorithm is an explicit set of instructions that have a defined starting and ending point. For example, the instructions you would follow to set up a VCR are considered an algorithm (although some might argue this). In reality, you perform algorithmic steps all the time. Everything from starting a car to baking a cake can be defined by an algorithm.

Cryptology (Encryption/Decryption)

Cryptology is the study of encryption and decryption algorithms. Encryption is simply the scrambling of a message or data through the use of an algorithm; the opposite of this is decryption.

Encryption is typically accomplished with the assistance of an external piece of data, which often comes in the form of a user-selected password or pass phrase. This not only makes the encryption stronger by enforcing a unique key, but it also keeps anyone who does not know the password from accessing the data.

There are two main types of encryption: symmetrical and asymmetrical. Each has its strengths and weaknesses and is best suited to specific applications.

Symmetrical Encryption

The symmetrical encryption and decryption processes are both accomplished using the same key. This is the most prevalent form of encryption. As an example, let's encrypt the word wireless.

1. Take the word and separate each letter and place a number 1 between each letter.

   wireless -> w 1 i 1 r 1 e 1 l 1 e 1 s 1 s

2. Convert the letters into their corresponding alphabetical numbers.

   w1i1r1e1l1e1s1s -> 23 1 9 1 18 1 5 1 12 1 5 1 19 1 19

3. Add 2 to each separate value.

   23 1 9 1 18 1 5 1 12 1 5 1 19 1 19 -> 25 3 11 3 20 3 7 3 14 3 7 21 3 21

You have now performed an encryption algorithm on the word wireless; to decrypt the ciphertext, simply step through the previous algorithm in reverse order.

1. 25 3 11 3 20 3 7 3 14 3 7 21 3 21 -> (- 2) -> 23 1 9 1 18 1 5 1 12 1 5 1 19 1 19

2. 23 1 9 1 18 1 5 1 12 1 5 1 19 1 19 -> (convert to alpha value) -> w1i1r1e1l1e1s1s

3. w 1 i 1 r 1 e 1 l 1 e 1 s 1 s -> (remove 1s) -> wireless

This algorithm is a good example of how computers have revolutionized data encryption. By hand, this type of processing would require hours for even the simplest and shortest of messages. However, give a computer this task, and it will take seconds to decrypt a page's worth of data.

As mentioned previously, symmetrical encryption uses pass phrases or key words to assist it in the encryption of a message. Using the previous example, we will now encrypt the word wireless using the word wep.

1. Convert each letter in the message into its alphanumerical value.

   wireless -> 23 9 18 5 12 5 19 19

2. Convert each letter in the pass phrase into its alphanumerical value.

   wep -> 23 5 16

3. Merge the words together starting from the left, repeating the password as necessary.
   

Thus, you now have an example of symmetric encryption. To decrypt it, you would need to know (or deduce) that the key was wep. Although our example used a short word, imagine the output from a page-long key. The results would be a long string of numbers that have nothing to do with the original value, and would remain worthless without the password wep.

Symmetric encryption is much faster than asymmetric encryption. However, the difficulty with symmetric encryption is that its security depends upon keeping its password secret.

Asymmetrical Encryption

The other type of encryption is known as asymmetrical encryption. This encryption is much more complex, but it has the potential to be more secure. A growing number of applications are incorporating this type of security. Email applications, VPNs, PKI, and even Application Service Providers use asymmetrical encryption.

Asymmetrical encryption requires the use of two keys, one public and one private. Each key requires the use of the other to decipher a message. In other words, imagine that your boss wants to send a secure message to you, and to be fairly confident that only you can open it. She could seal the message in a box using a padlock for which only you have the key. Thus, without your private key, not even your boss can reopen the message after it is secured.

Note that asymmetric encryption requires everyone to have access to a copy of your public "lock," also known as a public key. Typically, this information is available from a central server or a Web site and can be retrieved with minimal effort. However, this one extra step increases the level of complexity just enough to limit the universal adoption of asymmetric encryption.

Disadvantages of Encryption

There are multiple benefits with encryption. For example, it can be used to authenticate users, authorize access to resources, ensure data confidentiality, and guarantee data integrity. It can also be used to provide nonrepudiation for transactions.

However, there are also several potential drawbacks with encryption. These drawbacks include lost passwords, a false sense of security, and the processing overhead of using encryption. This section will briefly address these issues as they apply to wireless networking.

Lost Password

One problem with encryption is what to do in the event of a lost password. In this case, the only option is to find a method of cracking the password. However, depending on the method of encryption, it could be many years before you extract any data. In addition, some countries, including the United States, consider the very act of cracking a password illegal—even if the data belongs to you. Just ask security researcher Dmitry Sklyarov, a programmer for the Russian company Elcomsoft. At the behest of Adobe Systems, the FBI controversially arrested Sklyarov after he gave an academic presentation on password recovery.

Using Encryption Does Not Guarantee Security

The second issue is one of the biggest threats to wireless users. Many people consider their networks to be secure based solely on the fact that they are using WEP. This assumption is flawed, as the password is usually left blank or as the default. In addition, WEP does not protect against most traditional hacker attacks. Finally, WEP itself is fundamentally flawed. I encourage you to use WEP, but never use it as your only line of defense.

Password/shared-secret-based keys are only as good as the human that creates them. If passwords are easily guessed or appear in a dictionary, then it is far easier to guess/lookup the password/key than to brute-force the entire keyspace. This applies to all password based authentication/crypto systems.

Additionally, if a crypto system has algorithmic flaws or implementation flaws, the crypto can be circumvented. WEP is an example of a good cipher (RC4) implemented poorly. RC4 can be rendered ineffective due to the implementation flaws in WEP.

Encryption Overhead

The last issue also applies to wireless networking—the overhead or CPU time that it takes to encrypt and decrypt network data. This overhead can have a serious impact on the productivity of a network application, and can have detrimental results in time-critical situations.

Any encryption adds overhead to the processing requirements of a networking system. Encryption delays the transmission process and can also adversely affect network device processors' ability to deal with other critical/needed functions.

Ciphers

When discussing symmetric encryption, there are two main methods by which a chunk of data can be encrypted. It is important to understand the differences and the benefits of how they work in order to understand how RC4 encrypts data.

Block

A block cipher (such as DES or 3DES) takes a large chunk of data and encrypts it with the key. This process is repeated over and over again until the whole message is completely encrypted. Typically there is a size variable that controls how big the chunk of data can be. Regardless of the size, the entire key is used to encrypt the chunk of data.

For example, suppose you want to send your boss an email using a block cipher. In this case, you would enter one password, and the entire message would be encrypted at one time. The following equation illustrates the simplicity of this type of encryption, as well as its weakness.

Cipher Function (data, pass phrase) = Output 

Note that the entire pass phrase is used each time in its original form to encrypt the data. With continuous use, a block cipher is functionally weak. If even two blocks are encrypted with the same cipher, the pass phrase could be extracted from the ciphertext.

In other words, if an attacker can determine the original data of just one message, he can compare the ciphertext with the plaintext and calculate the difference. This difference would then be the code to crack any future encrypted messages. In addition, the two messages can be analyzed and compared. Depending on the encryption method, the two messages can be merged, which would cancel out the encryption, and essentially provide a hacker all the information he needs to view the data.

Stream Cipher

A stream cipher also uses a pass phrase. However, it encrypts data on a much smaller scale. Whereas a block cipher might encrypt a whole page of text at one time, a stream cipher can encrypt the bits that make up one letter of a page of text. To illustrate, the letter A is equivalent to the decimal value of 65, which can be converted to one byte, which in turn is comprised of eight bits. A stream cipher can encrypt that one bit before sending it out, and repeat the encryption seven more times for just one letter. This can result in thousands of encrypted values for a complete email or message.

A streaming cipher is capable of encrypting on a detailed level because it uses a state condition, in addition to the pass phrase and data. This means the data is encrypted differently for each chunk that passes through the encryption program. To perform a stream cipher, two streams are generated, one that feeds into the other. The first stream is called the key stream, which combines a state value, data value, and pass phrase value to generate a randomly changing stream of data. The key stream in turn is used to produce the output cipher by combining the new state value (from the key stream), data value, and key value. Mathematically, this is accomplished using two functions, as compared to the one function of a block cipher. This can be depicted as shown in the following section.

Self-Synchronizing Stream Cipher

The following are the two functions of the self-synchronizing stream cipher:

State Time+1 = State Function(State Time, Data Time, Password Time)  
Output Time = Cipher Function(State Time, Data Time, Password Time) 

As illustrated, the output is now dependent on three variables, two of which will be changing (the password is constant). The first function is known as the key stream generator, and the second is the cipher function.

The strength of this type of encryption is found in the fact that there are now two variables that change. Therefore, even if there is a predictable value in the data, the state will be randomly different, which significantly decreases the chances of an attacker being able to extract relevant data from the cipher.

There are a couple variations of stream ciphers that we need to define before we discuss weaknesses with the RC4 cipher implementation in WEP. These are known as synchronous stream ciphers and self-synchronizing stream ciphers. The difference between the two is found in whether the key stream relies on the data to produce the stream. The previous example illustrates how a self-synchronizing stream ciphers, as it relies on the data to produce the key stream. In contrast, the following example illustrates how a synchronous stream cipher creates the output. In this type of cipher, the first two functions combined are considered the key stream generator.

- Stream-2: Synchronous Stream Cipher   
State Time+1 = State Function(State Time, Password Time)   
Stream Value Time = Keystream Function(State Time, Password Time)   
Output Time = Cipher Function(Stream Value Time, Data Time) 

Although the synchronous cipher might seem more complicated, it is actually weaker than the self-synchronizing cipher. Notice from the last function of this type of cipher that only one "unknown" value is needed to reverse the encryption. On the other hand, the self-synchronizing encryption uses three variables.

The previous functions represent a process through which the data is combined. This process can be comprised of anything ranging from complex mathematical calculations to a simple addition of the two values. In our case, for RC4 the last function is an XOR binary addition process. The following will explain the XOR function, as it is used to produce the final RC4 ciphertext.

XOR

XOR is a simple logical operation. In our case, it serves as a rudimentary encryption scheme that combines one segment of data with another to produce a scrambled output. XOR is one of the most popular methods for encrypting data because of its speed and the fact that it works at the bit level.

To understand XOR, you must understand logic structures. See whether you can determine how the final bit is calculated

From this example, you should be able to determine a pattern. By comparing the bits from Byte 1 with the corresponding bits from the XOR byte, you can quickly deduce the algorithm. When there are similar bit characters (for example, 0 - 0, 1 - 1) the resulting bit is a 0, and when there are different bit characters (for example, 0 - 1, 1 -0) the resulting bit is a 1.

Although this type of encryption is rapid and operates at the bit level, it is problematic. To illustrate, let's examine the XOR calculation of a series of two bytes. The first will XOR the binary value of letter A, and the second will XOR the value of NULL (that is, zero), each using the XOR byte of 1111111

The letter A is transformed into a completely different value, which happens to be equivalent to the tilde (~) in ACSII. However, the resulting value is the same as the XOR key! In other words, if an attacker can determine that a chunk of data is NULL, he can quickly determine the XOR key used to encrypt that particular piece of code.

Although this is a security issue, in a proper implementation of RC4, the state value should randomly change, which then changes the XOR key. Therefore, any transposing of the XOR value would occur randomly, and would be almost impossible to predict. For example, if the key at Time 1 was 10101010, and the data was 01010101, the resulting value would be 11111111. This value would be the same if at Time 2 the key was 11111111 and the data was 00000000.

As you can see from the table, an attacker would have no way of knowing if the resulting value was a result of a NULL character or the result of a valid piece of data. However, this is irrelevant if the attacker can determine which packets of data did contain NULL characters.