Simple implementation of RC4 in C #

Introduction

At one time I played one pretty famous MMORPG in Runet. Spent a lot of time on it, but soon the gameplay bored me. However, there was a desire to learn how the game works and try to make various gadgets for it. The first result was a crooked bot written in C # and able to beat mobs, but it also quickly became uninteresting. By that time, I came across a forum related to hacking games and, in particular, the topic of one talented programmer who decided to parse the game’s traffic in his spare time. This greatly interested me and I decided to repeat his achievement.

Armed with Wireshark, I received several dumps and, frankly, was dumbfounded by the content. It was no longer getting used to hexadecimal values, but it was impossible to isolate any structure. Since I have very little experience in system programming, I decided to take the advice of a professional (topic author) and ask him for a tip: which way to dig. In addition to general recommendations, I learned that game traffic is encrypted using the RC4 algorithm, and server data is also compressed (more on that another time). The direction was set and I began to study the algorithm to implement it in C #.

RC4 Overview

So, RC4 is a stream cipher, which means that each character of open (unencrypted) text will be encrypted depending on two parameters: the key and the position of the character in clear text. In the next section, I will explain how this works.

This encryption algorithm was created by the professor of the Massachusetts Institute of Technology, Ronald Rivest, to whom we also owe such algorithms as RC2, RC5, RC6, RSA and the line of hashes MD2-MD6.

Despite the fact that hardly anyone will use RC4 in new critical projects due to known vulnerabilities, there are a number of technologies that use it. Examples of such technologies are WEP, SSL, TLS. Also, in my example, the developers of one of the MMORPG decided to use it.

Algorithm

I want everyone to understand how RC4 works, so I will explain it on my fingers.

So, the input data will be an array of bytes. It can be any information: voice, image, text. Of course, information can come in the form of a stream, but what is a stream, if not a long array?
What is keyless encryption !? The key also acts as input. For the RC4 algorithm, it can be from 8 to 2048 bits, but a range of 40 - 256 bits is usually used.
But the data for encryption with us is an array of bytes, and the key for some reason is in bits. The fact is that there is such a thing as the size of a block n. For an example, we will use n = 8, but the algorithm will be even more cryptographic, if we take n = 16. Then in one step 2 bytes will be encrypted right away.

An ideal option in terms of strength for a stream cipher is a key size comparable to the size of the encrypted data. Then, each plaintext bit is combined with the corresponding key bit by modulo-2 summation (XOR) to form an encrypted sequence. To decrypt, you need to do the same operation again on the receiving side.

Provided that the key bit sequence is randomly selected and has no periods, it is impossible to crack the cipher, but there is a problem of transmitting a long key. Therefore, in practice, a pseudo random number generator based on a given key is used to generate a key stream. That is, we expand our key to any size (dynamically, while processing the input data) and XOR combine it with the input data.

We will deal specifically with the algorithm using C # as an example. Create a class “RC4” and declare the following members:

byte[] S = new byte[256];
int x = 0;
int y = 0;

To generate the key stream, the cipher uses a hidden internal state consisting of two parts:
- A permutation containing all possible bytes from 0x00 to 0xFF (array S).
- Counter variables x and y.

For the initialization of the key vector-permutation, we use the Key-Scheduling Algorithm:

    private void init(byte[] key)
    {
      int keyLength = key.Length;

      for (int i = 0; i < 256; i++)
      {
        S[i] = (byte)i;
      }

      int j = 0;
      for (int i = 0; i < 256; i++)
      {
        j = (j + S[i] + key[i % keyLength]) % 256;
        S.Swap(i, j);      
      }
    }

From the point of view of the code, nothing complicated. I just want to note that the Swap method (swap two elements of the array in places) extends the standard list of methods of the Array class:

  static class SwapExt
  {
    public static void Swap(this T[] array, int index1, int index2)
    {
      T temp = array[index1];
      array[index1] = array[index2];
      array[index2] = temp;
    }
  }


The init method must be called before encryption / decryption when the key is known. You can do this in the constructor:

    public RC4(byte[] key)
    {
      init(key);
    }

Next, you need to implement a Pseudo-Random Generation Algorithm generator. With each call, the method will spit out the next byte of the key stream, which we will combine with the xor'om byte of the source data.

    private byte keyItem()
    {
      x = (x + 1) % 256;
      y = (y + S[x]) % 256;

      S.Swap(x, y);

      return S[(S[x] + S[y]) % 256];
    } 

Now the simplest is left! For each byte of the array / stream of input unencrypted data, we request the byte of the key and combine them using xor (^):

    public byte[] Encode(byte[] dataB, int size)
    {   
      byte[] data = dataB.Take(size).ToArray();       

      byte[] cipher = new byte[data.Length];

      for (int m = 0; m < data.Length; m++)
      {       
        cipher[m] = (byte)(data[m] ^ keyItem());
      }

      return cipher;
    }

For decryption, you can use the same method. Wrap it in a separate method for clarity:

    public byte[] Decode(byte[] dataB, int size)
    {
      return Encode(dataB, size);
    }

An example of how to use this class:

byte[] key = ASCIIEncoding.ASCII.GetBytes("Key");

RC4 encoder = new RC4(key);
string testString = "Plaintext";
byte[] testBytes = ASCIIEncoding.ASCII.GetBytes(testString);
byte[] result = encoder.Encode(testBytes, testBytes.Length);

RC4 decoder = new RC4(key);
byte[] decryptedBytes = decoder.Decode(result, result.Length);
string decryptedString = ASCIIEncoding.ASCII.GetString(decryptedBytes);

And here is the result to make sure that everything works correctly:


By implementing a class that decrypts traffic, we are one step closer to parsing packets.

In conclusion, I will say that this implementation is the simplest and most obvious. It can be complicated to increase resistance to breaking.

Many thanks to my friend Vort for the advice and recommendations.

Link to the entire source:
SourceForge - RC4.cs