Of Binary Bombs (part 4)

Part 3 of this series explored phase_3 of this riddle which marked the first phase that accepted more than a single correct input sequence. Here I'll continue with the next phase: sym.phase_4.

At first, some arguments are loaded onto the stack to prep for a call to sscanf but rather than an immediate string as the format string argument, an address is provided. Recall in in phase_2 that we could get a hint of the input by printing str._d_d_d_d_d_d (ps @ str._d_d_d_d_d_d) - here we need to understand the arguments to sscanf a little to know that the address 0x8049808 should contain a format string. Indeed, it does (ps @ 0x8049808 yields %d) - our input string needs to be a number. That number needs to be larger than 0.

    cmp dword [ebp-0x4], 0x0
    jg 0x8048d0e

After the input is checked, its value is pushed to the stack and control is passed to sym.func4.

The second requirement of our input is now revealed:

    cmp ebx, 0x1
    jle 0x8048cd0

For values larger than 1 sym.func4 is called recursively.

    lea eax, [ebx-0x1]
    push eax
    call sym.func4

So the input value to sym.func4 (our input, initially) is decremented by 1 and passed to the recursive call. The result of that call is saved to esi and then sym.func4 is called recursively yet again - this time after decrementing the input by 2.

    lea eax, [ebx-0x2]
    push eax
    call sym.func4

The return value of the second recursion is added to the result of the first and that sum becomes the return value of this depth of the recursive call. In C, this looks something like:

int func4 (int n) {
    if (n < 2) { return 1; }
    return func4 (n - 1) + func4 (n - 2);
}

Back in sym.phase_4 there is the following check:

    cmp eax, 0x37

The input, when fed to sym.func4, should return 55. The recursion of n-1 + n-2 is one way to calculate the Fibonacci number at index n. That, coupled with the fact that 55 is a Fibonacci number, allows us to derive the necessary input value of 9.

Next up, part 5.