CMU Bomb
About
A great introduction to binary reversing, it's a series of 6 levels written by a professor at Carnegie Mellon. I'd recommend brushing up on your assembly and GDB. The binary is available here.
Tools
The only tool I used to solve this challenge was GDB (with GEF installed). Any similar interactive debugger such as radare2 will work.
Hints
In the function phase_1() our input string is compared to a hard-coded string.
read_six_numbers() reads an input string into an array of six integers. phase_2() then iterates over the array and verifies that this sequence of numbers satisfies a certain property.
Not all tests need to be passed. Figure out how adjusting [ebp-0xc] changes where you jump.
You should read up on the Fibonacci sequence
This function generates a new string using the string located at 0x804b220 and your input ASCII values modulo 16.
You should be familiar with linked lists.
In order to access it, take a look at phase_defused().
Solutions
Before we start solving individual challenges, let's take a look at the framework under which each of the challenges are set up. Let's start by disassembling the main() function:
0x080489b0 <+0>: push ebp ; set up stack frame
0x080489b1 <+1>: mov ebp,esp
0x080489b3 <+3>: sub esp,0x14
0x080489b6 <+6>: push ebx
0x080489b7 <+7>: mov eax,DWORD PTR [ebp+0x8] ; eax = argc
0x080489ba <+10>: mov ebx,DWORD PTR [ebp+0xc] ; ebx = argv
0x080489bd <+13>: cmp eax,0x1 ; if argc == 1, use stdin
0x080489c0 <+16>: jne 0x80489d0 <main+32>
0x080489c2 <+18>: mov eax,ds:0x804b648 ; infile = stdin
0x080489c7 <+23>: mov ds:0x804b664,eax
0x080489cc <+28>: jmp 0x8048a30 <main+128> ; goto init_bomb
0x080489ce <+30>: mov esi,esi
0x080489d0 <+32>: cmp eax,0x2 ; if argc == 2, read file
0x080489d3 <+35>: jne 0x8048a10 <main+96> ; else print correct usage, exit
0x080489d5 <+37>: add esp,0xfffffff8 ; infile = fopen(argv[1], 'r')
0x080489d8 <+40>: push 0x8049620
0x080489dd <+45>: mov eax,DWORD PTR [ebx+0x4]
0x080489e0 <+48>: push eax
0x080489e1 <+49>: call 0x8048880 <fopen@plt>
0x080489e6 <+54>: mov ds:0x804b664,eax
0x080489eb <+59>: add esp,0x10
0x080489ee <+62>: test eax,eax
0x080489f0 <+64>: jne 0x8048a30 <main+128> ; read successful, goto init_bomb
0x080489f2 <+66>: add esp,0xfffffffc ; failed to read argv[1], exit
0x080489f5 <+69>: mov eax,DWORD PTR [ebx+0x4]
0x080489f8 <+72>: push eax
0x080489f9 <+73>: mov eax,DWORD PTR [ebx]
0x080489fb <+75>: push eax
0x080489fc <+76>: push 0x8049622
0x08048a01 <+81>: call 0x8048810 <printf@plt>
0x08048a06 <+86>: add esp,0xfffffff4
0x08048a09 <+89>: push 0x8
0x08048a0b <+91>: call 0x8048850 <exit@plt> ; exit
0x08048a10 <+96>: add esp,0xfffffff8 ; too many args, exit
0x08048a13 <+99>: mov eax,DWORD PTR [ebx]
0x08048a15 <+101>: push eax
0x08048a16 <+102>: push 0x804963f
0x08048a1b <+107>: call 0x8048810 <printf@plt>
0x08048a20 <+112>: add esp,0xfffffff4
0x08048a23 <+115>: push 0x8
0x08048a25 <+117>: call 0x8048850 <exit@plt> ; exit
0x08048a2a <+122>: lea esi,[esi+0x0]
0x08048a30 <+128>: call 0x8049160 <initialize_bomb> ;init_bomb:
0x08048a35 <+133>: add esp,0xfffffff4 ; print welcome message
0x08048a38 <+136>: push 0x8049660
0x08048a3d <+141>: call 0x8048810 <printf@plt>
0x08048a42 <+146>: add esp,0xfffffff4
0x08048a45 <+149>: push 0x80496a0
0x08048a4a <+154>: call 0x8048810 <printf@plt>
0x08048a4f <+159>: add esp,0x20 ; read line
0x08048a52 <+162>: call 0x80491fc <read_line>
0x08048a57 <+167>: add esp,0xfffffff4
0x08048a5a <+170>: push eax
0x08048a5b <+171>: call 0x8048b20 <phase_1> ; test against phase 1
0x08048a60 <+176>: call 0x804952c <phase_defused> ; test for success
0x08048a65 <+181>: add esp,0xfffffff4
0x08048a68 <+184>: push 0x80496e0
0x08048a6d <+189>: call 0x8048810 <printf@plt> ; success message
...
0x08048b19 <+361>: mov esp,ebp ; return 0
0x08048b1b <+363>: pop ebp
0x08048b1c <+364>: ret
Okay, so it looks like we can attempt challenges in one of two ways: by providing input through stdin, or a text file given as a command-line argument. If either method fails, the program exits. Then, for each challenge, read_line() is called, phase_n() runs, phase_defused() is called, and a success message is printed.
Now let's examine phase_defused(), since it's called after each phase:
0x0804952c <+0>: push ebp
0x0804952d <+1>: mov ebp,esp
0x0804952f <+3>: sub esp,0x64
0x08049532 <+6>: push ebx
0x08049533 <+7>: cmp DWORD PTR ds:0x804b480,0x6 ; num_input_strings ?= 6
0x0804953a <+14>: jne 0x804959f <phase_defused+115> ; if not, return
0x0804953c <+16>: lea ebx,[ebp-0x50] ; sscanf(???, "%d %s", input_num, input_string)
0x0804953f <+19>: push ebx
0x08049540 <+20>: lea eax,[ebp-0x54]
0x08049543 <+23>: push eax
0x08049544 <+24>: push 0x8049d03
0x08049549 <+29>: push 0x804b770
0x0804954e <+34>: call 0x8048860 <sscanf@plt>
0x08049553 <+39>: add esp,0x10 ; if failed, goto success
0x08049556 <+42>: cmp eax,0x2
0x08049559 <+45>: jne 0x8049592 <phase_defused+102>
0x0804955b <+47>: add esp,0xfffffff8 ; input_string ?= "austinpowers"
0x0804955e <+50>: push 0x8049d09
0x08049563 <+55>: push ebx
0x08049564 <+56>: call 0x8049030 <strings_not_equal>
0x08049569 <+61>: add esp,0x10
0x0804956c <+64>: test eax,eax
0x0804956e <+66>: jne 0x8049592 <phase_defused+102> ; if not, goto success
0x08049570 <+68>: add esp,0xfffffff4 ; call secret_phase
0x08049573 <+71>: push 0x8049d20
0x08049578 <+76>: call 0x8048810 <printf@plt>
0x0804957d <+81>: add esp,0xfffffff4
0x08049580 <+84>: push 0x8049d60
0x08049585 <+89>: call 0x8048810 <printf@plt>
0x0804958a <+94>: add esp,0x20
0x0804958d <+97>: call 0x8048ee8 <secret_phase>
0x08049592 <+102>: add esp,0xfffffff4 ;success: print "congrats"
0x08049595 <+105>: push 0x8049da0
0x0804959a <+110>: call 0x8048810 <printf@plt>
0x0804959f <+115>: mov ebx,DWORD PTR [ebp-0x68] ; return
0x080495a2 <+118>: mov esp,ebp
0x080495a4 <+120>: pop ebp
0x080495a5 <+121>: ret
This is interesting. It looks like phase_defused() pretty much always returns success, with a few notable exceptions: num_input_strings != 6, sscanf() fails, or if our input string is "austinpowers". In the last case, we're brought to a function called secret_phase(). The solution for this secret level will be described later.
Here's the disassembled phase_1():
0x08048b20 <+0>: push ebp ; set up stack frame
0x08048b21 <+1>: mov ebp,esp
0x08048b23 <+3>: sub esp,0x8
0x08048b26 <+6>: mov eax,DWORD PTR [ebp+0x8] ; strings_not_equal(&input, 0x80497c0)
0x08048b29 <+9>: add esp,0xfffffff8
0x08048b2c <+12>: push 0x80497c0
0x08048b31 <+17>: push eax
0x08048b32 <+18>: call 0x8049030 <strings_not_equal>
0x08048b37 <+23>: add esp,0x10
0x08048b3a <+26>: test eax,eax
0x08048b3c <+28>: je 0x8048b43 <phase_1+35> ; if equal, don't explode
0x08048b3e <+30>: call 0x80494fc <explode_bomb>
0x08048b43 <+35>: mov esp,ebp ; return 0
0x08048b45 <+37>: pop ebp
0x08048b46 <+38>: ret
As the first challenge, this one is straightforward: our input is compared to a string beginning at 0x80497c0. Using GDB, we can see that this string is:
x/s 0x80497c0
(out) 0x80497c0: "Public speaking is very easy."Here's the disassembled phase_2():
0x08048b48 <+0>: push ebp ; set up stack frame
0x08048b49 <+1>: mov ebp,esp
0x08048b4b <+3>: sub esp,0x20
0x08048b4e <+6>: push esi ; store callee-saved regs
0x08048b4f <+7>: push ebx
0x08048b50 <+8>: mov edx,DWORD PTR [ebp+0x8] ; read_6n(&input, &numlist)
0x08048b53 <+11>: add esp,0xfffffff8
0x08048b56 <+14>: lea eax,[ebp-0x18]
0x08048b59 <+17>: push eax
0x08048b5a <+18>: push edx
0x08048b5b <+19>: call 0x8048fd8 <read_six_numbers>
0x08048b60 <+24>: add esp,0x10 ; if numlist[0] != 1, explode
0x08048b63 <+27>: cmp DWORD PTR [ebp-0x18],0x1
0x08048b67 <+31>: je 0x8048b6e <phase_2+38>
0x08048b69 <+33>: call 0x80494fc <explode_bomb>
0x08048b6e <+38>: mov ebx,0x1 ; start checking at numlist[1]
0x08048b73 <+43>: lea esi,[ebp-0x18]
0x08048b76 <+46>: lea eax,[ebx+0x1] ; x_n ?= x_{n-1} * n
0x08048b79 <+49>: imul eax,DWORD PTR [esi+ebx*4-0x4]
0x08048b7e <+54>: cmp DWORD PTR [esi+ebx*4],eax
0x08048b81 <+57>: je 0x8048b88 <phase_2+64> ; if equal, goto inc
0x08048b83 <+59>: call 0x80494fc <explode_bomb> ; else explode
0x08048b88 <+64>: inc ebx ;inc: increment
0x08048b89 <+65>: cmp ebx,0x5 ; end if we've checked five numbers
0x08048b8c <+68>: jle 0x8048b76 <phase_2+46>
0x08048b8e <+70>: lea esp,[ebp-0x28] ; return
0x08048b91 <+73>: pop ebx
0x08048b92 <+74>: pop esi
0x08048b93 <+75>: mov esp,ebp
0x08048b95 <+77>: pop ebp
0x08048b96 <+78>: ret
And since read_six_numbers() is called from phase_2(), here is its assembly as well:
0x08048fd8 <+0>: push ebp ; set up stack frame
0x08048fd9 <+1>: mov ebp,esp
0x08048fdb <+3>: sub esp,0x8
0x08048fde <+6>: mov ecx,DWORD PTR [ebp+0x8] ; sscanf(arg1, "%d %d %d %d %d %d", arg2[0-5])
0x08048fe1 <+9>: mov edx,DWORD PTR [ebp+0xc]
0x08048fe4 <+12>: lea eax,[edx+0x14]
0x08048fe7 <+15>: push eax
0x08048fe8 <+16>: lea eax,[edx+0x10]
0x08048feb <+19>: push eax
0x08048fec <+20>: lea eax,[edx+0xc]
0x08048fef <+23>: push eax
0x08048ff0 <+24>: lea eax,[edx+0x8]
0x08048ff3 <+27>: push eax
0x08048ff4 <+28>: lea eax,[edx+0x4]
0x08048ff7 <+31>: push eax
0x08048ff8 <+32>: push edx
0x08048ff9 <+33>: push 0x8049b1b
0x08048ffe <+38>: push ecx
0x08048fff <+39>: call 0x8048860 <sscanf@plt>
0x08049004 <+44>: add esp,0x20 ; if read failed, explode
0x08049007 <+47>: cmp eax,0x5
0x0804900a <+50>: jg 0x8049011 <read_six_numbers+57>
0x0804900c <+52>: call 0x80494fc <explode_bomb>
0x08049011 <+57>: mov esp,ebp ; return
0x08049013 <+59>: pop ebp
0x08049014 <+60>: ret
The helper function read_six_numbers() is straightfoward: given an input string and number array, it will read six integers from the string into the array. These numbers are then examined in phase_2(): if each integer is not equal to its index times the previous value, the bomb explodes. Thus, for n = 1..6, we should print n! (n factorial): 1 2 6 24 120 720.
Here's the disassembled phase_3():
0x08048b98 <+0>: push ebp ; set up stack frame
0x08048b99 <+1>: mov ebp,esp
0x08048b9b <+3>: sub esp,0x14
0x08048b9e <+6>: push ebx
0x08048b9f <+7>: mov edx,DWORD PTR [ebp+0x8] ; sscanf(&input, "%d %c %d", var1, var2, var3)
0x08048ba2 <+10>: add esp,0xfffffff4
0x08048ba5 <+13>: lea eax,[ebp-0x4]
0x08048ba8 <+16>: push eax
0x08048ba9 <+17>: lea eax,[ebp-0x5]
0x08048bac <+20>: push eax
0x08048bad <+21>: lea eax,[ebp-0xc]
0x08048bb0 <+24>: push eax
0x08048bb1 <+25>: push 0x80497de
0x08048bb6 <+30>: push edx
0x08048bb7 <+31>: call 0x8048860 <sscanf@plt>
0x08048bbc <+36>: add esp,0x20 ; if read failed, explode
0x08048bbf <+39>: cmp eax,0x2
0x08048bc2 <+42>: jg 0x8048bc9 <phase_3+49>
0x08048bc4 <+44>: call 0x80494fc <explode_bomb>
0x08048bc9 <+49>: cmp DWORD PTR [ebp-0xc],0x7 ; var1 <= 7
0x08048bcd <+53>: ja 0x8048c88 <phase_3+240>
0x08048bd3 <+59>: mov eax,DWORD PTR [ebp-0xc] ; if var1 = 0, jump to 0x8048be0
0x08048bd6 <+62>: jmp DWORD PTR [eax*4+0x80497e8]
0x08048bdd <+69>: lea esi,[esi+0x0]
0x08048be0 <+72>: mov bl,0x71 ; bl = 'q'
0x08048be2 <+74>: cmp DWORD PTR [ebp-0x4],0x309 ; var3 = 777
0x08048be9 <+81>: je 0x8048c8f <phase_3+247>
.
.
.
0x08048c88 <+240>: mov bl,0x78
0x08048c8a <+242>: call 0x80494fc <explode_bomb>
0x08048c8f <+247>: cmp bl,BYTE PTR [ebp-0x5] ; bl ?= var2
0x08048c92 <+250>: je 0x8048c99 <phase_3+257> ; if not, explode
0x08048c94 <+252>: call 0x80494fc <explode_bomb>
0x08048c99 <+257>: mov ebx,DWORD PTR [ebp-0x18] ; return
0x08048c9c <+260>: mov esp,ebp
0x08048c9e <+262>: pop ebp
0x08048c9f <+263>: ret
For this challenge, three variables are read from our input and onto the stack. Presumably, these input values must pass a series of tests without exploding the bomb. After checking that var1 = [ebp-0xc] < 0x7, we're allowed to jump to a location in the code based upon the user-supplied value [ebp-0xc], choosing from a list of pointers located at 0x80497e8. By listing these values and checking the code, we can see that several of them would work:
x/7xw 0x80497e8
(out) 0x80497e8: 0x08048be0 0x08048c00 0x08048c16 0x08048c28
(out) 0x80497f8: 0x08048c40 0x08048c52 0x08048c64It's probably easiest to choose the first pointer, by setting var1 = 0. If this is our choice, we need to set var2 = 'q' and var3 = 777 to pass the remaining tests. Thus, a solution of 0 q 777 will allow us to return from phase_3() without exploding the bomb.
Here's the disassembled code for phase_4():
0x08048ce0 <+0>: push ebp ; set up stack frame
0x08048ce1 <+1>: mov ebp,esp
0x08048ce3 <+3>: sub esp,0x18
0x08048ce6 <+6>: mov edx,DWORD PTR [ebp+0x8] ; sscanf(&input, "%d", &var1)
0x08048ce9 <+9>: add esp,0xfffffffc
0x08048cec <+12>: lea eax,[ebp-0x4]
0x08048cef <+15>: push eax
0x08048cf0 <+16>: push 0x8049808
0x08048cf5 <+21>: push edx
0x08048cf6 <+22>: call 0x8048860 <sscanf@plt>
0x08048cfb <+27>: add esp,0x10 ; if read failed, explode
0x08048cfe <+30>: cmp eax,0x1
0x08048d01 <+33>: jne 0x8048d09 <phase_4+41>
0x08048d03 <+35>: cmp DWORD PTR [ebp-0x4],0x0 ; if null, explode
0x08048d07 <+39>: jg 0x8048d0e <phase_4+46>
0x08048d09 <+41>: call 0x80494fc <explode_bomb>
0x08048d0e <+46>: add esp,0xfffffff4 ; func4(var1)
0x08048d11 <+49>: mov eax,DWORD PTR [ebp-0x4]
0x08048d14 <+52>: push eax
0x08048d15 <+53>: call 0x8048ca0 <func4>
0x08048d1a <+58>: add esp,0x10 ; explode if result != 0x37
0x08048d1d <+61>: cmp eax,0x37
0x08048d20 <+64>: je 0x8048d27 <phase_4+71>
0x08048d22 <+66>: call 0x80494fc <explode_bomb>
0x08048d27 <+71>: mov esp,ebp ; return
0x08048d29 <+73>: pop ebp
0x08048d2a <+74>: ret
In phase_4() a single integer input is read, and then passed to func4(). If the result returned from func4() is not 0x37, the bomb explodes. Let's look at func4():
0x08048ca0 <+0>: push ebp ; set up stack frame and save regs
0x08048ca1 <+1>: mov ebp,esp
0x08048ca3 <+3>: sub esp,0x10
0x08048ca6 <+6>: push esi
0x08048ca7 <+7>: push ebx
0x08048ca8 <+8>: mov ebx,DWORD PTR [ebp+0x8] ; if var1 <= 1, return 1
0x08048cab <+11>: cmp ebx,0x1
0x08048cae <+14>: jle 0x8048cd0 <func4+48>
0x08048cb0 <+16>: add esp,0xfffffff4 ; var2 = func4(var1-1)
0x08048cb3 <+19>: lea eax,[ebx-0x1]
0x08048cb6 <+22>: push eax
0x08048cb7 <+23>: call 0x8048ca0 <func4>
0x08048cbc <+28>: mov esi,eax
0x08048cbe <+30>: add esp,0xfffffff4
0x08048cc1 <+33>: lea eax,[ebx-0x2] ; var3 = func4(var1-2)
0x08048cc4 <+36>: push eax
0x08048cc5 <+37>: call 0x8048ca0 <func4>
0x08048cca <+42>: add eax,esi ; var3 = (var2 + var3)
0x08048ccc <+44>: jmp 0x8048cd5 <func4+53>
0x08048cce <+46>: mov esi,esi ; return 1
0x08048cd0 <+48>: mov eax,0x1
0x08048cd5 <+53>: lea esp,[ebp-0x18] ; return var3
0x08048cd8 <+56>: pop ebx
0x08048cd9 <+57>: pop esi
0x08048cda <+58>: mov esp,ebp
0x08048cdc <+60>: pop ebp
0x08048cdd <+61>: ret
This function is a little tricky since it's recursive, but once you realize that func4(n) = func4(n-1) + func4(n-2), it should be clear that the results of func4() will follow the Fibonacci sequence. If you're unfamiliar with the sequence, you can start from the base case n=1 and work your way up to find that the 9th Fibonacci number is 55, or 0x37, so our answer should be 9.
Here's the disassembled code for phase_5():
0x08048d2c <+0>: push ebp ; set up stack frame and store regs
0x08048d2d <+1>: mov ebp,esp
0x08048d2f <+3>: sub esp,0x10
0x08048d32 <+6>: push esi
0x08048d33 <+7>: push ebx
0x08048d34 <+8>: mov ebx,DWORD PTR [ebp+0x8] ; var1 = strlen(input)
0x08048d37 <+11>: add esp,0xfffffff4
0x08048d3a <+14>: push ebx
0x08048d3b <+15>: call 0x8049018 <string_length>
0x08048d40 <+20>: add esp,0x10 ; explode if var1 != 6
0x08048d43 <+23>: cmp eax,0x6
0x08048d46 <+26>: je 0x8048d4d <phase_5+33>
0x08048d48 <+28>: call 0x80494fc <explode_bomb>
0x08048d4d <+33>: xor edx,edx
0x08048d4f <+35>: lea ecx,[ebp-0x8]
0x08048d52 <+38>: mov esi,0x804b220 ; s = "isrveawhobpnutfg"
0x08048d57 <+43>: mov al,BYTE PTR [edx+ebx*1] ; eax = input[i] % 16
0x08048d5a <+46>: and al,0xf
0x08048d5c <+48>: movsx eax,al
0x08048d5f <+51>: mov al,BYTE PTR [eax+esi*1]
0x08048d62 <+54>: mov BYTE PTR [edx+ecx*1],al ; var2[i] = s[ input[i] % 16 ]
0x08048d65 <+57>: inc edx
0x08048d66 <+58>: cmp edx,0x5 ; for i = 0 to 5
0x08048d69 <+61>: jle 0x8048d57 <phase_5+43>
0x08048d6b <+63>: mov BYTE PTR [ebp-0x2],0x0 ; var2 ?= "giants"
0x08048d6f <+67>: add esp,0xfffffff8
0x08048d72 <+70>: push 0x804980b
0x08048d77 <+75>: lea eax,[ebp-0x8]
0x08048d7a <+78>: push eax
0x08048d7b <+79>: call 0x8049030 <strings_not_equal>
0x08048d80 <+84>: add esp,0x10 ; explode if strings_not_equal
0x08048d83 <+87>: test eax,eax
0x08048d85 <+89>: je 0x8048d8c <phase_5+96>
0x08048d87 <+91>: call 0x80494fc <explode_bomb>
0x08048d8c <+96>: lea esp,[ebp-0x18] ; return
0x08048d8f <+99>: pop ebx
0x08048d90 <+100>: pop esi
0x08048d91 <+101>: mov esp,ebp
0x08048d93 <+103>: pop ebp
0x08048d94 <+104>: ret
The disassembled phase_5() code starts off fairly standard, checking that we submit a string of length 6, and then defining the string s = "isrveawhobpnutfg". It quickly becomes more complex in lines phase_5()+43 to phase_5()+61, where it calculates var2[i] = s[ input[i] % 16 ], replacing each of our six inputted characters with the nth character in s, where n = input[i] % 16. This occurs because x % 16 is equivalent to x & 0x0f. By looking at s and the desired result, "giants", we can determine what each of our input characters should be modulo 16, namely [15, 0, 5, 11, 13, 1] (since 'g' is the last character in s, 'i' is the first, and so on...). To convert these integers to more easily printable ASCII values, I added 48 to each (maintaining equivalence mod 16) before converting to the string "?05;=1".
The disassembled code for phase_6() is considerably more complicated than previous phases, so I'll break it into four more manageable chunks:
0x08048d98 <+0>: push ebp ; set up stack frame, save regs
0x08048d99 <+1>: mov ebp,esp
0x08048d9b <+3>: sub esp,0x4c
0x08048d9e <+6>: push edi
0x08048d9f <+7>: push esi
0x08048da0 <+8>: push ebx
0x08048da1 <+9>: mov edx,DWORD PTR [ebp+0x8] ; read_6n(&input, &var1)
0x08048da4 <+12>: mov DWORD PTR [ebp-0x34],0x804b26c
0x08048dab <+19>: add esp,0xfffffff8
0x08048dae <+22>: lea eax,[ebp-0x18]
0x08048db1 <+25>: push eax
0x08048db2 <+26>: push edx
0x08048db3 <+27>: call 0x8048fd8 <read_six_numbers>
0x08048db8 <+32>: xor edi,edi ; edi = 0
0x08048dba <+34>: add esp,0x10
0x08048dbd <+37>: lea esi,[esi+0x0]
0x08048dc0 <+40>: lea eax,[ebp-0x18] ;loop1: if input[edi] > 6, explode
0x08048dc3 <+43>: mov eax,DWORD PTR [eax+edi*4]
0x08048dc6 <+46>: dec eax
0x08048dc7 <+47>: cmp eax,0x5
0x08048dca <+50>: jbe 0x8048dd1 <phase_6+57>
0x08048dcc <+52>: call 0x80494fc <explode_bomb>
0x08048dd1 <+57>: lea ebx,[edi+0x1] ; ebx = edi + 1
0x08048dd4 <+60>: cmp ebx,0x5 ; if edi >= 5, goto jump1
0x08048dd7 <+63>: jg 0x8048dfc <phase_6+100>
0x08048dd9 <+65>: lea eax,[edi*4+0x0]
0x08048de0 <+72>: mov DWORD PTR [ebp-0x38],eax
0x08048de3 <+75>: lea esi,[ebp-0x18]
0x08048de6 <+78>: mov edx,DWORD PTR [ebp-0x38] ;loop2: explode if input[edi] == input[ebx]
0x08048de9 <+81>: mov eax,DWORD PTR [edx+esi*1]
0x08048dec <+84>: cmp eax,DWORD PTR [esi+ebx*4]
0x08048def <+87>: jne 0x8048df6 <phase_6+94>
0x08048df1 <+89>: call 0x80494fc <explode_bomb>
0x08048df6 <+94>: inc ebx ; goto loop2 while ++ebx <= 5
0x08048df7 <+95>: cmp ebx,0x5
0x08048dfa <+98>: jle 0x8048de6 <phase_6+78>
0x08048dfc <+100>: inc edi ;jump1: goto loop1 while ++ edi <= 5
0x08048dfd <+101>: cmp edi,0x5
0x08048e00 <+104>: jle 0x8048dc0 <phase_6+40>
First, six numbers are read into memory. After that is our first doubly-nested for loop. From lines phase_6()+94 to +104, it's clear that edi is used as a counter for the outer loop (loop1), and ebx is used as a counter for the inner loop (loop2). edi is initialized on line +32 to zero, and is incremented until it reaches five. Each time it's incremented, lines +40 to +52 check that the unsigned value at that index is less than seven. If not, the bomb explodes. For each iteration of the inner loop, ebx is initialized to ebx+1, and lines +65 to +89 ensure that all remaining numbers are unique. In summary, this section of the code checks that the user has inputted the integers 1 through 6, in some order.
Before proceeding, it's useful to gain an understanding of what the remainder of the code does. It took me a while to figure out, but the final section of phase_6() is the easiest to decipher:
0x08048e60 <+200>: mov DWORD PTR [esi+0x8],0x0 ; *(esi+8) = 0 / NULL
0x08048e67 <+207>: mov esi,DWORD PTR [ebp-0x34] ; esi = head
0x08048e6a <+210>: xor edi,edi ; edi = 0
0x08048e6c <+212>: lea esi,[esi+eiz*1+0x0] ; nop
0x08048e70 <+216>: mov edx,DWORD PTR [esi+0x8] ; if *esi < **(esi+8), explode
0x08048e73 <+219>: mov eax,DWORD PTR [esi]
0x08048e75 <+221>: cmp eax,DWORD PTR [edx]
0x08048e77 <+223>: jge 0x8048e7e <phase_6+230>
0x08048e79 <+225>: call 0x80494fc <explode_bomb>
0x08048e7e <+230>: mov esi,DWORD PTR [esi+0x8] ; while ++edi <= 4, esi = *(esi+8), perform check again
0x08048e81 <+233>: inc edi
0x08048e82 <+234>: cmp edi,0x4
0x08048e85 <+237>: jle 0x8048e70 <phase_6+216>
0x08048e87 <+239>: lea esp,[ebp-0x58] ; return
0x08048e8a <+242>: pop ebx
0x08048e8b <+243>: pop esi
0x08048e8c <+244>: pop edi
0x08048e8d <+245>: mov esp,ebp
0x08048e8f <+247>: pop ebp
0x08048e90 <+248>: ret
Line +230 clued me in that phase_6() uses a linked list, since repeatedly derefencing pointers in this manner is indicative of following a chain of next pointers. After some investigation, I determined that the node structure used is as follows:
struct node {
int value;
int node_id;
struct node * next;
}
Armed with this information, we can see that lines +216 through +237 iterate over the linked list, checking that the value of each node exceeds the value of the following node. In other words, we must reach line +200 with our linked list in reverse sorted order.
The next section we'll look at is from +106 to +170. Before doing so, let's get a sense of which local variables are stored on the stack and how. Since the only remaining call to explode_bomb() is on line +225, it's safe to set a breakpoint at +172 and continue to there.
break *0x8048e44
(out) Breakpoint 3 at 0x8048e44
continue
(out) Continuing.
x/15xw $ebp-0x3c
(out) 0xffffd2cc: 0xffffd2d8 0x00000010 0x0804b26c 0x0804b260
(out) 0xffffd2dc: 0x0804b23c 0x0804b248 0x0804b254 0x0804b230
(out) 0xffffd2ec: 0x0804b26c 0x00000002 0x00000005 0x00000004
(out) 0xffffd2fc: 0x00000003 0x00000006 0x00000001
x/3xw 0x804b260
(out) 0x804b260 <node2>: 0x000002d5 0x00000002 0x0804b254
x/3xw 0x804b23c
(out) 0x804b23c <node5>: 0x000000d4 0x00000005 0x0804b230
x/3xw 0x804b248
(out) 0x804b248 <node4>: 0x000003e5 0x00000004 0x0804b23c
x/3xw 0x804b254
(out) 0x804b254 <node3>: 0x0000012d 0x00000003 0x0804b248
x/3xw 0x804b230
(out) 0x804b230 <node6>: 0x000001b0 0x00000006 0x00000000
x/3xw 0x804b26c
(out) 0x804b26c <node1>: 0x000000fd 0x00000001 0x0804b260From this, we can see that these lines will create an array with pointers to each of the six nodes. These nodes are ordered by the input sequence provided, in my case 2 5 4 3 6 1. Let's take a look at the code to verify:
0x08048e02 <+106>: xor edi,edi ; edi = 0
0x08048e04 <+108>: lea ecx,[ebp-0x18] ; ecx = \&input
0x08048e07 <+111>: lea eax,[ebp-0x30]
0x08048e0a <+114>: mov DWORD PTR [ebp-0x3c],eax
0x08048e0d <+117>: lea esi,[esi+0x0] ; nop
0x08048e10 <+120>: mov esi,DWORD PTR [ebp-0x34] ;loop1: esi = head, ebx = 1
0x08048e13 <+123>: mov ebx,0x1 ; goto jump1 if input[edi] < 1
0x08048e18 <+128>: lea eax,[edi*4+0x0]
0x08048e1f <+135>: mov edx,eax
0x08048e21 <+137>: cmp ebx,DWORD PTR [eax+ecx*1]
0x08048e24 <+140>: jge 0x8048e38 <phase_6+160>
0x08048e26 <+142>: mov eax,DWORD PTR [edx+ecx*1] ; eax = input[edi]
0x08048e29 <+145>: lea esi,[esi+eiz*1+0x0] ; nop
0x08048e30 <+152>: mov esi,DWORD PTR [esi+0x8] ;loop2: while ebx++ < input[edi] : esi = *(esi+8)
0x08048e33 <+155>: inc ebx ; follow linked list to input[edi]th element
0x08048e34 <+156>: cmp ebx,eax
0x08048e36 <+158>: jl 0x8048e30 <phase_6+152>
0x08048e38 <+160>: mov edx,DWORD PTR [ebp-0x3c] ;jump1: node_list[edi] = esi
0x08048e3b <+163>: mov DWORD PTR [edx+edi*4],esi ; goto loop1 if ++edi <= 5
0x08048e3e <+166>: inc edi
0x08048e3f <+167>: cmp edi,0x5
0x08048e42 <+170>: jle 0x8048e10 <phase_6+120>
Again, we have a doubly-nested for loop. ebx is used to index the inner loop (which follows the linked list to our designated node, input[edi]), edi iterates over each of the six integers supplied, and esi stores a pointer to the current node. As expected, for each integer provided, the corresponding node is found and a pointer to it (esi) is written in an array starting at ebp-0x30. Memory location ebp-0x34 stores a pointer to the head of the linked list.
Now let's take a look at the only remaining section of code:
0x08048e44 <+172>: mov esi,DWORD PTR [ebp-0x30] ; head = node_list[0]
0x08048e47 <+175>: mov DWORD PTR [ebp-0x34],esi
0x08048e4a <+178>: mov edi,0x1 ; edi = 1
0x08048e4f <+183>: lea edx,[ebp-0x30] ; edx = \&node_list
0x08048e52 <+186>: mov eax,DWORD PTR [edx+edi*4] ; while edi++ <= 5: esi = *(esi+8) = node_list[edi]
0x08048e55 <+189>: mov DWORD PTR [esi+0x8],eax
0x08048e58 <+192>: mov esi,eax
0x08048e5a <+194>: inc edi
0x08048e5b <+195>: cmp edi,0x5
0x08048e5e <+198>: jle 0x8048e52 <phase_6+186>
This code iterates over each node in the list, overwriting the next pointers in the linked list and node list so that nodes will be visited in the order specified by our input. Let's use GEF again to look at the modified list:
break *0x8048e60
(out) Breakpoint 3 at 0x8048e60
continue
(out) Continuing.
x/15xw $ebp-0x3c
(out) 0xffffd2cc: 0xffffd2d8 0x00000010 0x0804b260 0x0804b260
(out) 0xffffd2dc: 0x0804b23c 0x0804b248 0x0804b254 0x0804b230
(out) 0xffffd2ec: 0x0804b26c 0x00000002 0x00000005 0x00000004
(out) 0xffffd2fc: 0x00000003 0x00000006 0x00000001
x/3xw 0x804b260
(out) 0x804b260 <node2>: 0x000002d5 0x00000002 0x0804b23c
x/3xw 0x804b23c
(out) 0x804b23c <node5>: 0x000000d4 0x00000005 0x0804b248
x/3xw 0x804b248
(out) 0x804b248 <node4>: 0x000003e5 0x00000004 0x0804b254
x/3xw 0x804b254
(out) 0x804b254 <node3>: 0x0000012d 0x00000003 0x0804b230
x/3xw 0x804b230
(out) 0x804b230 <node6>: 0x000001b0 0x00000006 0x0804b26c
x/3xw 0x804b26c
(out) 0x804b26c <node1>: 0x000000fd 0x00000001 0x0804b260In order to visit these nodes in descending order, we need to visit them in the order 4 2 6 3 1 5.
As we saw in the Overview, the function phase_defused() calls sscanf(..., "%d %s", n, s) after passing each phase, and will enter secret_phase() if s = "austinpowers". Since Level 4 is the only phase which requires a single integer as input, this is the phase where we should tack on "austinpowers" so that we can enter the secret level, making our solution 9 austinpowers.
Now that we can enter secret_phase(), here's the disassembly:
0x08048ee8 <+0>: push ebp ; set up stack
0x08048ee9 <+1>: mov ebp,esp
0x08048eeb <+3>: sub esp,0x14
0x08048eee <+6>: push ebx ; read_line(input)
0x08048eef <+7>: call 0x80491fc <read_line>
0x08048ef4 <+12>: push 0x0 ; strol(input, 0, 10)
0x08048ef6 <+14>: push 0xa
0x08048ef8 <+16>: push 0x0
0x08048efa <+18>: push eax
0x08048efb <+19>: call 0x80487f0 <__strtol_internal@plt>
0x08048f00 <+24>: add esp,0x10 ; explode if strol() > 1001
0x08048f03 <+27>: mov ebx,eax
0x08048f05 <+29>: lea eax,[ebx-0x1]
0x08048f08 <+32>: cmp eax,0x3e8
0x08048f0d <+37>: jbe 0x8048f14 <secret_phase+44>
0x08048f0f <+39>: call 0x80494fc <explode_bomb>
0x08048f14 <+44>: add esp,0xfffffff8 ; fun7(0x804b320, input)
0x08048f17 <+47>: push ebx
0x08048f18 <+48>: push 0x804b320
0x08048f1d <+53>: call 0x8048e94 <fun7>
0x08048f22 <+58>: add esp,0x10 ; explode if fun7() != 7
0x08048f25 <+61>: cmp eax,0x7
0x08048f28 <+64>: je 0x8048f2f <secret_phase+71>
0x08048f2a <+66>: call 0x80494fc <explode_bomb>
0x08048f2f <+71>: add esp,0xfffffff4 ; success!
0x08048f32 <+74>: push 0x8049820
0x08048f37 <+79>: call 0x8048810 <printf@plt>
0x08048f3c <+84>: call 0x804952c <phase_defused>
0x08048f41 <+89>: mov ebx,DWORD PTR [ebp-0x18]
0x08048f44 <+92>: mov esp,ebp
0x08048f46 <+94>: pop ebp
0x08048f47 <+95>: ret
After the first six phases run, read_line() is called again, and our input is converted to an integer. This integer must be less than 1002, and if fun7(addr, input) != 7 the bomb explodes. Here's fun7() disassembled:
0x08048e94 <+0>: push ebp ; set up stack
0x08048e95 <+1>: mov ebp,esp
0x08048e97 <+3>: sub esp,0x8
0x08048e9a <+6>: mov edx,DWORD PTR [ebp+0x8] ; edx = addr
0x08048e9d <+9>: mov eax,DWORD PTR [ebp+0xc] ; eax = num
0x08048ea0 <+12>: test edx,edx ; if addr == NULL, return -1
0x08048ea2 <+14>: jne 0x8048eb0 <fun7+28>
0x08048ea4 <+16>: mov eax,0xffffffff
0x08048ea9 <+21>: jmp 0x8048ee2 <fun7+78>
0x08048eb0 <+28>: cmp eax,DWORD PTR [edx] ; if num >= *addr, goto odd
0x08048eb2 <+30>: jge 0x8048ec5 <fun7+49>
0x08048eb4 <+32>: add esp,0xfffffff8 ; return fun7(*(addr+4), num)*2
0x08048eb7 <+35>: push eax
0x08048eb8 <+36>: mov eax,DWORD PTR [edx+0x4]
0x08048ebb <+39>: push eax
0x08048ebc <+40>: call 0x8048e94 <fun7>
0x08048ec1 <+45>: add eax,eax
0x08048ec3 <+47>: jmp 0x8048ee2 <fun7+78>
0x08048ec5 <+49>: cmp eax,DWORD PTR [edx] ;odd: if *addr == num, return 0
0x08048ec7 <+51>: je 0x8048ee0 <fun7+76>
0x08048ec9 <+53>: add esp,0xfffffff8 ; return fun7(*(addr+8), num)*2 + 1
0x08048ecc <+56>: push eax
0x08048ecd <+57>: mov eax,DWORD PTR [edx+0x8]
0x08048ed0 <+60>: push eax
0x08048ed1 <+61>: call 0x8048e94 <fun7>
0x08048ed6 <+66>: add eax,eax
0x08048ed8 <+68>: inc eax
0x08048ed9 <+69>: jmp 0x8048ee2 <fun7+78>
0x08048ee0 <+76>: xor eax,eax ; return 0
0x08048ee2 <+78>: mov esp,ebp ; return
0x08048ee4 <+80>: pop ebp
0x08048ee5 <+81>: ret
For clarity, I have deleted all nop instructions (and the equivalent lea esi, [esi+eiz*1+0x0], used for larger alignments).
First, if addr is a NULL pointer, -1 is returned. If num < *addr, then fun7(*(addr+4), num) * 2 is returned. If num > *addr, then fun7(*(addr+8), num) * 2 + 1 is returned. If num == *addr, 0 is returned. As explained earlier, we want fun7(0x0804b320, input) to return 7. Let's examine the chain of pointers from 0x0804b320 to get a better understanding of what will happen when func7() is called:
x/3w 0x0804b320
(out) 0x804b320 <n1>: 0x00000024 0x0804b314 0x0804b308
x/3w 0x0804b314
(out) 0x804b314 <n21>: 0x00000008 0x0804b2e4 0x0804b2fc
x/3w 0x0804b2e4
(out) 0x804b2e4 <n31>: 0x00000006 0x0804b2c0 0x0804b29c
x/3w 0x0804b2c0
(out) 0x804b2c0 <n41>: 0x00000001 0x00000000 0x00000000
x/3w 0x0804b29c
(out) 0x804b29c <n42>: 0x00000007 0x00000000 0x00000000
x/3w 0x0804b2fc
(out) 0x804b2fc <n32>: 0x00000016 0x0804b290 0x0804b2a8
x/3w 0x0804b290
(out) 0x804b290 <n43>: 0x00000014 0x00000000 0x00000000
x/3w 0x0804b2a8
(out) 0x804b2a8 <n44>: 0x00000023 0x00000000 0x00000000
x/3w 0x0804b308
(out) 0x804b308 <n22>: 0x00000032 0x0804b2f0 0x0804b2d8
x/3w 0x0804b2f0
(out) 0x804b2f0 <n33>: 0x0000002d 0x0804b2cc 0x0804b284
x/3w 0x0804b2cc
(out) 0x804b2cc <n45>: 0x00000028 0x00000000 0x00000000
x/3w 0x0804b284
(out) 0x804b284 <n46>: 0x0000002f 0x00000000 0x00000000
x/3w 0x0804b2d8
(out) 0x804b2d8 <n34>: 0x0000006b 0x0804b2b4 0x0804b278
x/3w 0x0804b2b4
(out) 0x804b2b4 <n47>: 0x00000063 0x00000000 0x00000000
x/3w 0x0804b278
(out) 0x804b278 <n48>: 0x000003e9 0x00000000 0x00000000It might not be clear immediately, but these pointers are building a binary tree which looks like this:
In order to return 7 from the uppermost fun7(), our input must be equal to an element of the tree, so that we initially return 0 and not -1. To reach 7, we should return 2*n+1 thrice successively (0 -> 1 -> 3 -> 7), meaning we should take the second branch each time, and the input we want is the rightmost leaf of the tree. This is 0x3e9 == 1001, which passes the initial checks.