UTCTF 2021 Reversing Recur Write up

Recur 

실행해보면

이상 진행되지 않는다. ghidra 분석시작

 

int main(void)

{
  ulong val;
  int i;
  char ch;
  
  i = 0;
  while (i < 0x1c) {
    ch = flag[i];
    val = recurrence(i * i);
    putchar((int)(char)((byte)val ^ ch));
    fflush(stdout);
    i = i + 1;
  }
  return 0;
}

ulong recurrence(int param_1)

{
  ulong a;
  ulong b;
  
  if (param_1 == 0) {
    a = 3;
  }
  else {
    if (param_1 == 1) {
      a = 5;
    }
    else {
      a = recurrence(param_1 + -1);
      b = recurrence(param_1 + -2);
      a = (ulong)(uint)((int)b * 3 + (int)a * 2);
    }
  }
  return a;
}

두 함수 발견. recurrence 안에 재귀함수로 시간이 오래걸리는 것으로 예정

recurrence(0) = 3
recurrence(1) = 5
recurrence(n) = 2 * recurrence(n-1) + 3 * recurrence(n-2)

함수 확인 후 이는 반복문으로 변경 가능.

플래그 변수 값 확인. 크기 28개의 배열

    ch = flag[i];
    val = recurrence(i * i);
    putchar((int)(char)((byte)val ^ ch));

flag[i] ^ recurrence(i * i) 로 복구가능. 

 

Solution

def recur(a):
    arr = [3, 5]
    for t in range(a):
        arr.append(2*arr[-1]+3*arr[-2])
    return arr[a]

flag = [0x76, 0x71, 0xc5, 0xa9, 0xe2, 0x22, 0xd8, 0xb5, 0x73, 0xf1, 0x92, 0x28, 0xb2, 0xbf,\
     0x90, 0x5a, 0x76, 0x77, 0xfc, 0xa6, 0xb3, 0x21, 0x90, 0xda, 0x6f, 0xb5, 0xcf, 0x38]

for i in range(0, len(flag)):
    print(chr(recur(i*i) & 0xFF ^ flag[i]), end="")

utflag{0pt1m1z3_ur_c0d3_l0l}