Vedran Budimcic

RSS

Binary Bomb - Phase 4

Don’t know what is going on? Start at the intro

This time before bothering to attempt any first guesses, lets just look at the phase_4 function to gain some intuition about how it works. Notice once again there is a call to sscanf, so let’s peek at the format string to see what kind of input this phase expects.

Notice that in the second highlighted segment our input value gets passed into the function func4, and the result of this function is compared against 0x37 (55 in decimal).

Now let’s look at func4 in chunks in order to understand it easier. First looking at the section A, if the input value (located at [%ebp + 0x8] and then copied into %ebx) is less than or equal to 1, then the function jumps down to section B and sets %eax to 1, which will become the function’s return value.

Otherwise the function steps into section C will call itself, passing in the original input decremented by one. This is followed by another call to func4, passing in the original input decremented by two. Then the result of these two function calls is summed and copied into %eax to become the return value of the function.

This process should sound very familiar to you! What is a famous function formed in this way, where F(x) = F(x-1) + F(x-2)? The Fibonacci sequence of course!

One thing to note is that the results of func4 is not exactly the same as the Fibonnaci number of the input. Notice that func4 will return 1 if the input is 1 or less. Therefore if we have an input of x = 2, it will return 1 for both the x - 1= 1 and x - 2 = 0 calls.

Remember that the phase_4 function succeeds if the output of func4 was 0x37 (55 in decimal). Since the Fibonacci number for 10 = 55, and we know that func4(0) = func(1) = 1, func4(2) = 2, whereas Fib(0) = 0, Fib(1) = 1, Fib(2) = 1 then we know that we just need to find an input x such that FIb(x + 1) = 55. Since Fib(10) = Fib(9 + 1) = 55, we know that the solution for this phase is 9.

Onto phase 5!