[SECCON Beginners CTF 2022] Recursive

このファイルは中でどんな処理をしているんだろう? バイナリ解析ツールで調べてみようかな

実行ファイルrecursiveが渡される。実行してみるとflagを聞かれる、所謂フラグチェッカー問である。

「問題名からして中で再帰してるんだろうな」と思いつつGhidraで中身を見ると、その期待を裏切らないcheck処理が発見された。

undefined8 check(char *flag,int n)

{
  int iVar1;
  int iVar2;
  size_t sVar3;
  char *pcVar4;
  undefined8 uVar5;

  sVar3 = strlen(flag);
  iVar1 = (int)sVar3;
  if (iVar1 == 1) {
    if (table[n] != *flag) {
      return 1;
    }
  }
  else {
    iVar2 = iVar1 / 2;
    pcVar4 = (char *)malloc((long)iVar2);
    strncpy(pcVar4,flag,(long)iVar2);
    uVar5 = check(pcVar4,n);
    if ((int)uVar5 == 1) {
      return 1;
    }
    pcVar4 = (char *)malloc((long)(iVar1 - iVar2));
    strncpy(pcVar4,flag + iVar2,(long)(iVar1 - iVar2));
    uVar5 = check(pcVar4,iVar2 * iVar2 + n);
    if ((int)uVar5 == 1) {
      return 1;
    }
  }
  return 0;
}

この関数では

• flagの長さが1 → table[n]と一致するかチェック
• flagの長さが2以上 → 半分に分けてそれぞれcheck。後半のcheckはnに半分にした後の長さの2乗を加算

といったような具合でflagをチェックしている。
またcheckを呼び出しているmainでは以下の記述がある

  __isoc99_scanf("%39s%*[^\n]",flag);
  flag_len = strlen(flag);
  if (flag_len == 0x26) {
    uVar1 = check(flag,0);

つまりflagの長さは0x26で確定している。

なので、この再帰関数をそのまま実装して、flagの何文字目がtable[n]に対応しているのかを調べればよい。

#!/usr/bin/env python3

table = バイナリのtableそのまま
flag = [0]*38

def check(s, n, x):
  #print(s)
  sVar3 = len(s)
  iVar1 = sVar3
  if (iVar1 == 1):
    print(f'flag[{x}] = {chr(table[n])}')
    flag[x] = table[n]
    #if (table[n] != s[0]):
      #return 0

  else:
    iVar2 = iVar1 // 2
    pcVar4 = s[:iVar2]
    uVar5 = check(pcVar4, n, x)
    if (uVar5 == 1):
      return 1

    pcVar4 = s[iVar2:]
    uVar5 = check(pcVar4, iVar2 * iVar2 + n, x + iVar2)
    if (uVar5 == 1):
      return 1

  return 0

def main():
  s = 'a'*38
  check(s, 0, 0)

  print(''.join(map(chr, flag)))

main()

ctf4b{r3curs1v3_c4l1_1s_4_v3ry_u53fu1}