GUET-CTF2019_Reverse_number-game_writeup

, ,

64bit 文件，无壳

IDA64 打开:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
unsigned __int64 __fastcall main(int a1, char **a2, char **a3)
{
  __int64 v4; // [rsp+8h] [rbp-38h]
  __int64 v5; // [rsp+10h] [rbp-30h] BYREF
  __int16 v6; // [rsp+18h] [rbp-28h]
  __int64 v7; // [rsp+20h] [rbp-20h] BYREF
  __int16 v8; // [rsp+28h] [rbp-18h]
  char v9; // [rsp+2Ah] [rbp-16h]
  unsigned __int64 v10; // [rsp+38h] [rbp-8h]

  v10 = __readfsqword(0x28u);
  v5 = 0LL;
  v6 = 0;
  v7 = 0LL;
  v8 = 0;
  v9 = 0;
  __isoc99_scanf("%s", &v5);
  if ( (unsigned int)sub_4006D6((const char *)&v5) )
  {
    v4 = sub_400758(&v5, 0LL, 10LL);
    sub_400807(v4, (__int64)&v7);
    v9 = 0;
    sub_400881(&v7);
    if ( (unsigned int)sub_400917() )
    {
      puts("TQL!");
      printf("flag{");
      printf("%s", (const char *)&v5);
      puts("}");
    }
    else
    {
      puts("your are cxk!!");
    }
  }
  return __readfsqword(0x28u) ^ v10;
}

从下往上分析

sub_400917

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
__int64 sub_400917()
{
  unsigned int v1; // [rsp+0h] [rbp-10h]
  int i; // [rsp+4h] [rbp-Ch]
  int j; // [rsp+8h] [rbp-8h]
  int k; // [rsp+Ch] [rbp-4h]

  v1 = 1;
  for ( i = 0; i <= 4; ++i )                    // 五列
  {
    for ( j = 0; j <= 4; ++j )                  // 五行
    {
      for ( k = j + 1; k <= 4; ++k )
      {
        if ( *((_BYTE *)&byte_601060 + 5 * i + j) == *((_BYTE *)&byte_601060 + 5 * i + k) )
          v1 = 0;
        if ( *((_BYTE *)&byte_601060 + 5 * j + i) == *((_BYTE *)&byte_601060 + 5 * k + i) )
          v1 = 0;
      }
    }
  }
  return v1;
}

把 byte_601060 （其实原来是 unk_601060, 按 D 可以改写格式） 输出然后格式化数据：

1
2
3
4
5
14#23
30#1#
0#23#
#3##0
42##1

不像迷宫题，应该是一个数独，尝试解一下：

1
Answer: 0 4 2 1 4 2 1 4 3 0

sub_4006D6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
__int64 __fastcall sub_4006D6(const char *a1)
{
  __int64 result; // rax
  int i; // [rsp+1Ch] [rbp-4h]

  if ( strlen(a1) == 10 )
  {
    for ( i = 0; i <= 9; ++i )
    {
      if ( a1[i] > 52 || a1[i] <= 47 )
        goto LABEL_2;
    }
    result = 1LL;
  }
  else
  {
LABEL_2:
    puts("Wrong!");
    result = 0LL;
  }
  return result;
}

输入的长度为10，那最终 flag 的长度应该也是 10, if 语句中做了限制， ASCII 在47 和 52 之间，也就是数字 0-4

继续分析：

sub_400807

1
2
3
4
5
6
7
8
9
10
11
12
13
__int64 __fastcall sub_400807(__int64 a1, __int64 a2)
{
  __int64 result; // rax

  result = a1;
  if ( a1 )
  {
    sub_400807(*(_QWORD *)(a1 + 8), a2);
    *(_BYTE *)(a2 + dword_601080++) = *(_BYTE *)a1;
    result = sub_400807(*(_QWORD *)(a1 + 16), a2);
  }
  return result;
}

二叉树遍历的中序遍历，补充说明见文章最后；也可以动调出来答案的顺序(下标)

本地分析

直接把下标带入二叉树中序遍历：

1
2
3
4
       0
    1     2
  3   4  5  6
7 8  9

那么最终的下标应该是: 7 3 8 1 9 4 0 2 5 6

动调分析

IDA 远程动调
在以下地方打上断点：

  • if ( (unsigned int)sub_4006D6((const char *)&v5) )
  • if ( (unsigned int)sub_400917() )

F9 到第一个断点输入下标 0123456789, 进入第一个绕过的地方：
sub_4006D6 函数中会判断输入的是否在 0-4 之间，很显然我们输入的肯定不在，因为我们要得到二叉树遍历的下标结果

1
2
3
4
5
6
7
.text:0000000000400A5D call    ___isoc99_scanf
.text:0000000000400A62 lea     rax, [rbp+var_30]
.text:0000000000400A66 mov     rdi, rax
.text:0000000000400A69 call    sub_4006D6
.text:0000000000400A6E test    eax, eax
.text:0000000000400A70 jz      loc_400B08
.text:0000000000400A76 lea     rax, [rbp+var_30]

所以可以等 RIP 到 jz loc_400B08 的时候，修改 ZF 寄存器中的值为 0 , 即可继续运行程序 s

在 Hex 00007FFD82669D70 中可以看到我们输入的数据

1
2
3
00007FFD82669D60  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  ................
00007FFD82669D70  30 31 32 33 34 35 36 37  38 39 00 00 00 00 00 00  0123456789......
00007FFD82669D80  00 00 00 00 00 00 00 00  00 00 00 2D 7E 73 00 00  ...........-~s..

F9 运行到 if ( (unsigned int)sub_400917() ) 处，此处 sub_400807(v4, (__int64)&v7); 二叉树遍历已经结束，双击 v7 可以看到下标

1
2
3
4
5
6
7
8
9
10
[stack]:00007FFD82669D80 db  37h ; 7
[stack]:00007FFD82669D81 db  33h ; 3
[stack]:00007FFD82669D82 db  38h ; 8
[stack]:00007FFD82669D83 db  31h ; 1
[stack]:00007FFD82669D84 db  39h ; 9
[stack]:00007FFD82669D85 db  34h ; 4
[stack]:00007FFD82669D86 db  30h ; 0
[stack]:00007FFD82669D87 db  35h ; 5
[stack]:00007FFD82669D88 db  32h ; 2
[stack]:00007FFD82669D89 db  36h ; 6

顺序和静态分析的一样 7 3 8 1 9 4 0 5 2 6

最后结果

Answer: 0 4 2 1 4 2 1 4 3 0 按照顺序 7 3 8 1 9 4 0 5 2 6 调换位置输出，最终答案是:

1
2
3
4
5
6
7
8
9
flag = [''] * 10
j = 0
answer = '0421421430'
for i in '7381940526':
    flag[int(i)] = answer[j]
    j += 1
print("flag{" + ''.join(flag) + "}")

# flag{1134240024}

补充： 二叉树遍历识别

1
2
3
4
     1
  2     3
4   5     6
   7  8

前序遍历：1 2 4 5 7 8 3 6
中序遍历：4 2 7 5 8 1 3 6
后序遍历：4 7 8 5 2 6 3 1

逆向中可能遇到的伪代码：

  • 先序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
__int64 __fastcall preorder_traverse(__int64 a1, __int64 a2)
{
  __int64 result;

  result = a1;
  if (a1)
  {
    *(_BYTE *)(a2 + dword_601080++) = *(_BYTE *)a1; // ① 先处理根节点
    preorder_traverse(*(_QWORD *)(a1 + 8), a2);     // ② 再访问左子树
    result = preorder_traverse(*(_QWORD *)(a1 + 16), a2); // ③ 最后访问右子树
  }
  return result;
}
  • 中序遍历
1
2
3
4
5
6
7
8
9
__int64 __fastcall sub_400807(__int64 a1, __int64 a2)
result = a1;
if ( a1 )
{
    sub_400807(*(_QWORD *)(a1 + 8), a2); // 递归访问左子树
    *(_BYTE *)(a2 + dword_601080++) = *(_BYTE *)a1; // 处理当前节点的数据（写入目标缓冲区）
    result = sub_400807(*(_QWORD *)(a1 + 16), a2); // 递归访问右子树
}
return result;
  • 后序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
__int64 __fastcall postorder_traverse(__int64 a1, __int64 a2)
{
  __int64 result;

  result = a1;
  if (a1)
  {
    postorder_traverse(*(_QWORD *)(a1 + 8), a2);        // ① 左子树
    postorder_traverse(*(_QWORD *)(a1 + 16), a2);       // ② 右子树
    *(_BYTE *)(a2 + dword_601080++) = *(_BYTE *)a1;     // ③ 根节点
  }
  return result;
}