Challenges.re - RE 03#

The Challenges.re is a website with compilation of Reverse Engineering exercises, I’m writing this document for me only, to exercise my knowledge with assembly and reverse engineering. If you want to solve these exercises by yourself one day, please do not read my solution, try for yourself, my answer can be wrong, so don’t trust me, trust the process.

Question#

Reverse Engineering challenge #3. Tags: . What does this code do? The function has array of 64 32-bit integers, I removed it in each assembly code snippet to save space. The array is:

int v[64]=
	{ -1,31, 8,30, -1, 7,-1,-1, 29,-1,26, 6, -1,-1, 2,-1,
	  -1,28,-1,-1, -1,19,25,-1, 5,-1,17,-1, 23,14, 1,-1,
	   9,-1,-1,-1, 27,-1, 3,-1, -1,-1,20,-1, 18,24,15,10,
	  -1,-1, 4,-1, 21,-1,16,11, -1,22,-1,12, 13,-1, 0,-1 };

Assembly Code#

f:
	mov	edx, edi
	shr	edx
	or	edx, edi
	mov	eax, edx
	shr	eax, 2
	or	eax, edx
	mov	edx, eax
	shr	edx, 4
	or	edx, eax
	mov	eax, edx
	shr	eax, 8
	or	eax, edx
	mov	edx, eax
	shr	edx, 16
	or	edx, eax
	imul	eax, edx, 79355661 ; 0x4badf0d
	shr	eax, 26
	mov	eax, DWORD PTR v[0+rax*4]
	ret

With comments each line:

f: 									; Function method
	mov	edx, edi					; Move data from EDI to EDX
	shr	edx 						; Shift right EDX 1 bit (EDX / 2) 0x2
	or	edx, edi 					; Make and OR comparison EDX with EDI and store in EDX
	mov	eax, edx 					; Move data from EDX to EAX
	shr	eax, 2 						; Shift right EAX 2 bits (EDX / 4) 0x4
	or	eax, edx 					; Make and OR comparison EAX with EDX and store in EAX
	mov	edx, eax 					; Move data from EAX to EDX
	shr	edx, 4 						; Shift right EDX 4 bits (EDX / 16) 0x10
	or	edx, eax 					; Make and OR comparison EDX with EAX and store in EDX
	mov	eax, edx 					; Move data from EDX to EAX
	shr	eax, 8 						; Shift right EAX 8 bits (EDX / 256) 0x100
	or	eax, edx 					; Make and OR comparison EAX with EDX and store in EAX
	mov	edx, eax 					; Move data from EAX to EDX
	shr	edx, 16 					; Shift right EDX 16 bits (EDX / 65536) 0x10000
	or	edx, eax 					; Make and OR comparison EDX with EAX and store in EDX
	imul	eax, edx, 79355661 		; (0x4badf0d) Multiply EDX with 79355661 and store in EAX
	shr	eax, 26  					; Shift right EAX 26 bits (EAX / 67108864) 0x4000000
	mov	eax, DWORD PTR v[0+rax*4] 	; Move v[0+RAX*4] DWORD to EAX
	ret

Making a table of pseudo-code, it looks something like:

OP	Arg1	Arg2	Arg3	Pseudo-code
MOV	EDX	EDI		EDX = EDI
SHR	EDX	1		EDX = EDX » 1
OR	EDX	EDI		EDX = EDI \| EDX
MOV	EAX	EDX		EAX = EDX
SHR	EAX	2		EAX = EAX » 2
OR	EAX	EDX		EAX = EDX \| EAX
MOV	EDX	EAX		EDX = EAX
SHR	EDX	4		EDX = EDX » 4
OR	EDX	EAX		EDX = EAX \| EDX
MOV	EAX	EDX		EAX = EDX
SHR	EAX	8		EAX = EAX » 8
OR	EAX	EDX		EAX = EDX \| EAX
MOV	EDX	EAX		EDX = EAX
SHR	EDX	16		EDX = EDX » 16
OR	EDX	EAX		EDX = EAX \| EDX
IMUL	EAX	EDX	79355661	EAX = EDX * 0x4badf0d
SHR	EAX	26		EAX = EAX » 26
MOV	EAX	DWORD PTR v[0+rax*4]		EAX = (int)v[RAX]
RET				return EAX

And trying to reverse into c code:

// Type your code here, or load an example.
int v[64]=
	{ -1,31, 8,30, -1, 7,-1,-1, 29,-1,26, 6, -1,-1, 2,-1,
	  -1,28,-1,-1, -1,19,25,-1, 5,-1,17,-1, 23,14, 1,-1,
	   9,-1,-1,-1, 27,-1, 3,-1, -1,-1,20,-1, 18,24,15,10,
	  -1,-1, 4,-1, 21,-1,16,11, -1,22,-1,12, 13,-1, 0,-1 };

int f(int num) {

    num|=(num>>1);
    num|=(num>>2);
    num|=(num>>4);
    num|=(num>>8);
    num|=(num>>16);

    num*=79355661;

    num>>=26;

    return v[num];
}

With that information we can make a table of possible results:

input	output	decimal	In Array
0	0x0	0	-1
1	0x1	1	31
2-3	0x3	3	30
4-7	0x8	8	29
8-15	0x11	17	28
16-31	0x24	36	27
32-63	0x0a	10	26
64-127	0x16	22	25
128-255	0x2d	45	24
256-511	0x1c	28	23
512-1023	0x39	57	22
1024-2047	0x34	52	21
And so go on

What the code does#

It takes the most valuable Left bit, expand to be filled all the way to the right, the result is then multiplied by a magic number : 79355661.

This number make a result that is filtered by shifting 26 bits to the right. Making it range from 0 to 63, the possible numbers to gather in the v[] array.

The result will then gather a value inside the array. In this case the value 1 returns 31, the value 2 and 3 returns 30, etc.

It’s decrementing a value in each bit reached to the left. (check table above)

This could be used as an obfuscation type of code. Putting malware to be read in an unusual order, tricking known antivirus database standards.