【reverse】buu-[WUSTCTF2020]level4——二叉树+IDA动态调试

hans7

依赖

• IDA7.7+IDA动态调试
• Ubuntu20.04

本文csdn：https://blog.csdn.net/hans774882968/article/details/126825372

本文juejin：https://juejin.cn/post/7142534478538211342/

本文52pojie：https://www.52pojie.cn/thread-1687144-1-1.html
作者：hans774882968以及hans774882968以及hans774882968

思路

Ubuntu下file命令：64位ELF，x86-64。

IDA一打开即可定位到main函数：

int __cdecl main(int argc, const char **argv, const char **envp)
{
  puts("Practice my Data Structure code.....");
  puts("Typing....Struct.....char....*left....*right............emmmmm...OK!");
  init("Typing....Struct.....char....*left....*right............emmmmm...OK!", argv);
  puts("Traversal!");
  printf("Traversal type 1:");
  type1(&unk_601290);
  printf("\nTraversal type 2:");
  type2(&unk_601290);
  printf("\nTraversal type 3:");
  puts("    //type3(&x[22]);   No way!");
  puts(&byte_400A37);
  return 0;
}

看看init函数：

unsigned __int64 init()
{
  int i; // [rsp+Ch] [rbp-34h]
  char v2[40]; // [rsp+10h] [rbp-30h] BYREF
  unsigned __int64 v3; // [rsp+38h] [rbp-8h]

  v3 = __readfsqword(0x28u);
  strcpy(v2, "I{_}Af2700ih_secTS2Et_wr");
  for ( i = 0; i <= 23; ++i )
    x[24 * i] = v2[i];
  qword_601298 = (__int64)&unk_6011E8;
  qword_6011F0 = (__int64)&unk_601260;
  qword_601268 = (__int64)&unk_6010F8;
  qword_601100 = (__int64)&unk_601110;
  qword_601108 = (__int64)&unk_601140;
  qword_601270 = (__int64)&unk_601230;
  qword_601238 = (__int64)&unk_601158;
  qword_601240 = (__int64)&unk_601098;
  qword_6010A0 = (__int64)&unk_601200;
  qword_6010A8 = (__int64)&unk_601188;
  qword_6011F8 = (__int64)&unk_601170;
  qword_601178 = (__int64)&unk_6011B8;
  qword_601180 = (__int64)&unk_6010B0;
  qword_6010B8 = (__int64)x;
  qword_6010C0 = (__int64)&unk_601218;
  qword_6012A0 = (__int64)&unk_601278;
  qword_601280 = (__int64)&unk_6010E0;
  qword_601288 = (__int64)&unk_6011A0;
  qword_6011B0 = (__int64)&unk_601128;
  qword_601130 = (__int64)&unk_6012A8;
  qword_601138 = (__int64)&unk_6011D0;
  qword_6011D8 = (__int64)&unk_601248;
  qword_6011E0 = (__int64)&unk_6010C8;
  return __readfsqword(0x28u) ^ v3;
}

这里qword_601298等变量都处于bss段。init函数给bss段的若干位置赋了一个字符，然后是一系列类似于qword_601298 = 0x6011e8的操作，暂时不清楚含义（下文有解释）。这表明bss段有一个结构体数组，每个结构体占24个字节空间。

接下来看看type1和type2：

__int64 __fastcall type1(char *a1)
{
  __int64 result; // rax

  if ( a1 )
  {
    type1(*((_QWORD *)a1 + 1));
    putchar(*a1);
    return type1(*((_QWORD *)a1 + 2));
  }
  return result;
}

int __fastcall type2(char *a1)
{
  int result; // eax

  if ( a1 )
  {
    type2(*((_QWORD *)a1 + 1));
    type2(*((_QWORD *)a1 + 2));
    return putchar(*a1);
  }
  return result;
}

结合调用的方式type1(&unk_601290) type2(&unk_601290)和bss段有一个结构体数组的事实，不难得出type1和type2分别表示二叉树的中序和后序遍历，*((_QWORD *)a1 + 1)和*((_QWORD *)a1 + 2)分别表示二叉树的左右孩子，而我们期望得到的是前序遍历。因为字符有重复，所以直接通过数据结构课上学到的那个经典算法来确定二叉树应该是不可行的。因此我们需要在init函数执行完毕后，提取二叉树Node结构体数组的信息。至此，我们可以猜到init函数类似于qword_601298 = 0x6011e8的操作是给二叉树节点指定左右孩子，也就是build_tree。获取Node数组最简单的做法是：先IDA动态调试（入门戳这qwq）到init函数执行完毕时，再shift+E导出此时的bss段数据。bss段数据如下，可以很清晰地看到结构体：

代码

提取到二叉树Node结构体数组的信息后，只需要实现前序遍历二叉树了。我们需要做int数组转64位整数的操作，可以用python+libnum库来实现。

参考链接1的代码中，类似x[22].left = 15的语句，自己手动翻译原有代码是很费劲的，也许是写脚本生成出来的，因此我认为我这种写法更好。

from libnum import s2n

def main():
    tree = [
        0x49, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0x00, 0x00, 0x00, 0x7B, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0x00, 0x00, 0x12, 0x60, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x88, 0x11, 0x60, 0x00, 0x00, 0x00, 0x00, 0x00, 0x5F, 0x00,
        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x80, 0x10, 0x60, 0x00,
        0x00, 0x00, 0x00, 0x00, 0x18, 0x12, 0x60, 0x00, 0x00, 0x00,
        0x00, 0x00, 0x7D, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x41, 0x00, 0x00, 0x00,
        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x66, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10, 0x11,
        0x60, 0x00, 0x00, 0x00, 0x00, 0x00, 0x40, 0x11, 0x60, 0x00,
        0x00, 0x00, 0x00, 0x00, 0x32, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x37, 0x00,
        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xA8, 0x12, 0x60, 0x00,
        0x00, 0x00, 0x00, 0x00, 0xD0, 0x11, 0x60, 0x00, 0x00, 0x00,
        0x00, 0x00, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x30, 0x00, 0x00, 0x00,
        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x69, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xB8, 0x11,
        0x60, 0x00, 0x00, 0x00, 0x00, 0x00, 0xB0, 0x10, 0x60, 0x00,
        0x00, 0x00, 0x00, 0x00, 0x68, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x5F, 0x00,
        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0x00, 0x00, 0x00, 0x28, 0x11, 0x60, 0x00, 0x00, 0x00,
        0x00, 0x00, 0x73, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x65, 0x00, 0x00, 0x00,
        0x00, 0x00, 0x00, 0x00, 0x48, 0x12, 0x60, 0x00, 0x00, 0x00,
        0x00, 0x00, 0xC8, 0x10, 0x60, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x63, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x60, 0x12,
        0x60, 0x00, 0x00, 0x00, 0x00, 0x00, 0x70, 0x11, 0x60, 0x00,
        0x00, 0x00, 0x00, 0x00, 0x54, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x53, 0x00,
        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0x00, 0x32, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x58, 0x11, 0x60, 0x00, 0x00, 0x00, 0x00, 0x00, 0x98, 0x10,
        0x60, 0x00, 0x00, 0x00, 0x00, 0x00, 0x45, 0x00, 0x00, 0x00,
        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x74, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xF8, 0x10,
        0x60, 0x00, 0x00, 0x00, 0x00, 0x00, 0x30, 0x12, 0x60, 0x00,
        0x00, 0x00, 0x00, 0x00, 0x5F, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0x00, 0xE0, 0x10, 0x60, 0x00, 0x00, 0x00, 0x00, 0x00,
        0xA0, 0x11, 0x60, 0x00, 0x00, 0x00, 0x00, 0x00, 0x77, 0x00,
        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xE8, 0x11, 0x60, 0x00,
        0x00, 0x00, 0x00, 0x00, 0x78, 0x12, 0x60, 0x00, 0x00, 0x00,
        0x00, 0x00, 0x72, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0x00, 0x00, 0x00, 0x00, 0x00
    ]

    def addr2idx(addr: int) -> int:
        return addr - 0x601080

    def get_left(idx: int) -> int:
        return s2n(bytes(tree[idx + 8:idx + 16])[::-1])

    def get_right(idx: int) -> int:
        return s2n(bytes(tree[idx + 16:idx + 24])[::-1])

    def solve():
        ans = ''

        def dfs(u: int):
            nonlocal ans
            if u < 0 or u >= len(tree):
                return
            ans += chr(tree[u])
            dfs(addr2idx(get_left(u)))
            dfs(addr2idx(get_right(u)))

        dfs(addr2idx(0x601290))
        return ans
    ans = solve()
    print(ans)

if __name__ == "__main__":
    main()

参考资料

1. https://lantern.cool/wp-games-buuctf

iloveasdl

学习了！！

aspllh

真厉害，大佬，我学到了