Binary Bomb - Phase 4
I Am Having a Very Difficult Time Tracing the Assembly Code for the Following Binary Bomb (An Assignment from School Where a Bomb Has to Be Defused, This Bomb...
I am having a very difficult time tracing the assembly code for the following binary bomb (An assignment from school where a bomb has to be defused, this bomb contains 6 phases which all have 1 correct input to proceed to the next phase). I am currently on phase_4 and it has a recursive function called func4. I have identified that the input is "%d %d" which is two integers. However, I cannot quite figure out what func4 is doing, even after getting the info on all registers throughout every step.
Phase_4:
(gdb) disas
Dump of assembler code for function phase_4:
=> 0x08048e24 <+0>: sub $0x2c,%esp
0x08048e27 <+3>: lea 0x1c(%esp),%eax
0x08048e2b <+7>: mov %eax,0xc(%esp)
0x08048e2f <+11>: lea 0x18(%esp),%eax
0x08048e33 <+15>: mov %eax,0x8(%esp)
0x08048e37 <+19>: movl $0x804a7f1,0x4(%esp)
0x08048e3f <+27>: mov 0x30(%esp),%eax
0x08048e43 <+31>: mov %eax,(%esp)
0x08048e46 <+34>: call 0x80488d0 <__isoc99_sscanf@plt>
0x08048e4b <+39>: cmp $0x2,%eax
0x08048e4e <+42>: jne 0x8048e5d <phase_4+57>
0x08048e50 <+44>: mov 0x18(%esp),%eax
0x08048e54 <+48>: test %eax,%eax
0x08048e56 <+50>: js 0x8048e5d <phase_4+57>
0x08048e58 <+52>: cmp $0xe,%eax
0x08048e5b <+55>: jle 0x8048e62 <phase_4+62>
0x08048e5d <+57>: call 0x8049470 <explode_bomb>
0x08048e62 <+62>: movl $0xe,0x8(%esp)
0x08048e6a <+70>: movl $0x0,0x4(%esp)
0x08048e72 <+78>: mov 0x18(%esp),%eax
0x08048e76 <+82>: mov %eax,(%esp)
0x08048e79 <+85>: call 0x8048dbb <func4>
0x08048e7e <+90>: cmp $0x25,%eax
0x08048e81 <+93>: jne 0x8048e8a <phase_4+102>
0x08048e83 <+95>: cmpl $0x25,0x1c(%esp)
0x08048e88 <+100>: je 0x8048e8f <phase_4+107>
0x08048e8a <+102>: call 0x8049470 <explode_bomb>
0x08048e8f <+107>: add $0x2c,%esp
0x08048e92 <+110>: ret
End of assembler dump.
func4:
Breakpoint 2, 0x08048dbb in func4 ()
(gdb) disas
Dump of assembler code for function func4:
=> 0x08048dbb <+0>: sub $0x1c,%esp
0x08048dbe <+3>: mov %ebx,0x14(%esp)
0x08048dc2 <+7>: mov %esi,0x18(%esp)
0x08048dc6 <+11>: mov 0x20(%esp),%eax
0x08048dca <+15>: mov 0x24(%esp),%edx
0x08048dce <+19>: mov 0x28(%esp),%esi
0x08048dd2 <+23>: mov %esi,%ecx
0x08048dd4 <+25>: sub %edx,%ecx
0x08048dd6 <+27>: mov %ecx,%ebx
0x08048dd8 <+29>: shr $0x1f,%ebx
0x08048ddb <+32>: add %ebx,%ecx
0x08048ddd <+34>: sar %ecx
0x08048ddf <+36>: lea (%ecx,%edx,1),%ebx
0x08048de2 <+39>: cmp %eax,%ebx
0x08048de4 <+41>: jle 0x8048dfd <func4+66>
0x08048de6 <+43>: lea -0x1(%ebx),%ecx
0x08048de9 <+46>: mov %ecx,0x8(%esp)
0x08048ded <+50>: mov %edx,0x4(%esp)
0x08048df1 <+54>: mov %eax,(%esp)
0x08048df4 <+57>: call 0x8048dbb <func4>
0x08048df9 <+62>: add %eax,%ebx
0x08048dfb <+64>: jmp 0x8048e16 <func4+91>
0x08048dfd <+66>: cmp %eax,%ebx
0x08048dff <+68>: jge 0x8048e16 <func4+91>
0x08048e01 <+70>: mov %esi,0x8(%esp)
0x08048e05 <+74>: lea 0x1(%ebx),%edx
0x08048e08 <+77>: mov %edx,0x4(%esp)
0x08048e0c <+81>: mov %eax,(%esp)
0x08048e0f <+84>: call 0x8048dbb <func4>
0x08048e14 <+89>: add %eax,%ebx
0x08048e16 <+91>: mov %ebx,%eax
0x08048e18 <+93>: mov 0x14(%esp),%ebx
0x08048e1c <+97>: mov 0x18(%esp),%esi
0x08048e20 <+101>: add $0x1c,%esp
0x08048e23 <+104>: ret
End of assembler dump.
1 Answer
I hope it's obvious that phase4 is checking that the first number is in the range 0..14 inclusive (see lines +44..+57)
Then it invokes func4 with three arguments: the first number entered, 0 and 14 (lines +62..+85). Next it checks that the return value is 0x25 (37 decimal) on line +90 and that the second number entered is also 37 (line +95)
Let's move on to func4. I'll call the three arguments x, low and high. Initially you don't know what they are of course. Lines +23..+34 calculate (high - low) / 2. The ugly mess is because the compiler generates code to handle negative numbers with truncation to zero. We won't see any negative numbers though. Line +36 is just a fancy addition, so in ebx we now have low + (high - low) / 2 which is also known as the average of the two numbers. The code then compares this average to the number x that has been provided as first argument. Lines +43..+62 get executed if x < average and they invoke func4(x, low, average - 1) and add the returned value to the average. Similarly, lines +70..+89 get executed if x > average and calculate average + func4(x, average + 1, high). If x == average then just the average itself is returned.
It's basically doing a binary search and summing up the guesses as it goes. Given that the interval has 15 elements, it will need at most 4 guesses. The first guess is going to be 7, so to get the required result of 37 we need 30 more. We have at most 3 more tries and all the guesses will be either less than 7 or more than 7. Since 7 * 3 = 21 and that can't give us 30 it means the number has to be greater than 7. Second guess is thus going to be (8 + 14) / 2 = 11, making our sum 18 with 19 more to go. If the number was above 11 that would mean we overshoot the target, so the number must be more than 7 and less than 11. Third guess is thus (8 + 10) / 2 = 9 which brings the sum to 27 with 10 more to go and just a single guess, so that means the number is 10.
TL;DR: the correct input should be 10 and 37
David Miller brings 15 years of experience in global economics, personal finance strategy, and market dynamics. He specializes in turning complex economic trends into actionable insights for everyday readers.
