Hacker Reversing Challenge 2007 Phase III Problem & Solution -
Hacker Reversing Challenge 2007 Phase III Problem & Solution
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
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





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




                        ; 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 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 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.
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.
Target Program & Solution for Hacker Challenge Phase III
See Also
   Hacker Reversing Challenge 2007 
   Hacker Reversing Challenge 2007 Phase I Problem and Solution
   Tutorial on floating point calculations in assembly 
   Unpacking UPX packed binary using OllyDbg 
   Exposing the covert way to find the reference count of DLL.