There is something that we come across almost daily when we analyze malware in the VRT: RC4. We recently came across CVE-2014-1776 and like many malware samples and exploits we analyze, RC4 is used to obfuscate or encrypt what it is really doing. There are many ways to implement RC4 and it is a very simple, small algorithm. This makes it very common in the wild and in various standard applications. Open-source C implementations can be found on several websites such asApple.com and OpenSSL.org.

What is RC4?  
RC4 was designed by Ron Rivest of RSA Security in 1987. RC4 is a fast and simple stream cipher that uses a pseudo-random number generation algorithm to generate a key stream. This key stream can be used in an XOR operation with plaintext to generate ciphertext. The same key stream can then be used in an XOR operation against the ciphertext to generate the original plaintext.

While it is still common in malware, RC4 has been legitimately implemented in a number of areas where speed and privacy are of concern. In the past, both WEP and TLS both used RC4 to protect data sent across the wire. However, last Fall,Microsoft recommended that customers disable RC4 by enabling TLS1.2 and AES-GCM.

For more information including a detailed history of RC4, check out theWikipedia article.

Why is it used in malware?  
Increasingly, we find that RC4 is used to encode data that is sent to a remote server to be decrypted on the other side using a pre-shared key. This makes detection a bit trickier (but not impossible) and also makes it harder to determine exactly what is being sent across the wire. What we will usually do when we think we've come across some sort of encryption is determine the source of it and whether the data being sent is static (for matching purposes) and what exactly that data is.

How does it work?
*Note: For these examples, I will be using a variant of the Coremex Search Engine Hijacker (MD5: 70E2090D5DEE18F3E45D38BF254EFF87) after it has resumed its suspended child process.

RC4 is implemented in two main phases:

1. A Key Scheduling Algorithm is executed using a symmetric key to create an array of 256 bytes (0x100h).

2. This array is then used in a pseudo-random number generation algorithm to generate a cipher stream that can be decoded using the same key.

Many books and internet articles will represent theKey Scheduling Algorithm (KSA) with the following Pseudocode:

To better understand how the algorithm works, split it into multiple sections.

Section 1:

Create and Initialize the Substitution Box

This section creates an array (or an "SBox"/Substitution Box) where each value equals its position in the array from 0-255 (0x00-0xFF) , this is also known as its identity permutation:

This initial table-creation is a key indicator when looking for this type of encryption in malware samples. For this sample, the RC4 KSA was initialized using the following loop in x86 assembly code:

100020E5xoreax,eax    ; Initialize counter to 0
 loop:

100020E7                    ; Give each array index its identity value

100020E7mov[eax+ecx],al; using EAX as a counter/value:

100020E7                    ; S[0] = 0x00 ... S[256] = 0xFF

100020EAinceax         ; Increment counter by 1

100020EBcmpeax,100h   ; Compare counter value to 256 (0x100h) // NOTE THE 100h!

100020F0jlshort loop ; Loop around if counter < 256

Note the instruction at 0x100020EB 100h is a great value to search a binary for in a disassembler like IDA Pro. Looking for an instruction that is comparing a register to 100h can often point you in the right direction, especially if you know the malware is using RC4 ahead of time.

While looking at the memory dump that [eax+ecx] points to after this loop completes, you can see the newly-constructed SBox that looks like the one above:

0012FBB0  00 01 02 03 04 05 06 07  08 09 0A 0B 0C 0D 0E 0F  ................

0012FBC0  10 11 12 13 14 15 16 17  18 19 1A 1B 1C 1D 1E 1F  ................

0012FBD0  20 21 22 23 24 25 26 27  28 29 2A 2B 2C 2D 2E 2F   !"#$%&'()*+,-./

0012FBE0  30 31 32 33 34 35 36 37  38 39 3A 3B 3C 3D 3E 3F  0123456789:;<=>?

0012FBF0  40 41 42 43 44 45 46 47  48 49 4A 4B 4C 4D 4E 4F  @ABCDEFGHIJKLMNO

0012FC00  50 51 52 53 54 55 56 57  58 59 5A 5B 5C 5D 5E 5F  PQRSTUVWXYZ[\]^_

0012FC10  60 61 62 63 64 65 66 67  68 69 6A 6B 6C 6D 6E 6F  `abcdefghijklmno

0012FC20  70 71 72 73 74 75 76 77  78 79 7A 7B 7C 7D 7E 7F  pqrstuvwxyz{|}~.

0012FC30  80 81 82 83 84 85 86 87  88 89 8A 8B 8C 8D 8E 8F  Ç.éâäàåçêëèïî.Ä.

0012FC40  90 91 92 93 94 95 96 97  98 99 9A 9B 9C 9D 9E 9F  .æÆôöòûùÿÖÜ¢£.Pƒ

0012FC50  A0 A1 A2 A3 A4 A5 A6 A7  A8 A9 AA AB AC AD AE AF  áíóúñѪº¿¬¬½¼¡«»

0012FC60  B0 B1 B2 B3 B4 B5 B6 B7  B8 B9 BA BB BC BD BE BF  ¦¦¦¦¦¦¦++¦¦+++++

0012FC70  C0 C1 C2 C3 C4 C5 C6 C7  C8 C9 CA CB CC CD CE CF  +--+-+¦¦++--¦-+-

0012FC80  D0 D1 D2 D3 D4 D5 D6 D7  D8 D9 DA DB DC DD DE DF  ---++++++++¦_¦¦¯

0012FC90  E0 E1 E2 E3 E4 E5 E6 E7  E8 E9 EA EB EC ED EE EF  aßGpSsµtFTOd8fen

0012FCA0  F0 F1 F2 F3 F4 F5 F6 F7  F8 F9 FA FB FC FD FE FF  =±==()÷˜°··vn²¦

Now that the table has been initialized, it’s time to scramble the box.

Section 2:

Scramble SBox with Key “0006” (ASCII 0x30303036)

This routine takes the initialized table and performs various byte-swaps against the table using the key and its length (keys can range from 1->255 bytes in length). Here is how this sample implemented this routine. Note that the exact assembly instructions will vary amongst compilers, platforms and languages.

100020F4 loop:              ; ECX = S[0] | EDI = j

100020F4mov    eax,esi        ; Initialize EAX

100020F6cdq                       ; EAX -> EDX:EAX (with sign)

100020F7idiv   [esp+0Ch+keylen]        ; EDX = i mod keylen

100020FBmov    bl,[esi+ecx]       ; BL = S[i]

100020FEmov    eax,[esp+0Ch+key]  ; EAX = key

10002102movzxeax,byteptr[edx+eax]; EAX = key[i mod keylen]

10002106add    eax,edi                ; EAX = (j + key[i mod keylen])

10002108movzxedx,bl            ; EDX = S[i]

1000210Badd    edx,eax                ; EDX = (j + S[i] + key[i mod keylen])

1000210Dand    edx,0FFh               ; Another way to mod 255

10002113mov    edi,edx            ; j = (j + S[i] + key[i mod keylen])

10002115mov    al,[edi+ecx]       ; AL = s[j]

10002118mov    [esi+ecx],al   ; S[i] = S[j]

1000211Binc    esi                ; i++

1000211Ccmp    esi,100h           ; Check if i < 256 // NOTE THE 100h!

10002122mov    [edi+ecx],bl       ; S[j] = S[i]

10002125jl     shortloop; Loop if Less  In IDA Pro, the SBox Scramble loop following the Initialization loop may resemble these basic blocks:

 Manually calculating at least the first few bytes of this example with a pencil and a piece of paper will help make it more clear how the bytes are swapped to generate this new SBox:

Initialized SBox:

 For the first byte of the Key “0006”, ( Key[0] ) is “0", remember this is ASCII “0x30>”:

j :=(j + S[i]+ key[i mod keylength])mod256

swap values of S[i]andS[j]

i =0// first round

j =(j+ S[i]+ key[imodkeylength])mod0x100

=(0+ S[0x00]+ key[0mod4])mod0x100

=(0+0+ key[0])mod0x100

=(0+0x30)mod0x100

=0x30mod0x100

=0x30

S[0x0]=0x30

S[0x30]=0x00
 
After bytes S[0x00] and S[0x30] are swapped, the resulting table looks like this:

 For the second byte of the Key “0006”, ( Key[1] ) is also “0”, or ASCII “0x30”:

i =1// second round

j =(j+ S[i]+ key[imodkeylength])mod0x100

=(0x30+S[0x01]+ key[1mod4])mod0x100

=(0x30+1+key[1])mod0x100

=(0x31+0x30)mod0x100

=0x61mod0x100

=0x61

S[0x1]=0x100

S[0x61]=0x100
 After bytes S[0x01] and S[0x61] are swapped, the resulting table looks like this:

 The algorithm will continue to perform this calculation 256 times. Note that these values will continue to be swapped out and will even swap previously-swapped bytes as well. Using the key “0006”, the malware sample will end up generating the following SBox on the stack (I added the corresponding SBox array indexes for visualization purposes only):

S[00] | 0012FBB0  18 8A 98 7B|16 35 F4 A8|C0 A5 53 94|D0 0D 87 90| 

S[10] | 0012FBC0  2B 11 BA 26|08 25 C7 75|EB C6 83 D4|20 12 73 DB|

S[20] | 0012FBD0  1B 4E FF D3|EF 72 50 2E|B9 33 AF DC|6C C9 42 8C|

S[30] | 0012FBE0  BC 29 3A E8|EC 3B E7 54|44 F5 C3 3F|3C A9 32 17|

S[40] | 0012FBF0  59 60 DF 23|F0 6A B7 89|8B 43 7E C2|47 A3 37 A6|

S[50] | 0012FC00  34 A7 67 95|D8 B1 46 D9|56 28 A2 5B|7D 4C 41 7F|

S[60] | 0012FC10  5E AE 85 88|B2 9C 9B 0F|0A AB 8D 6E|ED 96 40 92|

S[70] | 0012FC20  45 1A F9 CE|B0 3E 9D 1D|68 1E E3 13|2A 51 D6 B4|

S[80] | 0012FC30  EE 58 D5 E1|D1 BB 39 4A|4F 15 07 B8|80 69 E4 FC|

S[90] | 0012FC40  5A 21 A1 1C|7C 9A 0E 5F|FD CB 02 B5|FA BD 57 86|

S[A0] | 0012FC50  E9 8E CA E5|5D 19 6F AA|4D CD 71 F2|BE 49 0B E2|

S[B0] | 0012FC60  F1 79 A0 D2|B6 DD F6 F8|2F E6 78 C1|52 CF 05 04|

S[C0] | 0012FC70  E0 6D 70 97|99 24 FE 06|4B 91 76 A4|B3 FB 63 09|

S[D0] | 0012FC80  81 64 00 82|5C C5 EA 36|AD 03 C8 0C|1F 84 48 C4|

S[E0] | 0012FC90  74 31 01 55|62 66 8F 9F|38 61 F7 BF|27 7A 22 AC|

S[F0] | 0012FCA0  9E 65 77 F3|6B 2C DE DA|30 14 3D CC|2D 93 D7 10|

Section 3:

Generate the Key Stream and Encode Data

The next step is to use this newly-created SBox to encode the data. This is done by creating a keystream using the SBox and this algorithm. The result, K is then used in an XOR operation with each byte of the plaintext to generate the encrypted data.

This routine takes the modified SBox and again performs various byte-swaps against the table. It then uses this information to generate the keystream(K). This stream is XOR'd against the plaintext until all of the plaintext has been encoded. If the length of the plaintext exceeds the length of the keystream, the stream starts over at K[0]. Here is how this sample implemented the routine:

Note that this sample used the following structure (other implementations may use u_char for indexes) to store the SBox and its two counters:

struct rc4_state

{

u_char perm[256]; // SBox

__int32 index1;// i

__int32 index2;// j

};

This sample encodes various data about the victims machine and sends the data encoded with this RC4 stream to its Command and Control server. This section of the malware just happens to be encoding a hash of one of my system files. The original hash that it encodes is: EA497F6BD6555BA85127CE083A513BE8:
 10002174loop:

10002174movecx,[ebp+68h+state.index1]; ECX = i

10002177incecx                    ; i += 1

10002178andecx,esi            ; i = i mod 0x100

1000217Amov[ebp+68h+state.index1],ecx; Store i

1000217Dleaedx,[ebp+ecx+68h+state]    ; EDX = *S[i]

10002184movzx     ecx,byteptr[edx]    ; ECX = S[i]

10002187addecx,[ebp+68h+state.index2]; ECX = j + S[i]

1000218Aandecx,esi                ; ECX = (j + S[i]) mod 0x100

1000218Cmov[ebp+68h+state.index2],ecx; j = (j + S[i]) mod 0x100

1000218Fmoval,[ebp+ecx+68h+state.perm]; AL = S[j]

10002196movzx      ebx,byteptr[edx]   ; EBX = S[i]

10002199mov[edx],al               ; S[i] = S[j]

1000219Bmoveax,[ebp+68h+state.index2]; EAX = j

1000219Emov[ebp+eax+68h+state.perm],bl; S[j] = S[i]

100021A5moveax,[ebp+68h+Plaintext]     ; EAX = Plaintext

100021A8movedx,[ebp+68h+state.index1]   ; EDX = i

100021ABmovzx     edx,[ebp+edx+68h+state.perm]; EDX = S[i]

100021B3leaecx,[edi+eax]; ECX = *Plaintext[x]

100021B6moveax,[ebp+68h+state.index2]; EAX = j

100021B9movzx     eax,[ebp+eax+68h+state.perm]; EAX = S[j]

100021C1addeax,edx; EAX = S[i] + S[j]

100021C3andeax,esi; EAX = (S[i] + S[j]) mod 0x100

100021C5moval,[ebp+eax+68h+state.perm]; AL = S[(S[i] + S[j]) mod 0x100]

100021CCxor[ecx],al; Plaintext[x] ^ Output K

100021CEincedi; x++

100021CFcmpedi,[ebp+68h+arg_4]; Check if x < len(Plaintext)

100021D2jbshortloop; Loop if x < len(Plain  In IDA Pro, the RC4_Crypt loop may resemble these basic blocks:

Once the length of the plaintext is met, the keystream K is completely generated. As each value of K was generated, it was used to XOR the complimentary byte of the plaintext, in this case it looked like this:

To decrypt the ciphertext, simply reverse the process:

Exercise:

Putting it all together with Python
I implemented RC4 in Python, treating input as strings and outputting the SBox contents both before and after scrambling.

I've linked the Python code here: rc4Gen.py