## 2018/10/12

Categories: reverse-engineering

solve.py

350

## Description

As the song draws closer to the end, another executable be-quick-or-be-dead-3 suddenly pops up. This one requires even faster machines. Can you run it fast enough too? You can also find the executable in /problems/be-quick-or-be-dead-3_2_fc35b1f6832df902b8e2f724772d012f.

## Hints

How do you speed up a very repetitive computation?

## How2solve

We are given a binary. Running produces the following output.

``````\$ ./be-quick-or-be-dead-3
Be Quick Or Be Dead 3
=====================

Calculating key...
You need a faster machine. Bye bye.
``````

Decompiling the code shows a recursive function.

``````__int64 __fastcall calc(unsigned int n)
{
int v1; // ebx
int v2; // ebx
int v3; // er12
int v4; // ebx
unsigned int result; // [rsp+1Ch] [rbp-14h]

if ( n > 4 )
{
v1 = calc(n - 1);
v2 = v1 - (unsigned __int64)calc(n - 2);
v3 = calc(n - 3);
v4 = v3 - (unsigned __int64)calc(n - 4) + v2;
result = v4 + 4660 * (unsigned __int64)calc(n - 5);
}
else
{
result = n * n + 9029;
}
return result;
}

__int64 calculate_key()
{
return calc(0x19965u);
}
``````

This algorithm can be rewritten in python and optimized with bottom-up dynamic programming.

``````import ctypes
inp = 0x19965
memo = {}
def calc(n):
if n in memo:
return memo[n]
if n > 4:
result = calc(n - 3) - calc(n - 4) + (calc(n - 1) - calc(n - 2)) + 4660 * calc(n - 5)
else:
result = n ** 2 + 9029
memo[n] = result
return result
for i in range(inp):
calc(i)
print(ctypes.c_uint32(calc(inp)).value)
``````

The `ctypes` module is used here to cast the result so it fits in a 32 bit integer.

## Running the script

The script took 2.68 seconds to run on my machine and prints `2653079950`. We can then use the trick in be-quick-or-be-dead-2 to make gdb jump over the calculation and setting `rax` equal to `2653079950`.

## Flag

``````picoCTF{dynamic_pr0gramming_ftw_b5c45645}
``````