Hacker Reversing Challenge 2007 Phase III Problem & Solution

Hacker Reversing Challenge 2007 Phase III Problem & Solution - www.SecurityXploded.com

About Hacker Reversing Challenge 2007

This is the international reverse engineering challenge conducted by U.S based security company. The purpose of this challenge is to evaluate the effectiveness of software protections. The results of this effort is used to improve the protection measures used in the softwares.

The contest is carried out in 3 phases where first and third phase involved breaking the protection of custom programs by using reverse engineering. The interesting part of this reversing challenge is the usage of floating point computations.

For more details on various phases and the rules, visit the Hacker Challenge website.

Hacker Reversing Challenge Phase III Program

The target binary program for the phase III, can be downloaded from here. This contains the protected Windows binary program, readme file with instructions and the final solved program.

Hacker Reversing Challenge Phase III Problem

Phase III of the challenge involved breaking the protection of Windows binary program that produces certain output. Goal of this challenge is to achieve following objectives

Reverse engineer the mathematical formula that results in the value "-59.0079" of the output.
Remove the limitation on an input data field of the code so that values of 200 or greater are treated the same as values less than 200.

Hacker Reversing Challenge Phase III Solution and Analysis

Here is the complete report of various steps involved in breaking the protection towards achieving the above mentioned objectives. This is the exact report that was submitted as part of Hacker Challenge Phase III solution.

Initial Analysis of the Target Program

The initial analysis of the program is done using the tools PEid, PEditor and IDA Pro. Here is the outcome of the analysis

PEid indicated no packer. That means nothing to worry about unpacking.
Looking at the import section using PEditor revealed the presence of several anti debugging tricks such as IsDebuggerPresent, QueryPerformanceFrequency, and GetTickCount etc.
Also the TLS table found to be empty. So no TLS callback functions are used.
IDA pro analysis revealed several obscured code sections which are decoded dynamically thus making static analysis more difficult.

Defeating the Various Protections

This program uses various anti-debugging protections coupled with tricks to prevent static analysis. Below are the more details about each of them.

Defeating Anti-Debugging Protection: IsDebuggerPresent

This is well known technique which uses IsDebuggerPresent function or directly read the value of PEB.BeingDebugged to check if the program is being debugged.

It is defeated by setting the PEB.BeingDebugged value to zero. Same can also be achieved using the following Ollyscript.

dbh // set the PEB.BeingDebugged to zero

Defeating Anti-Debugging Protection: Timer checks

This program uses function QueryPerformanceFrequency to detect any debugging activity. If this function is not supported, then it uses traditional GetTickCount to achieve the same.

This protection is defeated by patching the QueryPerformanceFrequency function to return zero so that it falls back to GetTickCount technique. Then GetTickCount function is patched to return zero. However this program uses intelligent approach by calling sleep(xtime) and then making sure that GetTickCount results in difference of time greater than xtime. This requires individual code patching. Here is the Ollyscript used for defeating these timer checks against debugging.

// patch the QueryPerformanceFrequency to return false
gpa "QueryPerformanceFrequency", "kernel32.dll"
mov [$RESULT], #33C0C20400# // xor eax, eax; retn 4;

// patch the GetTickCount to return zero
gpa "GetTickCount", "kernel32.dll"
mov [$RESULT], #33C0C3# // xor eax, eax; retn;

// Individual code patches for GetTickCount trick
mov [4020E7], #9090#
mov [403545], #EB09#
mov [402EA8], #9090#
mov [402EB8], #EB08#

Defeating Anti-Debugging Protection: SEH Traps

There are few SEH (Structured Exception Handling) traps which alters the code flow and final output. These SEH traps are implemented inside the functions starting at 401B70 and 401D80.

These tricks are defeated by replacing calls to these function at various places by using following code sequence "xor eax, eax; nop; nop; nop;". Here is the Ollyscript which achieves the same.

mov [401C3A], #33C0909090# // patch the call to 401D80
mov [401C43], #33C0909090# // patch the call to 401B70

mov [401F08], #33C0909090# // patch the call to 401B70
mov [402166], #33C0909090# // patch the call to 401D80

Defeating Protection Against Static Analysis

In the target program, there are 3 code sections which are decoded dynamically thus preventing static analysis. The decoding function starts at address 401C20 which dynamically builds following code sections

[402D50 to 402E2B] Size: DC //Decode function called from 402C0D
[402F20 to 402FFF] Size: E0 //Decode function called from 402CD4
[401EF0 to 401FDF] Size: F0 //Decode function called from 402D18

Defeating Check Against Code Section Integrity

This program calculates the checksum for certain code sections to verify if it is altered. The code section from address 402C15 to 402C58 performs checking for 402D50. Also the code section from address 402C5F to 402CA7 does checksum calculation of function starting at 401EF0.

During debugging there is nothing needs to be done. However while building final binary these checks can be prevented by using the jump instruction.

Producing the right Output with the Password

On running the program, it prints only few lines. After debugging, I have found that it performs certain calculations (402D81 - 402E28) and then compares the result with "4242" at instruction 402E0D. Since this comparison is failing, the flag value at address 402E24 is not set thus resulting in improper output.

This is fixed by replacing the jmp instruction at 402E22 with nop's through the following Ollyscript.

mov [402E22], #9090# // patch jmp instruction to display more lines

On patching this instruction, it produces the remaining output lines, but first 3 lines are still missing. After closely looking at the logic of the program, it is clear that first line of the input is already read at instructions 402D5F and 402D7C. Thus when it comes to input processing loop at 402EF0, reading starts with second line of input from data.txt. As a result, in the final output first 3 lines are missing.

The solution to this problem is tricky one. We need to add another input line at the top of data.txt by just copying the existing first line. Final input file, data.txt looks like this

// Final data.txt file
1 175 35 1 4 33 70 17
1 175 35 1 4 33 70 17
2 100 35 2 4 22 66 28 12
3 175 35 1 7 10 17 8 4 6 10 5
4 220 33 1 7 10 17 8 4 6 10 5
5 175 35 1 3 5 14 13
6 100 35 2 3 1 1 1

Breaking the Limitation of 200 in the Input

Below is the code section which checks if the second value in every input line exceeds 200.

; converts input value to floating point

00402F61 51 push ecx

00402F62 E8 B4 A5 00 00 call _atof

00402F67 DD 5D 48 fstp [ebp+78h+var_30]

00402F6A DD 05 E8 84 42+ fld ds:dbl_4284E8

00402F70 83 C4 04 add esp, 4

; compares value with 200

00402F73 DC 5D 48 fcomp [ebp+78h+var_30]

00402F76 DF E0 fnstsw ax

00402F78 F6 C4 05 test ah, 5

; if less than 200, jmp to loc_402F8B

00402F7B 7A 0E jp short loc_402F8B

; if more than 200, alter these values

00402F7D C7 45 48 77 4A+ mov dword ptr [ebp+78h+var_30], 0EB074A77h

00402F84 C7 45 4C FF FF+ mov dword ptr [ebp+78h+var_30+4], 4068FFFFh

00402F8B

loc_402F8B:

00402F8B

Looking at the code, it is clear that if the value exceeds 200 then the local variables are altered which results in wrong output.

This limitation is circumvented by replacing the conditional jump (jp) instruction at 402F7B with an unconditional jump (jmp) instruction. Following Ollyscript illustrates the same.

// patch for input limitation of 200
mov [402F7B], #EB0E#

Reverse Engineering a Formula

The function starting at 401EF0 computes the value of -59.0079. Here is the disassembly of the same. Also it uses the values from the 3rd row which is shown below.

//3rd row of the input, used for the formula.
3 175 35 1 7 10 17 8 4 6 10 5

; These instructions uses values from the input and

; performs simple arithmetic operations

00401F18 mov ecx, [esi+0D0h] ; ecx = 5

00401F1E sub ecx, [esi+0C4h] ; ecx = 5 Ã¢â‚¬â€œ 4 = 1

00401F24 mov eax, [esi+0C0h] ; eax = 8

00401F2A add ecx, [esi+0B8h] ; ecx = 1 + 10 = 11

00401F30 lea edx, [eax+eax*2] ; edx = 8 + 8*2 = 24

00401F33 lea eax, [edx+ecx*2] ; eax = 24 + 11*2 = 46

00401F36 sub eax, [esi+0CCh] ; eax = 46-10 = 36

00401F3C mov ecx, [esi+34h] ; ecx = 1

00401F3F sub eax, [esi+0BCh] ; eax = 36 Ã¢â‚¬â€œ 17 = 19

00401F45 add eax, [esi+0C8h] ; eax = 19 + 6 = 25

00401F4B cmp ecx, 1 ; true

00401F4E mov [ebp+var_4], eax ; var4 = 25

00401F51 jnz short loc_401F80 ; jump not taken

00401F53 fild [ebp+var_4] ; st0 = 25

00401F56 mov ecx, eax ; ecx = 25

00401F58 imul ecx, eax ; ecx = 25*25 = 625

00401F5B fmul ds:dbl_4284C0 ; st0 = 25*0.00045719

; st0 = 0.011429

00401F61 fsubr ds:dbl_4284B8 ; st0 = 1.21721-0.011429

; st0 = 1.20578

00401F67 mov [ebp+var_4], ecx ; var4 = 625

00401F6A fild [ebp+var_4] ; st0=625, st1=1.20578

00401F6D fmul ds:dbl_4284B0 ; st0=625*6.7e-07

; st0=0.00041875

00401F73 faddp st(1), st ; st0=1.20578+0.00041875

; st0=1.20619

00401F75 fild dword ptr [esi+30h]; st0=35, st1=1.20619

00401F78 fmul ds:dbl_4284A8 ; st0=35*0.00025696

; st0=0.0089935

00401F7E jmp short loc_401FB0

00401F80

;---------------------------------------------------------------------------

; This code block is not used here

00401F80 loc_401F80:

00401F80 cmp ecx, 2

00401F83 jnz short loc_401FB5

00401F85 fild [ebp+var_4]

00401F88 mov edx, eax

00401F8A imul edx, eax

00401F8D fmul ds:dbl_4284A0

00401F93 fsubr ds:dbl_428498

00401F99 mov [ebp+var_4], edx

00401F9C fild [ebp+var_4]

00401F9F fmul ds:dbl_428490

00401FA5 faddp st(1), st

00401FA7 fild dword ptr [esi+30h]

00401FAA fmul ds:dbl_428488

;---------------------------------------------------------------------------

00401FB0

00401FB0 loc_401FB0:

00401FB0 fsubp st(1), st ; st0=st1-st0=1.20619-0.0089

; st0= 1.1972

00401FB2 fstp [ebp+var_C] ; varC = 1.1972

00401FB5

00401FB5 loc_401FB5:

00401FB5 fild dword_42EBB8 ; st0= 510

00401FBB mov ecx, esi ;

00401FBD fdiv [ebp+var_C] ; st0 = 510/1.1972

; st0 = 425.992

00401FC0 fadd dbl_42EBB0 ; st0 = 425.992 + 0

; Here comes the final value -59.0079

;

00401FC6 fsub ds:dbl_428440 ; st0 = 425.992-485

; st0 = -59.0079

Here is the final formula for -59.0079
Here variable with prefix 'd' refers to input values from data.txt and variables with prefix 'g' refers to global values. All the input values used in this formula are from the third line as given below.

Reference, 3rd input line
3 175 35 1 7 10 17 8 4 6 10 5

A = [ (d12 - d9 + d6) * 2 ] + d8 + d8 * 2 - d11 - d7 + d10

B = [ ( g4284B8 - A * g4284C0 ) + (A * A * g4284B0) ] - (d3 * g4284A8)

Result = ( g42EBB8 / B) - g428440

After substituting the values, the above formula takes the following form

A = [ (5 - 4 + 10) * 2 ] + 8 + 8 * 2 - 10 - 17 + 6 = 25

B = [(1.21721 - 25 * 0.00045719) + (25 * 25 * 6.7e-07)] - (35 * 0.00025696)
B = 1.1972

Result = ( 510 / 1.1972 ) - 485 = -59.0079

Constructing the Final Binary Program

Once all the protections, limits are broken, it is time to construct the final executable program.

Here are the steps involved in building final binary.

Dump the decoded bytes for code section from 402D50 to 402E2B and restore the same in the original program final.exe
Next patch the decode function call (it is no longer required) and checksum calculation functionality by putting the jmp instruction (EB 58) at 402BFE.
Similarly dump the decoded bytes for code section from 402F20 to 402FFF and restore the same in original program.
Now patch the decode function call which decodes above code section by placing jump instruction (EB 1A) at 402CBD. Also patch the instruction at 402CDF with 3 nops (90 90 90).
Then patch the program to display more lines by defeating the comparison at 402E22 by replacing it with 2 nops ( 90 90)
Finally remove the limitation of 200 on input value by replacing conditional jump (jp) with unconditional jump(jmp, EB 0E) instruction at 402F7B.

Conclusion

This program has better protection mechanism than the one in phase I of the challenge. Static analysis preventive steps along with the anti debugging techniques make the challenge really entertaining.

At the end all the protections are broken, limitation of input value is circumvented and formula for the output value is reverse engineered successfully.

Download

Target Program & Solution for Hacker Challenge Phase III