Hacker Reversing Challenge 2007 Phase I Problem & Solution

Hacker Reversing Challenge 2007 Phase I 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 I Program

The target binary program for the phase I, can be downloaded from here. This contains the protected Windows binary program, readme file with instructions, the solved program and the solution by Hacker Challenge team.

Hacker Reversing Challenge Phase I Problem

Phase I 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 "10.9319" of the output.
Remove the limitation on an input data field of the code so that values greater than 210.5 are treated the same as values less than 210.5.

Hacker Reversing Challenge Phase I Solution and Analysis

The brief solution by Hacker Challenge team is included along with target program. 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 1 solution.

Step 1: Initial Analysis of the Target Program

Attacking the program started with analysis of the program using tools PEid (PE Packer Identifier) and PEditor (PE file viewer and editor). Here are the interesting things that have been found during this phase

PEid indicates no packer. That means either it is not packed at all or not packed with any known packer.
Looking at the sections in PEditor, the last section named 'JR' looks suspicious. Also the OEP lies in this section. This is possible indication that code is packed.
Import section looks normal that means there will not be much problem with unpacking the file.
Also import section contains couple of interesting APIs such as IsDebuggerPresent, GetTickCount etc which says what sort of anti-debugging tricks have been used.
TLS table is empty.That means there is no TLS trick to worry about. Some protectors use TLS callback functions to perform anti-debugging actions.

Next the target program is loaded into IDA Pro disassembler for further analysis. Looking at the sections in the disassembly mode, it is clear that 'text' section is encrypted. IDA makes it easy to write comments as new things are discovered while attack is going on. Also it is easy to distinguish between library calls and internal functions calls using IDA. After the initial analysis is completed, I executed the program in the cmd prompt to see the output. First time it displayed the message saying 'Missing password.txt'. Then I created the dummy text file with some values in it and named it as password.txt. This time it displayed the message saying 'Incorrect password'.

After collecting enough details about the program, it is time to get into action.

Step 2: Unpacking the Original Binary

The target program is loaded into OllyDbg with IDA pro showing disassembly of the same. Program starts execution at address 0x428288. After some series of jumps, it calls the function which begins at address 0x4284B9 and ends at 0x4286EB. This function goes through each section header in the PE file and unpacks them. Here is disassembly of main part of this function which checks for various sections by their name and then jumps to relevant code to unpack that section.

StartUnpacking:

004284C8 52 PUSH EDX

004284C9 50 PUSH EAX

; checks if section name is '.text'

004284CA 3E:813E 2E746578 CMP DWORD PTR DS:[ESI],7865742E

004284D1 0F84 C1000000 JE UnpackTextSection

; checks if section name is 'CODE'

004284D7 3E:813E 434F4445 CMP DWORD PTR DS:[ESI],45444F43

004284DE 0F84 B4000000 JE UnpackTextSection

; checks if section name is '.data'

004284E4 3E:813E 2E646174 CMP DWORD PTR DS:[ESI],7461642E

004284EB 0F84 E8000000 JE UnpackDataSection

; checks if section name is 'DATA'

004284F1 3E:813E 44415441 CMP DWORD PTR DS:[ESI],41544144

004284F8 0F84 DB000000 JE UnpackDataSection

; checks if section name is 'SSB'

004284FE 3E:813E 42535300 CMP DWORD PTR DS:[ESI],535342

00428505 74 50 JE SHORT final.00428557

; checks if section name is '.idata'

00428507 3E:813E 2E696461 CMP DWORD PTR DS:[ESI],6164692E

0042850E 0F84 06010000 JE final.0042861A

; checks if section name is '.edata'

00428514 3E:813E 2E656461 CMP DWORD PTR DS:[ESI],6164652E

0042851B 75 16 JNZ SHORT CheckRsrcSection

0042851D 52 PUSH EDX

0042851E 8BD5 MOV EDX,EBP

00428520 81C2 F0E74400 ADD EDX,44E7F0

00428526 F702 80000000 TEST DWORD PTR DS:[EDX],80

0042852C 5A POP EDX

0042852D 0F84 28010000 JE final.0042865B

CheckRsrcSection:

; checks if section name is '.rsrc'

00428533 3E:813E 2E727372 CMP DWORD PTR DS:[ESI],7273722E

0042853A 75 16 JNZ SHORT final.00428552

0042853C 52 PUSH EDX

0042853D 8BD5 MOV EDX,EBP

0042853F 81C2 F0E74400 ADD EDX,44E7F0

00428545 F702 80000000 TEST DWORD PTR DS:[EDX],80

0042854B 5A POP EDX

0042854C 0F84 42010000 JE final.00428694

00428552 E9 83010000 JMP GotoNextSection

GotoNextSection:

;esi=esi+40,go to next section header

004286DA 83C6 28 ADD ESI,28

004286DD 58 POP EAX

004286DE 5A POP EDX

004286DF 42 INC EDX

;are we done with 5 sections ?

004286E0 66:3E:3B57 06 CMP DX,WORD PTR DS:[EDI+6]

004286E5 0F85 DDFDFFFF JNZ StartUnpacking

004286EB C3 RETN

At the beginning of each loop ESI points to name of the section, for example '.text'. Since this program does not contain 'SSB', 'idata' & 'edata' section, that part of the code does not get executed.

Initially ESI points to '.text' (name of text section) and then jumps to address 0x428598. Here it checks if the section->PointerToRawData and section->SizeOfRawData are not NULL. Then it pushes all the relevant parameters and calls the function which starts at 0x42847C and ends at 0x4284B8. This function decrypts entire text section by performing various operations on each byte. After that it jumps to address 0x4286DA (look at the 'GotoNextSection' in the above code) where it moves to next section header.

Then it checks if we are done with unpacking all the 5 sections. Otherwise it goes back to code at 'StartUnpacking' (0x4284C8) and performs the similar operations on other sections. For next iteration ESI points to '.rdata' section, but no action is taken and it just moves to the next section.

Now ESI is pointing to '.data' section and it jumps to code at address 0x4285D9 which does basic checks and then calls the function at 0x4286EC which decrypts 'data' section. After unpacking 'data' section it moves to '.rsrc' section. After comparison it jumps to code at address 0x428694 which does some basic checks and calls the function at 0x428729 which does some flag checks etc. The last section to be checked is 'JR'. This time nothing happens and unpacking section comes to the end.

After the completion of unpacking process, it jumps to location 0x428890. There we have another jump which takes us to the location 0x4289D0. Here we have following code

004289D0 BA B8 94 40 00 mov edx, offset dword_4094B8
004289D5 FF E2 jmp edx

This code puts the address 0x4094B8 which lies in 'text' section into EDX and then jumps to it. This is nothing but the real OEP (Original Entry Point) of the target program.

Step 3: Dumping the Unpacked Program

Now the OllyDbg is standing still at real OEP 0x4094B8, it is time to dump the program using OllyDmp plugin. On launching OllyDmp it automatically fills in all the relevant values including the RVA of OEP as shown in the picture below. Note that 'Rebuild Import' checkbox is unchecked so as to dump the program without fixing the imports. On clicking the 'Dump' button, entire program from memory is dumped to file 'final_dmp.exe'.

Figure 1: Dumping the program using OllyDmp

Next ImpREC ( Import Reconstructor ) is launched to fix the imports. Now in the ImpREC, currently debugging process final.exe is selected, OEP field is changed 0x94B8 and then performed 'IAT Autosearch'. Then clicking on 'Get Imports' button, all the import functions from kernel32.dll is listed as shown in the picture below. Now the import table for the previously dumped file final_dmp.exe is fixed by clicking 'Fix Dump' button which creates new file final_dmp_.exe. To verify the entire operation, dumped program final_dmp_.exe is executed to see everything works as in original program.

Figure 2: Fixing the import table using ImpREC

Step 4: Starting with Unpacked Program

Now the fresh unpacked program final_dmp_.exe is launched into IDA pro for detailed analysis and also loaded into debugger, OllyDbg for live tracing. Quick analysis at IDA pro reveals that 'main ()' function begins at address 0x406F30.

Now after tracing a bit, arrived at location 0x406F82 where it calls the function 0x4065B0 which opens the 'password.txt' file. If the file is not found, then it throws up the error 'Missing password.txt' and exits. Otherwise it proceeds to read the data from the file, by calling the function which starts at 0x406410.

Step 5: Defeating the Password Protection

On reading data from the file, execution starts at address 0x406FE8 where it converts the input string value to long using 'atol () ' function. After this it perform various computations on this value from 0x406FF1 to 0x40700C as shown below.

; stores the input value into ecx
00406FF1 8B C8 mov ecx, eax

                                    ; performs series of operations on input
00406FF3     B8 31 0C C3 30         mov     eax, 30C30C31h
00406FF8     F7 E9                  imul    ecx
00406FFA     C1 FA 03               sar     edx, 3
00406FFD     8B C2                  mov     eax, edx
00406FFF     C1 E8 1F               shr     eax, 1Fh
00407002     03 C2                  add     eax, edx
00407004     6B C0 2A               imul    eax, 2Ah
00407007     8B D1                  mov     edx, ecx
00407009     83 C4 04               add     esp, 4

                                    ; Is computed value matches input?
0040700C     2B D0                  sub     edx, eax
0040700E     75 4E                  jnz     short loc_40705E

                                    ; check for zero input value
00407010     85 C9                  test    ecx, ecx
00407012     74 4A                  jz      short loc_40705E

                                    ; print 'Thank You' message
00407014     68 44 E5 41 00         push    offset strThankYou
00407019     68 F8 54 42 00         push    offset unk_4254F8
0040701E     E8 4D EF FF FF         call    PrintString_405f70

Once the operations are over, it checks if the final value matches with input value. In case of mismatch 'Incorrect password' message is shown and program is terminated. Otherwise it checks for zero input value and then proceeds to display the 'Thank You' message.

There are 2 ways to defeat this password protection check. One way is to provide the right password and another way is to patch the jump instructions. From the analysis of the mathematical operations it is clear that input value should be multiple of 0x2A (42 decimal) . Hence any password value which is multiple of 42 will succeed.

Another trivial way is to replace the 6 bytes from 0x40700E to 0x407012 with 0x90 (nop) so that above check succeeds always. I used this approach and modified these bytes to defeat this password protection mechanism.

Step 6: Bypassing Anti Debugging Tricks

Once the password check is completed, execution starts at address 0x407023 where it calls the function GetTickCount to get current time. The returned value is stored in EDI for using it later. This function is used to check if the program being traced in debugger.

Next it checks if the program is being debugged. This is done by checking if the 'BeingDebugged' flag in the PEB. If the program is debugged then this flag will be set to TRUE.This program uses following familiar instructions to perform this check.

00407039 64 A1 30 00 00 00 mov eax, large fs:30h

0040703F 0F B6 40 02 movzx eax, byte ptr [eax+2]

00407043 0A C0 or al, al

00407045 74 09 jz short loc_407050

This check is defeated by setting the value of 'BeingDebugged' to zero by using OllyAdvanced plugin. This is better method of defeating this check rather than patching the bytes since these checks are scattered throughout the program.

Next the program jumps to location 0x407077 where it calls the function IsDebuggerPresent to check for the presence of debugger. Internally this function checks the value of 'BeingDebugged' flag of PEB. Since this flag is already set to zero, there is no need to worry.

After bypassing these checks, the program arrives at the location 0x407088. There is nothing interesting happens other than some initialization until the program reaches address 0x40711B. Here it calls the GetTickCount function to get current time and then subtract the previous value from it. Next it does the check to verify if the difference is less than 0x7D0. If not then that means the program is being traced.

0040711B FF D6 call esi ; GetTickCount

0040711D 2B C7 sub eax, edi

0040711F 3D D0 07 00 00 cmp eax, 7D0h

00407124 76 07 jbe short loc_40712D

There are many ways to defeat this popular trick. One way is to use OllyAdvanced plugin which patches the GetTickCount function to make it return zero. But this will be risky if the program does checksum calculation of these API functions to make sure it is not altered.

Here I have set the hardware breakpoint on GetTickCount function. When this function returns, tick count is stored in the EAX register. So once the function returns, EAX value is changed to zero resulting in normal execution of the program.

This anti-debugging trick is used at many places in the program and it is bypassed using the above mentioned method.

Step 7: Reading the Input Values from data.txt

After this execution continues normally and at location 0x407146, it calls the function 401230. This is interesting function which does the initialization of local structure that is later used during computation of output 10.9319..!

Next after tracing few instructions, program arrives at the location 0x40719B. Here it invokes the function 4065B0 which basically opens the 'data.txt' file for reading. Then the instructions from address 0x4071B1 to 0x40726E, read the 10 input values from this file by calling the function at 406410. After which all these string values are converted into long/float by instructions ranging from 0x407282 to 0x4072EB by calling atol()/atof() functions.

Step 8: Removing the 210.5 Limit on Input Value

Next the program execution continues at location 0x4072F0. Here it checks if the input value is less than or equal to 210.5. The disassembly of the this verification process is shown below.

; Pushes 210.5 and then 8^th input value

; onto floating point stack

004072F0 DD 05 D8 E4 41 00 fld ds:dbl_41E4D8

004072F6 DD 45 D0 fld [ebp+68h+varFloat8]

004072F9 83 C4 28 add esp, 28h

; Is 220 > 210.5???

; st(0)=220 & st(1)=210.5

004072FC D8 D1 fcom st(1)

; store the floating point status register

004072FE DF E0 fnstsw ax

; The result is non zero if input value

; is less than or equal to 210.5 else it

; will be zero

00407300 F6 C4 41 test ah, 41h

00407303 75 08 jnz short loc_40730D

; input > 210.5, so use 210.5 only

00407305 DD D8 fstp st

00407307 EB 06 jmp short loc_40730F

loc_407309:

00407309 32 DB xor bl, bl

0040730B EB 71 jmp short loc_40737E

loc_40730D: ; input <= 210.5, use the input

0040730D DD D9 fstp st(1)

0040730F

If the input value is less than or equal to 210.5 then the value 210.5 is popped out from the floating point stack and supplied input value is used for computations. Otherwise the input value (which is greater than 210.5) is popped off the stack and value 210.5 is used for further operations.

This limitation on the input value is defeated to make the program use the input value in all the cases by changing the opcode at instruction 0x407303 from 75(JNZ) to EB(JMP). This way it ensures that always input value (rather than 210.5) is used in the output computations.

Step 9: Defeating the Anti-patching Technique

After a bit of tracing from 0x40730F, the program reaches the location 0x40737E. Here it calls the function starting at 401740 that does the checksum calculation. This is to prevent any binary patching of the program.

0040737E E8 BD A3 FF FF call 401740_CalculateChecksum

00407383 3D 5C B5 1D D8 cmp eax, 0D81DB55Ch

00407388 74 3A jz short loc_4073C4

Since the binary is already patched to bypass the limitation on input value as mentioned in the preceding section, checksum here will not be correct. Hence to defeat this checksum verification, opcode at 0x407388 is changed from 74(JZ)to EB(JMP), so that program always takes normal execution patch irrespective of checksum result.

Step 10: Finding Formula for 10.9319

Once the above patching is done, the program continues execution at 0x4073c4. Here it loads the target function address (0x401290) into the EDX and then calls it. This function at 0x401290 actually does the computation of output value 10.9319. However at the beginning of this function there are few anti-debugging checks such as GetTickCount, IsDebuggerPresent etc. Once these checks are bypassed using the methods described earlier, it arrives at the location 0x4012D8 where the actual computation happens to produce output value 10.9319. The disassembly of entire operations is given below.

004012D8 8B 86 C0 00 00 00 mov eax, [esi+0C0h] ; eax = 8

004012DE DB 05 68 30 42 00 fild dword_423068 ; st(0)=1efh(495)

004012E4 03 86 BC 00 00 00 add eax, [esi+0BCh] ; eax +=11h(17)

004012EA 5F pop edi

004012EB 03 86 B8 00 00 00 add eax, [esi+0B8h] ; eax+=0ah(10)

004012F1 8B C8 mov ecx, eax ; ecx=eax=23h(35)

004012F3 0F AF C8 imul ecx, eax ; ecx=4c9h(1225)

004012F6 89 44 24 08 mov [esp+0Ch+var_4], eax

004012FA DB 44 24 08 fild [esp+0Ch+var_4] ; st(0)=23h(35)

004012FE 89 4C 24 08 mov [esp+0Ch+var_4], ecx

; st(0)= st(0) * dbl_41E220

; st(0)= 0.0289345 = 35 * 0.0008267

00401302 DC 0D 20 E2 41 00 fmul ds:dbl_41E220

; st(0)= dbl_41E218 Ã¢â‚¬â€œ st(0)

; st(0)=1.080445= 1.10938-0.0289345

00401308 DC 2D 18 E2 41 00 fsubr ds:dbl_41E218

; push 4c9h(1225) onto float stack

; st(0) = 1225

0040130E DB 44 24 08 fild [esp+0Ch+var_4]

; st(0)=st(0) * dbl_41E210

; st(0)=0.00196= 1225 * 1.6e-6

00401312 DC 0D 10 E2 41 00 fmul ds:dbl_41E210

; st(1)=st(1)+st(0)=1.080445+0.00196

; After addition, perform POP on fl.stack

; Result: st(0)=1.082405, st(1)=495

00401318 DE C1 faddp st(1), st

; PUSH the value at address esi+30h

; then perform st(0) = st(0) * dbl_41E208

; result: st(0)=0.00849= 33 * 0.0002574

0040131A DB 46 30 fild dword ptr [esi+30h]

0040131D DC 0D 08 E2 41 00 fmul ds:dbl_41E208

; st(1)=st(1)Ã¢â‚¬â€œst(0)= 1.082405 - 0.00849

; After subtraction, POP from fl.stack

; Result: st(0)=1.0739, st(1)=495

00401323 DE E9 fsubp st(1), st

; st(1)=st(1)/st(0)=495/1.0739

; After division, POP from fl.stack

; Result: st(0)=460.9319

00401325 DE F9 fdivp st(1), st

; st(0) = st(0)+dbl_4248C0 =460.9319 + 0.0

00401327 DC 05 C0 48 42 00 fadd dbl_4248C0

; st(0) = st(0)- dbl_41E1B8=460.9319-450

; Result: st(0) = 10.9319 J

0040132D DC 25 B8 E1 41 00 fsub ds:dbl_41E1B8

; Finally store the result 10.9319 onto

; local variable

00401333 DD 96 98 00 00 00 fst qword ptr [esi+98h]

After couple of floating point operations, we arrive at location 0x40132D which produces final result, 10.9319. This value is stored into local variable for printing later. Then the function returns to main() after calculating few other output values.

The entire series of floating point operations for producing the output 10.9319 can be put in the following equation form. Here global variables start with 'g' and local variables start with 'local' prefix.

A = ( (local_ESI_C0h + local_ESI_BCh) + local_ESI_B8h)

X = {g_41E218 - (g_41E220 * A) } + { (A* A) * g_41E210}

Result= [{g_423068/(X -(local_ESI_30h * g_41E208))}+g_4248C0] - g_41E1B8

Though the value of g_4248C0 is zero it is included as it was used in computing the formula. The original solution from Hacker Challenge Team does not have this in the equation. As a result my entire 15 page report was termed 'PARTIAL Solution'. Looks like evaluators have forgotten basic maths :)

Step 11: Another Checksum Verification

Next in the main program execution continues from address 0x4073D4. Here we encounter series of printing operations which calls the function 0x405F70 for printing individual values. This goes on till the address 0x407615 where we encounter another checksum calculation. The disassembly of the checksum verification process is given below.

00407615 E8 E6 A0 FF FF call 401700_CalculateChecksum2

; verify if the checksum is correct?

0040761A 3D F7 B3 7A 50 cmp eax, 507AB3F7h

0040761F 74 0C jz short loc_40762D

; if checksum failed, then load new

; value into dbl_4248C0 from dbl_41E4C8

00407621 DD 05 C8 E4 41 00 fld ds:dbl_41E4C8

00407627 DD 1D C0 48 42 00 fstp dbl_4248C0

0040762D

loc_40762D:

0040762D 84 DB test bl, bl

This is the clever checksum verification than the one we encountered earlier. If the checksum is not correct then it just changes the value of one of the global variable dbl_4248C0 which is used in computation of final output values. Hence if there is any patching in the program, then the output will be different.

To defeat this checksum verification, one has to just change the opcode at 0040761F from 74(jz) to EB(jmp)so that it will follow normal execution path irrespective of the checksum result.

Then the program continues execution at 0x407641 where it prints remaining three rows by calling the function 0x406CE0. Finally the program comes to an end at 0x40767F.

Summary of Attack

Target program final.exe is unpacked to produce the original binary file.
Unpacked program is loaded into debugger and the anti-debugging tricks are defeated by using OllyAdvanced plug-in and making use of hardware breakpoints on system APIs.
Password protection is defeated by replacing 6 continuous bytes starting from address 0x40700E with nop (0x90)opcode.
Next the limitation on input value (210.5) is bypassed by modifying the opcode at location 0x407303 from 0x75(jnz) to 0xEB(jmp).
After that function which computes output value 10.9319 is found and reversed to produce the formula behind this operation.
Finally all the checksum verification methods are disabled by patching at the relevant locations so that program executes normally.

Conclusion

This is great challenge from reversing point of view especially due to usage of floating point computations. Packing the program with custom packer makes it difficult for casual cracker and prevents static analysis of the program using disassembler. Also the checksum verification technique is effective considering that program requires patching to defeat the various protections. Though the anti debugging techniques used in the program are basic ones, they are good enough to deceive new players entering this reversing game.

Download

Target Program & Solution for Hacker Challenge Phase I