be-quick-or-be-dead-3

Problem files

be-quick-or-be-dead-3

Solve script

solve.py

Points

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}