网站 › 『脱壳破解区』 › 【reverse】buu-[WUSTCTF2020]level4——二叉树+IDA动态调试

hans7 发表于 2022-9-13 00:41

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

本帖最后由 hans7 于 2022-9-13 00:47 编辑

### 依赖

- 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
**作者：(https://blog.csdn.net/hans774882968)以及(https://juejin.cn/user/1464964842528888)以及(https://www.52pojie.cn/home.php?mod=space&uid=1906177)**

### 思路

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

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

```c
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);   No way!");
puts(&byte_400A37);
return 0;
}
```

看看`init`函数：

```c
unsigned __int64 init()
{
int i; //
char v2; // BYREF
unsigned __int64 v3; //

v3 = __readfsqword(0x28u);
strcpy(v2, "I{_}Af2700ih_secTS2Et_wr");
for ( i = 0; i <= 23; ++i )
    x = v2;
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`：

```c
__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](https://www.52pojie.cn/thread-1686855-1-1.html)）到`init`函数执行完毕时，再`shift+E`导出此时的bss段数据。bss段数据如下，可以很清晰地看到结构体：

### 代码

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

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

```python
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)[::-1])

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

    def solve():
      ans = ''

      def dfs(u: int):
            nonlocal ans
            if u < 0 or u >= len(tree):
                return
            ans += chr(tree)
            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 发表于 2022-9-14 08:24

学习了！！

aspllh 发表于 2022-9-19 11:52

真厉害，大佬，我学到了

查看完整版本: 【reverse】buu-[WUSTCTF2020]level4——二叉树+IDA动态调试