Hello You,

In this blog post I’ll not only explain how to solve the challenge but will explain the algorithm used itself, what it is and why we often see it used in malware binaries.

All will be answered in this blog post.

RC4 Algorithm#

RC4 (also known as Rivest Cipher 4) is a form of stream cipher and variable-length key algorithm. It encrypts messages one byte at a time, what makes RC4 popular is how simple it is to apply it and that it is high-speed algorithm even on a really large pieces of data and it is just a few lines of code and that’s simply why it has been used by many malware authors. Additionally, it is similar to the one-time pad, except that generated pseudorandom bits, rather than a prepared stream, are used.

RC4 uses a pseudorandom bit generator that produces a stream 8-bit number that is unpredictable without knowledge of the input key, the output of the generator is called key-stream, and is combined one byte at a time with the plaintext stream cipher using X-OR operation.

Note that RC4 use has been banned by the Internet Engineering Task Force because it’s not a strong algorithm and multiple vulnerabilities have been found in it, rendering it insecure.

RC4 relies on 2 mathematical concepts:

  • Key scheduling algorithm (KSA) which initalizes the process in an array typically referred to as S-box. That S-box is processed 256 times, and bytes from the key are mixed in too.
for(int i = 0; i < 256; i++)
	S[i] = i;

// KSA is going to use the secret key to scramble this array.
for(int i = 0; i < 256; i++) {
	j = (j + S[i] + key[i % len]) % 256;

	swap(&S[i], &S[j]);
}
  • Pseudo-random generation algorithm (PRGA) where data is fed byte by byte and a mathematical model modifies it. The model looks up values and adds them to 256, and uses the sum as the byte within the keystream (a stream of random or pseudorandom characters that are combined with a plaintext message to produce an encrypted message). It swaps each element with another at least once every 256 rounds.
i, j = 0;
while (true) {
    i = (i + 1) % 256;
    j = (j + S[i]) % 256;
    swap(S[i], S[j]);
    t = (S[i] + S[j]) % 256;
    k = S[t];
}

The key generation algorithm used uses a variable-light key from 1 to 256 bytes to initialize a 256-byte state vector S, with elements S[0] to S[255].

For encryption and decryption a byte K is generated from S by selecting one of the 255 entries in a systematic fashion, then the entries in S are permuted (Swapped with each other) again.

TL;DR This algorithm simply generates a 256 bytes array with values from 0 to 255 and permutes the array based on the secret key, here we finish with the KSA phase and move on to the PRGA where we generate a key stream that will be xored with the provided plain and that’s simply how we get the cipher text :)

How to detect RC4#

We’ll be using Ghidra to analyze the file, and in the challenge I wrote, to make things as easy as possible, I didn’t even strip the binary. So, if you go to the functions list, you will literally see the RC4 function.

However, let’s say the binary was stripped — how would we detect this algorithm?

From our understanding of the algorithm, it must create an S-box array and use a for loop that iterates 256 times to initialize the S-box with values from 0 to 255. So, if you find such behavior in the code, it’s a strong indicator that RC4 is being used.

As we can see here, it sets local_10 to 0x0, then jumps to a check to see if local_10 has reached 0xff. If it’s less than or equal to 0xff, it jumps back to LAB_00101dc, where the initialization of the S-box array happens.

This pattern can also be easily identified in the decompiled pseudo-code.

RSuiiii4 challenge solution#

With the first look to the main function we see the possible key, which is rc4isthekey, and possible cipher text that starts in local_48

But let’s go back one step and understand what the binary is doing, which is also can be seen and understood from the usage, where you can see it is requiring you when you run the challenge to put the flag as an argument.

This means that the flag will appear in the running binary for a time to check the user input (which is another way to solve the challenge)

So what is going on in the main function is that it takes the argument you provided and encrypts it, then it compares it byte by byte with the hard coded cipher text, if it doesn’t match it prints Try Harder...

In this approach, we’ll try to get the cipher text and decrypt it using the key that we have

let’s get the value of local_48, we’ll do so by changing the type of local_48 to an array by right-clicking on local_48 and selecting retype variable to char[42] (42 or any big value that is near to the estimated value) which will give us this output, which can be easily extracted

Now convert the values to hex and use cyberchef RC4 recipe, and you’ll get the flag :)

That was simply it :3