picoCTF 2018 be-quick-or-be-dead-3 Reversing

be-quick-or-be-dead-3 - Points: 350 - (Solves: 260)

요약

재귀적 함수 호출이 엄청 많이 일어나는 calc() 연산을

반복적 함수 호출로 코드를 바꿔서 연산하면

시간복잡도가 선형 시간을 갖게되어 연산에 걸리는 시간을 확연히 줄일 수가 있습니다.

재귀함수 호출 대신 연산 결과값을 바이너리 패치를 통해 넣어주고

해당 바이너리를 실행시켜주면 플래그가 나오게 됩니다.

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_1_036263621db6b07c874d55f1e0bba59d.

Writeup

# ./be-quick-or-be-dead-3
Be Quick Or Be Dead 3
=====================

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

위는 be-quick-or-be-dead-3 를 실행시켜본 모습입니다.

void get_key()
{
  puts("Calculating key...");
  key = calculate_key();
  puts("Done calculating key");
}

get_key() 함수의 3번째 줄의 문자열은 출력됬지만

5번째 줄의 문자열이 출력되지 않은 것으로 보아

calcuate_key() 함수를 수행 중에 SIGALRM 이 발생한 것으로 보인다.

int calc(int a1)
{
  if ( a1 > 4 )
  {
    return calc(a1 - 3) - calc(a1 - 4) + calc(a1 - 1) - calc(a1 - 2) + 0x1234 * calc(a1 - 5);
  }
  else
  {
    return a1 * a1 + 0x2345;
  }
}

int calculate_key()
{
  return calc(100021);
}

calculate_key() 함수는 calc() 함수를 호출하고 있었고

calc() 함수는 재귀함수였다.

calc(6) = calc(6 - 3) - calc(6 - 4) + calc(6 - 1) - calc(6 - 2) + 0x1234 * calc(6 - 5)
        = calc(3) - calc(2) + calc(5) - calc(4) + 0x1234 * calc(1)
        = calc(3) - calc(2) + (calc(5 - 3) - calc(5 - 4) + calc(5 - 1) - calc(5 - 2) + 0x1234 * calc(5 - 5)) - calc(4) + 0x1234 * calc(1)
        = calc(3) - calc(2) + calc(2) - calc(1) + calc(4) - calc(3) + 0x1234 * calc(0) - calc(4) + 0x1234 * calc(1)
        = calc(3) - calc(2) + calc(2) - calc(1) + calc(4) - calc(3) + 0x1234 * calc(0) - calc(4) + 0x1234 * calc(1)

재귀함수는 함수호출이 많이 발생한다는 단점이 있습니다.

calc(0) ~ calc(4) 는 재귀적으로 1번찍 호출이 일어나고

calc(5) 은 6번

calc(6) 은 11번

calc(7) 은 21번

calc(8) 은 41번

calc(9) 은 81번

calc(10) 은 161번

calc(11) 은 316번 호출된다.

(시간복잡도가 비선형)

be-quick-or-be-dead-3 은 calc(100021) 을 연산할 때

분명 엄청 많은 호출이 일어날 것이다.

해결 방법은 간단하다.

재귀(recursive)를 반복(iterative)으로 바꿔서 연산해보면 된다.

예를 들어서 calc(6) 을 호출하기 위해서

calc(0) = 0x2345
calc(1) = 0x2346
calc(2) = 0x2349
calc(3) = 0x234e
calc(4) = 0x2355
calc(5) = calc(2) - calc(1) + calc(4) - calc(3) + 0x1234 * calc(0)
        = 0x2349 - 0x2346 + 0x2355 - 0x234e + 0x1234 * 0x2345
        = 0x282040e
calc(6) = calc(3) - calc(2) + calc(5) - calc(4) + 0x1234 * calc(1)
        = 0x234e - 0x2349 + 0x282040e - 0x2355 + 0x1234 * 0x2346
        = 0x503f6f6

calc(6) 계산에 호출 7번이면 된다.

calc(7) 은 호출 8번

calc(8) 은 9번

calc(9) 은 10번

calc(10) 은 11번

calc(11) 은 12번

시간복잡도가 선형(Linear)으로 바뀌었다.

import ctypes

def calc(a1):
  if ( a1 > 4 ):
    return d[a1 - 3] - d[a1 - 4] + d[a1 - 1] - d[a1 - 2] + 4660 * d[a1 - 5];
  else:
    return a1 * a1 + 9029;

d = {} # directory
for i in range(100022): # calc(100021)
    d[i] = ctypes.c_uint(calc(i)).value # save
print(hex(d[i])) # print result
# key = 0x221d8eea

이제 바이너리 패치를 통해 문제를 풀면 됩니다.

calc() 함수를 호출하는 부분을

계산하여 나온 0x221d8eea 로 패치해줍니다.

void get_key()
{
  puts("Calculating key...");
  key = 0x221D8EEA;
  puts("Done calculating key");
}

패치한 바이너리를 실행해주면 키값이 나오게 됩니다.

# ./be-quick-or-be-dead-3
Be Quick Or Be Dead 3
=====================

Calculating key...
Done calculating key
Printing flag:
picoCTF{dynamic_pr0gramming_ftw_a0b0b7f8}