Post

Identifying RC4 in Malware - Custom Implementation vs WinCrypto API

Posted
Preview Image
By Ben Hopkins
15 min read
Identifying RC4 in Malware - Custom Implementation vs WinCrypto API

What is RC4?

RC4 is a very commonly used stream cipher. Rather than encrypting data in fixed blocks (like AES), it generates a keystream - a pseudorandom stream of bytes - and XORs that against your plaintext to produce ciphertext. Decryption is identical because XOR is reversible with the same key.

There are two main ways that RC4 is implemented in malware. The first is a custom implementation, where the developer has written the algorithm themselves from scratch. This means you can see the raw mechanics in the decompiler — the S-box initialisation, the key mixing loop, the swaps, and the XOR operation. The second is via the Windows CryptAPI, where the developer delegates the encryption to Windows own crypto library. In this case you won’t see any of the RC4 internals; instead you’ll see a chain of Crypt* API calls, mayve all of these, or just some of them:

  • CryptAcquireContext
  • CryptCreateHash
  • CryptDeriveKey
  • CryptEncrypt/CryptDecrypt
  • CryptDestroyKey

When considering a custom implementation, RC4 has two distinct phases:

  1. KSA (Key Scheduling Algorithm) takes your key and uses it to initialise a 256-byte array (called the S-box). This is the setup phase.
  2. PRGA (Pseudo-Random Generation Algorithm) walks through the S-box to generate the keystream bytes, which are then XORed against the data.

With the basics out of the way, lets break down exactly how these two methods work.

RC4 Custom Implementation

As previously mentioned, custom RC4 requires logic that handles the KSA process, the PRGA, and the XOR, so lets break dow how this looks.

KSA (Key Scheduling Algorithm)

KSA is the initialisation stage. It works by creating a list of values from 0-256, each value is then swapped with another based on a calculation. The code blocks below (In Python and C) shows a basic implementation:

1
2
3
4
5
6
7
8

def KSA(key):  

    S = range(0, 256)  # Generate a "table" of values from 0 to 256
    j = 0
    for i in range(0, 256):
            j = (j + S[i] + key[i % len(key)]) % 256   # Table is scrambled, swapping each value with eachother
            S[i], S[j] = S[j], S[i]                    # Swapping S[i] with S[j]
    return S

1
2
3
4
5
6
7
8

for (i = 0, j = 0; i < 256; i++)
{
    j = (j + context->s[i] + key[i % length]) % 256; // j is derived from the key, making the swap pattern key-dependent

    temp = context->s[i];          // Store original value of S[i] before it gets overwritten
    context->s[i] = context->s[j]; // Overwrite S[i] with S[j]
    context->s[j] = temp;          // Write original S[i] into S[j], completing the swap
}

PRGA (Pseudo-Random Generation Algorithm)

The PGRA generates and outputs the keystream using the list of values from before. It then generates as many bytes as needed - up to the value of 256.

Note: Take note of the value “256”, it is quite easy to detect an RC4 algorithm through the number of modulo it uses. In code this may also show as 0x100 or 100h (256 in hex) so convert to a decimal to get 256.

The code implementations are below in python and C:

1
2
3
4
5
6
7
8
9
10

def PRGA(S):

    i = 0
    j = 0
    while True:  # Responsible for outputting the keystream used for the XOR
            i = (i + 1) % 256
            j = (j + S[i]) % 256
            S[i], S[j] = S[j], S[i]  # Swapping S[i] with S[j]
            K = S[(S[i] + S[j]) % 256]
            yield K  # K is the generator containing the keystream

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

void Rc4Cipher(Rc4Context* context, const unsigned char* input, unsigned char* output, size_t length)
{
    unsigned char temp;
    
    // Process each byte of the input
    for (size_t k = 0; k < length; k++)
    {
        // Update i
        context->i = (context->i + 1) % 256;
        
        // Update j
        context->j = (context->j + context->s[context->i]) % 256;
        
        // Swap S[i] and S[j]
        temp = context->s[context->i];
        context->s[context->i] = context->s[context->j];
        context->s[context->j] = temp;
        
        // Generate keystream byte and XOR with input
        output[k] = input[k] ^ context->s[(context->s[context->i] + context->s[context->j]) % 256];
    }
}

XOR

The last stage is a simple XOR operation, XORing each byte of the given data with a byte of the keystream generated previously. The implementations are below for python and C:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

def main():

    plaintext = "RC4_Encryption_Test"
    key = [ord(c) for c in "encryption key"]
    output = ""
    
    S = KSA(key)
    keystream = PRGA(S)
    
    for c in plaintext:   # XOR each byte of the ciphertext/plaintext with a byte of the keystream
            output += "%02X" % (ord(c) ^ keystream.next())  # Output the ciphertext/plaintext as hex
    print output  # Display the ciphertext/plaintext

if __name__ == "__main__"
            main()

1

output[k] = input[k] ^ context->s[(context->s[context->i] + context->s[context->j]) % 256];

Note: The operator ^ is XOR in C.

Decompiled Example

This example is from a North Korean malware sample showing a custom RC4 implementation that combines all three stages into one function:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

int result; // eax
char v11; // cl
char v12; // [esp+Fh] [ebp-101h]
char S; // [esp+10h] [ebp-100h]
char v14; // [esp+11h] [ebp-FFh]
__int16 v15; // [esp+10Dh] [ebp-3h]
char v16; // [esp+10Fh] [ebp-1h]

S = byte_409704;
v2 = 0;
memset(&v14, 0, 0xFCu);
v15 = 0;
v16 = 0;
LOBYTE(v9) = 0;
v4 = 0;

// S-box initialisation --> Stage 1
do
{
    *(&S + v4) = v4;
    ++v4;
}
while ( v4 < 256 );

// KSA  --> Stage 2
v5 = 0;
do
{
    v6 = *(&S + v5);
    v7 = (unsigned __int8)(v6 + v2 + byte_408030[v5++ % 10]);
    v2 = v7;
    v8 = *(&S + v7);
    *(&S + v7) = v6;
    *(&v12 + v5) = v8;
}
while ( v5 < 256 );

// PRGA / XOR  --> Stage 3/4
LOBYTE(v9) = 0;
for ( result = 0; result < a2; ++result )
{
    v3 = (unsigned __int8)(v3 + 1);
    v11 = *(&S + v3);
    v9 = (unsigned __int8)(v9 + *(&S + v3));
    *(&S + v3) = *(&S + v9);
    *(&S + v9) = v11;
    *(_BYTE *)(result + a1) ^= *(&S + (unsigned __int8)(v11 + *(&S + v3)));
}
return result;

With some of the theory out of the way, lets look inside a real malware sample in a decompiler to find the custom RC4 implementation.

Worked Example: Remcos RAT

Sample Hash: 0af76f2897158bf752b5ee258053215a6de198e8910458c02282c2d4d284add5

Note: The decompiler I’m using throughout this blog is Binary Ninja, but the principles work regardless of your decompiler choice; thoiugh results may vary on the quality of decompiled code and how richly the code is commented.

Opening this sample in Binary Ninja, and navigating to the strings, there is a string for SETTINGS , which represents the config that this Remcos RAT sample wants to decrypt using RC4.

Settings reference

By hitting X in that we can get the cross reference and find sub_41b4a8.

1
2
3
4
5
6
7
8
9
10

0041b4b9   HRSRC hResInfo =
0041b4b9      FindResourceA(hModule: data_472d40, lpName: "SETTINGS", lpType: 0xa)
0041b4b9        
0041b4c3   if (hResInfo != 0)
0041b4d4      int32_t eax_1 =
0041b4d4         LockResource(hResData: LoadResource(hModule: data_472d40, hResInfo))
0041b4e3      hResInfo = SizeofResource(hModule: data_472d40, hResInfo)
0041b4e9      *arg1 = eax_1
0041b4e9        
0041b4ee   return hResInfo

Next, we hit X on sub_41b4a8 to get the cross reference of that, which leads to sub_40f3c3.

rc4 decrypt config

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

0040f3c3    void* __fastcall sub_40f3c3 RC4_Decrypt_Config

0040f3c9        char* var_424 = nullptr
0040f3d9        HRSRC eax = sub_41b4a8 (&var_424)
0040f3de        char* edi = var_424
0040f3e4        uint32_t ebp = zx.d(*edi)
0040f3e7        uint32_t var_438 = ebp
0040f3e8        char* eax_1 = _malloc()
0040f3f5        sub_436910(eax_1, &edi[1], ebp)
0040f408        void var_41c
0040f408        void* var_438_2 = sub_4020b7(&var_41c, eax_1, ebp)
0040f40e        sub_401fe2(0x475338)
0040f417        sub_401fd8()
0040f421        char* esi_1 = eax + 0xffffffff - ebp
0040f423        char* var_438_3 = esi_1
0040f424        var_424 = esi_1
0040f428        char* eax_4 = _malloc()
0040f43a        sub_436910(eax_4, &edi[1 + ebp], var_424)
0040f448        char var_404[0x404]
0040f448        sub_406cb7(&var_404, eax_1, ebp)     // <-- Wrapper function 1
0040f45b        sub_406dd8(&var_404, arg1, eax_4, var_424) // <-- Wrapper function 2
0040f461        j___free_base(eax_4)
0040f473        return arg1

From this function, the important subroutines to look at are:

  • sub_436910 → Key being extracted from here
  • sub_406cb7 → wrapper for → sub_406ccd → RC4 init and KSA function
  • sub_406dd8 → wrapper for → sub_406d3c → RC4 PRGA and XOR function

KSA

Going into the wrapper function sub_406cb7, and then locating sub_406ccd. This function contains both phases of the RC4 KSA, first initialising the S-box with values 0-255 (SIMD optimised by the compiler), then scrambling it using the supplied key in a series of key-dependent swaps:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

00406cd0    int32_t esi = 0
00406cd3    int32_t edi = arg1
00406cd3        
00406cf4    // S-box setup for stage-1 RC4 decrypt
00406cf4    for (int32_t i = 0; i s< 256; i += 4)
00406ce8        *(edi + (i << 2)) =
00406ce8            __paddd_xmmdq_memdq(_mm_shuffle_epi32(zx.o(i), 0), data_46d290)
00406ce8        
00406d33    uint32_t result
00406d33        
00406d33    // KSA process, takes the values from 0-256 and scrambles them
00406d33    for (int32_t i_1 = 0; i_1 s< 256; )
00406d0d        esi = (esi + zx.d(*(modu.dp.d(0:i_1, arg3) + arg2)) + *(edi + (i_1 << 2)))
00406d0d            & 0x800000ff
00406d0d            
00406d13        if (esi s< 0)
00406d1c            esi = ((esi - 1) | 0xffffff00) + 1
00406d1c            
00406d1d        arg1.b = *(edi + (i_1 << 2))
00406d23        *(edi + (i_1 << 2)) = *(edi + (esi << 2))
00406d26        i_1 += 1
00406d27        result = zx.d(arg1.b)
00406d2a        *(edi + (esi << 2)) = result
00406d2a        
00406d39    return result

PRGA & XOR

Going into the wrapper function sub_406dd8 enabled you to find sub_406d3c. This function contains the RC4 PRGA, walking the S-box to generate keystream bytes which are XORed against the input data byte by byte, producing the decrypted output.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

00406d4e    // The `0x400` is 1024 bytes, which is 256x4 - each byte is
00406d4e    // being stored as a DWORD
00406d4e    int32_t esi = 0
00406d51    int32_t edi = 0
00406d53    char var_400[0x400]
00406d53    char* result
00406d53    void* ecx
00406d53    // Copy S-box into local var_400
00406d53    result, ecx = sub_436910(&var_400, arg1, 0x400)
00406d62    char* i = nullptr
00406d62        
00406d67    // if arg3 is equal to -1, don't run. Common Windows API error
00406d67    // return code - sanity check
00406d67    if (arg3 != 0xffffffff)
00406dc9        do  // Main loop doing the PRGA
00406d72            esi = (esi + 1) & 0x800000ff
00406d72                
00406d78            if (esi s< 0)
00406d81                esi = ((esi - 1) | 0xffffff00) + 1
00406d81                
00406d82            int32_t eax = *(&var_400 + (esi << 2))
00406d88            edi = (edi + eax) & 0x800000ff
00406d88                
00406d8e            if (edi s< 0)
00406d97                edi = ((edi - 1) | 0xffffff00) + 1
00406d97                
00406d98            ecx.b = eax.b  // The swap
00406d9e            // Basically S[i] = S[j]
00406d9e            *(&var_400 + (esi << 2)) = *(&var_400 + (edi << 2))
00406da2            result = zx.d(ecx.b)
00406da5            *(&var_400 + (edi << 2)) = result
00406daf            // (S[i] + S[j]) % 256
00406daf            ecx = (*(&var_400 + (esi << 2)) + result) & 0x800000ff
00406daf                
00406db5            if (ecx s< 0)
00406dbe                ecx = ((ecx - 1) | 0xffffff00) + 1
00406dbe                
00406dbf            result.b = var_400[ecx << 2]
00406dc3            i[arg2] ^= result.b  // The XOR
00406dc6            i = &i[1]
00406dc9        while (i u< arg3 + 1)
00406dc9        
00406dd5    return result

RC4 using WinCryptAPIs

Aside from using custom implementations, malware authors can also make use of CryptAPIs (functions that do this on their own). Bear in mind that it’ll most likely be obfuscated in real samples. RC4 implementation will look different when using Windows APIs because Windows handles the KSA and PRGA processes through its APIs, so you won’t see the same pattern.

The indicator imports to look for:

When looking for these APIs, the most straightforeward way to do this is to look at the programs imports, specifically you’d be looking for a pattern of APIs including:

  • CryptAcquireContext - initialises the crypto provider
  • CryptCreateHash - creates a hash object (often used to derive the key)
  • CryptDeriveKey - derives the actual encryption key from a hash
  • CryptEncrypt / CryptDecrypt - the actual encryption/decryption call
  • CryptDestroyKey / CryptDestroyHash / CryptReleaseContext - clean-up

The key differences from custom RC4:

  • You never see the KSA or PRGA loops
  • No 256 element S-box
  • No XOR operation visible
  • Instead you see a chain of Crypt* API calls
  • The algorithm is identified by the constant passed to CryptDeriveKey or CryptCreateHash — RC4 has a specific algorithm ID (CALG_RC4 = 0x6801)

That constant 0x6801 is the smoking gun, as it has the same role as the 256/0x100 constant in custom RC4.

Worked Example: OrcaKiller RAT

Sample Hash: 253a704acd7952677c70e0c2d787791b8359efe2c92a5e77acea028393a85613

Opening this sample in Binary Ninja, and navigating to the imports, and searching for Crypt, you’ll notice the Windows CryptAPI references:

crypt imports

Double-clicking into one of these strings (CryptDecrypt in this example) shows that they are direct imports

crypt imports

Now that we know they are imports, the next step is to go to the Symbols tab and search for one of these strings as imports:

search symbols

Now hitting X on CryptDecrypt for example will show the cross references:

x-refs

We’ll want to go into subroutine sub_4012c0. The entire function is below:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

004012c0 BOOL __thiscall sub_4012c0(int32_t* arg1, int32_t arg2, uint8_t* arg3, uint32_t* arg4)

004012c9    if (*arg1 == 0)
00401390        return arg4
00401390        
004012e1    uint32_t var_4
004012e1    BOOL eax = CryptCreateHash(hProv: arg1[1], Algid: 0x8003, hKey: 0, dwFlags: 0, 
004012e1        phHash: &var_4)
004012e1        
004012e9    if (eax == 0)
00401398        return eax
00401398        
00401303    BOOL esi =
00401303        CryptHashData(hHash: var_4, pbData: &arg1[2], dwDataLen: 0x10, dwFlags: 0)
00401303        
00401307    if (esi != 0)
00401324        uint32_t var_8
00401324        esi = CryptDeriveKey(hProv: arg1[1], Algid: 0x6801, hBaseData: var_4, 
00401324            dwFlags: 0, phKey: &var_8)
00401324            
00401328        if (esi != 0)
00401330            BOOL eax_7
00401330                
00401330            if (arg2 == 0)
00401368                eax_7 = x(hKey: var_8, hHash: 0, Final: 1, dwFlags: 0, pbData: arg3, 
00401368                    pdwDataLen: arg4)
00401330            else
0040134b                eax_7 = CryptEncrypt(hKey: var_8, hHash: 0, Final: 1, dwFlags: 0, 
0040134b                    pbData: arg3, pdwDataLen: arg4, dwBufLen: arg1[8])
0040134b                
00401372            esi = eax_7
00401375            CryptDestroyKey(hKey: var_8)
00401375        
00401380    CryptDestroyHash(hHash: var_4)
0040138d    return esi

The main line to be aware of is:

1

esi = CryptDeriveKey(hProv: arg1[1], Algid: 0x6801, hBaseData: var_4,

Notice it’s using CryptDeriveKey, Microsoft docs below:

It takes the arguments, including an ALG_ID which is the algorithm ID, basically what algorithm its going to use. In this case its 0x6801 which confirms it is CALG_RC4. Microsoft docs below.

The exact reference in MSDN is:

alg-id reference

Now we know for sure its doing RC4, lets look at how the function itself works as a whole:

1. Create the hash object:

0x8003 = CALG_MD5 , it’s hashing something with MD5 first. Refer to the MSDN above.

1

CryptCreateHash(Algid: 0x8003)

2. Hash the key material:

Hashing 16 bytes (0x10) of data; this is the raw key material being fed into MD5.

1

CryptHashData(pbData: &arg1[2], dwDataLen: 0x10)

3. Derive the RC4 key:

Using the MD5 hash output to derive an RC4 key, so the actual RC4 key is MD5(key_material).

1

CryptDeriveKey(Algid: 0x6801)

4. Encrypt/Decrypt based on arg2:

Same function handles both directions, controlled by the arg2 flag.

1
2
3
4

if (arg2 == 0)
    CryptDecrypt(...)
else
    CryptEncrypt(...)

Conclusion

RC4 remains one of the most commonly encountered encryption algorithms in malware, and being able to identify it quickly - whether implemented manually or via the Windows CryptAPI is a fundamental skill for any malware analyst. The two implementations look completely different in a decompiler, but the indicators are consistent enough that with practice they become immediately recognisable.

Malware, Internals, Encryption
Malware Internals Encryption
This post is licensed under CC BY 4.0 by the author.