A simple implementation of RC4 in C #

Introduction

At one time I played one fairly well-known MMORPG in runet. I 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 bells and whistles for it. The first result was the curve bot written in C # and able to beat the mobs, but it also quickly became uninteresting. By that time I stumbled upon a forum related to hacking games and, in particular, the theme of a talented programmer who at his leisure decided to disassemble game traffic. It really interested me and I decided to repeat his achievement.

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


')

General information about RC4

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

This encryption algorithm was created by a professor at MIT, Ronald Rivest, to whom we also owe such algorithms as RC2, RC5, RC6, RSA and the MD2-MD6 hash ruler.

Despite the fact that it is unlikely that anyone will use RC4 in new responsible 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 on my fingers.

So, the input data will be an array of bytes. This 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 kind of encryption without a key !? The key also acts as input. For RC4, it can be from 8 to 2048 bits, but usually a range of 40 - 256 bits is used.
But the data for encryption is an array of bytes, and for some reason, the key is in bits. The fact is that there is such a thing as block size n. For 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 immediately.

The ideal option in terms of strength for a stream cipher is a key size comparable to the size of the encrypted data. Then each bit of plaintext is combined with the corresponding key bit by modulo 2 summation (XOR), forming an encrypted sequence. For decryption, it is necessary to do the same operation again on the receiving side.

Provided that the sequence of key bits is chosen arbitrarily 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 keystream. That is, we expand our key to any size (dynamically, during the processing of input data) and combine it with XOR with input data.

Specifically, we will deal with the algorithm on the example of C #. Create a class "RC4" and declare the following members:

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

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

For the initial initialization of the permutation vector with the key, the Key-Scheduling Algorithm is used:

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);
}
}

In terms of code, nothing complicated. I just want to note that the Swap method (swap two elements of the array) expands the standard list of Array class methods:

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 sequence generator (Pseudo-Random Generation Algorithm). With each call, the method will spit out the next byte of the key stream, which we will combine with the xor and the 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 key byte and combine them with 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 decoding, you can use the same method. Wrap it up in a separate method for clarity:

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

An example of how this class can be used:

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 everything works correctly:


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

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

Many thanks to my friend Vort for advice and recommendations.

Link to the entire source:
SourceForge - RC4.cs