BUUCTF-[RoarCTF2019]polyre 详细WP

OLLVM 与去平坦化 & 有无符号数 & 整数溢出

Posted by WuJ on April 30, 2020

OLLVM 与去平坦化 & [RoarCTF2019] polyre 详细WP

OLLVM

llvm是一个底层虚拟机,OLLVM(Obfuscator-LLVM)是瑞士西北应用科技大学安全实验室于2010年6月份发起的一个项目,这个项目的目标是提供一个LLVM编译套件的开源分支,能够通过代码混淆和防篡改,增加对逆向工程的难度,提供更高的软件安全性。目前,OLLVM已经支持LLVM-4.0.1版本;所使用的编译器是clang。

llvm保护的大概方法是:程序主要使用一个主分发器来控制程序基本块的执行流程进而模糊每个模块之间的联系。

平坦化程序特征

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
__int64 __fastcall check(__int64 a1)
{
  size_t v1; // rax@13
  signed int v2; // ecx@13
  char v3; // ST04_1@16
  signed int v4; // eax@18
  signed int v5; // eax@21
  signed int v6; // eax@24
  signed int v7; // eax@27
  signed int v9; // [sp+44h] [bp-1Ch]@1
  int v10; // [sp+48h] [bp-18h]@1
  signed int v11; // [sp+5Ch] [bp-4h]@0

  srand(0x64u);
  v10 = 0;
  v9 = 706310565;
  while ( 1 )
  {
    while ( 1 )
    {
      while ( 1 )
      {
        while ( 1 )
        {
          while ( 1 )
          {
            while ( 1 )
            {
              while ( 1 )
              {
                while ( 1 )
                {
                  while ( v9 == -2109444161 )
                  {
                    v7 = 1322041670;
                    if ( *(_BYTE *)(a1 + 3) == 100 )
                      v7 = 867560817;
                    v9 = v7;
                  }
                  if ( v9 != -2069803162 )
                    break;
                  ++v10;
                  v9 = 706310565;
                }
                if ( v9 != 306556692 )
                  break;
                v4 = 1322041670;
                if ( *(_BYTE *)a1 == 97 )
                  v4 = 564228819;
                v9 = v4;
              }
              if ( v9 != 341947172 )
                break;
              v6 = 1322041670;
              if ( *(_BYTE *)(a1 + 2) == 99 )
                v6 = -2109444161;
              v9 = v6;
            }
            if ( v9 != 564228819 )
              break;
            v5 = 1322041670;
            if ( *(_BYTE *)(a1 + 1) == 98 )
              v5 = 341947172;
            v9 = v5;
          }
          if ( v9 != 682671478 )
            break;
          v3 = *(_BYTE *)(a1 + v10);
          *(_BYTE *)(a1 + v10) = rand() % 5 + v3 - 97 + 97;
          v9 = -2069803162;
        }
        if ( v9 != 706310565 )
          break;
        v1 = strlen((const char *)a1);
        v2 = 306556692;
        if ( v10 < v1 )
          v2 = 682671478;
        v9 = v2;
      }
      if ( v9 != 867560817 )
        break;
      v11 = 4;
      v9 = 1000770411;
    }
    if ( v9 == 1000770411 )
      break;
    if ( v9 == 1322041670 )
    {
      v11 = 0;
      v9 = 1000770411;
    }
  }
  return (unsigned int)v11;
}

1

尝试进行函数的恢复

  1. 函数的开始地址为序言的地址
  2. 序言的后继为主分发器
  3. 后继为主分发器的块为预处理器
  4. 后继为预处理器的块为真实块
  5. 无后继的块为retn块
  6. 剩下的为无用块

deflat 去平坦化脚本使用方法

deflat.py

最早版本 [python2] https://github.com/SnowGirls/deflat

修改版 [python3] https://github.com/cq674350529/deflat

使用方法

进入 angr 虚拟环境

python deflat.py -f path/to/binary --addr hexaddress

示例 1

这是自带的 sample check_passwd_flat

image-20200430011431202

用 ida 打开发现是平坦化的

关键之处在于寻找程序的 address

注意到“函数的开始地址为序言的地址”,因此我们需要在序言中找函数起始位置

image-20200430011732697

image-20200430011801733

如上图,地址为 0x400530

运行脚本 (注意需要把下图两个文件从上层目录复制过来)

image-20200430011920780

运行结果

image-20200430012346936

发现已经成功去平坦化

image-20200430012444846

示例 2 —— [RoarCTF2019] polyre WP

去平坦化

IDA 打开程序

Xnip2020-04-30_00-32-05

找序言的函数起始位置

Xnip2020-04-30_00-55-26

运行程序

python deflat.py -f polyre --addr 0x400620

运行结果,成功去平坦化

Xnip2020-04-30_01-10-02

分析代码

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
__int64 __fastcall main(__int64 a1, char **a2, char **a3)
{
  signed __int64 v4; // [rsp+1E0h] [rbp-110h]
  int i; // [rsp+1E8h] [rbp-108h]
  int v6; // [rsp+1ECh] [rbp-104h]
  int v7; // [rsp+1ECh] [rbp-104h]
  char s1[48]; // [rsp+1F0h] [rbp-100h]
  char s[60]; // [rsp+220h] [rbp-D0h]
  unsigned int v10; // [rsp+25Ch] [rbp-94h]
  char *input; // [rsp+260h] [rbp-90h]
  int v12; // [rsp+26Ch] [rbp-84h]
  bool v13; // [rsp+272h] [rbp-7Eh]
  unsigned __int8 v14; // [rsp+273h] [rbp-7Dh]
  int v15; // [rsp+274h] [rbp-7Ch]
  char *v16; // [rsp+278h] [rbp-78h]
  int v17; // [rsp+284h] [rbp-6Ch]
  int v18; // [rsp+288h] [rbp-68h]
  bool v19; // [rsp+28Fh] [rbp-61h]
  char *v20; // [rsp+290h] [rbp-60h]
  int v21; // [rsp+298h] [rbp-58h]
  bool v22; // [rsp+29Fh] [rbp-51h]
  __int64 v23; // [rsp+2A0h] [rbp-50h]
  bool v24; // [rsp+2AFh] [rbp-41h]
  __int64 v25; // [rsp+2B0h] [rbp-40h]
  __int64 v26; // [rsp+2B8h] [rbp-38h]
  __int64 v27; // [rsp+2C0h] [rbp-30h]
  __int64 v28; // [rsp+2C8h] [rbp-28h]
  int v29; // [rsp+2D0h] [rbp-20h]
  int v30; // [rsp+2D4h] [rbp-1Ch]
  char *v31; // [rsp+2D8h] [rbp-18h]
  int v32; // [rsp+2E0h] [rbp-10h]
  int v33; // [rsp+2E4h] [rbp-Ch]
  bool v34; // [rsp+2EBh] [rbp-5h]

  v10 = 0;
  memset(s, 0, 0x30uLL);
  memset(s1, 0, 0x30uLL); 
  printf("Input:", 0LL);
  input = s;
  if ( dword_603058 >= 10 && (((_BYTE)dword_603054 - 1) * (_BYTE)dword_603054 & 1) != 0 ) // 这行代码出现很多次,但对程序本身并无实际意义,是去平坦化的遗留产物
    goto LABEL_43;
  while ( 1 )
  {
    __isoc99_scanf((__int64)"%s", (__int64)input); //
    v6 = 0;
    if ( dword_603058 < 10 || (((_BYTE)dword_603054 - 1) * (_BYTE)dword_603054 & 1) == 0 )
      break;
LABEL_43:
    __isoc99_scanf((__int64)"%s", (__int64)input);
  }
  while ( 1 )
  {
    do
      v12 = v6;
    while ( dword_603058 >= 10 && (((_BYTE)dword_603054 - 1) * (_BYTE)dword_603054 & 1) != 0 );
    v13 = v12 < 64;
    while ( dword_603058 >= 10 && (((_BYTE)dword_603054 - 1) * (_BYTE)dword_603054 & 1) != 0 )
      ;
    if ( !v13 )
      break;
    v14 = s[v6];
    do
      v15 = v14;
    while ( dword_603058 >= 10 && (((_BYTE)dword_603054 - 1) * (_BYTE)dword_603054 & 1) != 0 );
    if ( v15 == 10 )
    {
      v16 = &s[v6];
      *v16 = 0;
      break;
    }
    v17 = v6 + 1;
    do
      v6 = v17;
    while ( dword_603058 >= 10 && (((_BYTE)dword_603054 - 1) * (_BYTE)dword_603054 & 1) != 0 );
  }
  for ( i = 0; ; ++i ) // 关键循环
  {
    do
      v18 = i;
    while ( dword_603058 >= 10 && (((_BYTE)dword_603054 - 1) * (_BYTE)dword_603054 & 1) != 0 );
    do
      v19 = v18 < 6; // 外层循环 6 次
    while ( dword_603058 >= 10 && (((_BYTE)dword_603054 - 1) * (_BYTE)dword_603054 & 1) != 0 );
    if ( !v19 )
      break;
    do
      v20 = s;
    while ( dword_603058 >= 10 && (((_BYTE)dword_603054 - 1) * (_BYTE)dword_603054 & 1) != 0 );
    v4 = *(_QWORD *)&v20[8 * i]; // 将输入转为 8 个 signed long long 类型
    v7 = 0;
    while ( 1 )
    {
      v21 = v7;
      do
        v22 = v21 < 64; // 内层循环 64 次
      while ( dword_603058 >= 10 && (((_BYTE)dword_603054 - 1) * (_BYTE)dword_603054 & 1) != 0 );
      if ( !v22 )
        break;
      v23 = v4;
      v24 = v4 < 0;
      if ( v4 >= 0 ) // 若 v4 大于 0
      {
        v27 = v4;
        do
          v28 = 2 * v27; // v4 * 2
        while ( dword_603058 >= 10 && (((_BYTE)dword_603054 - 1) * (_BYTE)dword_603054 & 1) != 0 );
        v4 = v28;
      }
      else // 若 v4 小于 0
      {
        v25 = 2 * v4; // v4 * 2
        do
          v26 = v25;
        while ( dword_603058 >= 10 && (((_BYTE)dword_603054 - 1) * (_BYTE)dword_603054 & 1) != 0 );
        v4 = v26 ^ 0xB0004B7679FA26B3LL; // 之后异或
      }
      v29 = v7;
      do
        v7 = v29 + 1;
      while ( dword_603058 >= 10 && (((_BYTE)dword_603054 - 1) * (_BYTE)dword_603054 & 1) != 0 );
    }
    v30 = 8 * i;
    v31 = &s1[8 * i];
    if ( dword_603058 >= 10 && (((_BYTE)dword_603054 - 1) * (_BYTE)dword_603054 & 1) != 0 )
LABEL_55:
      *(_QWORD *)v31 = v4;
    *(_QWORD *)v31 = v4;
    if ( dword_603058 >= 10 && (((_BYTE)dword_603054 - 1) * (_BYTE)dword_603054 & 1) != 0 )
      goto LABEL_55;
    v32 = i + 1;
  }
  do
    v33 = memcmp(s1, &unk_402170, 0x30uLL); // 最后按字节进行比较
  while ( dword_603058 >= 10 && (((_BYTE)dword_603054 - 1) * (_BYTE)dword_603054 & 1) != 0 )
    ;
  if ( v34 )
    puts("Wrong!");
  else
    puts("Correct!");
  return v10;
}

伪代码

加密算法大致是:输入 48,平分 6 组,将每组 8 字节转化为 long 类型的值,对每组进行加密,先判断正负,然后将值乘 2,随后根据正负异或 0xB0004B7679FA26B3,循环 64 次,最后进行比较

1
2
3
4
5
6
7
8
i=0
#x=?
while(i<64):
    if x>=0:
        x=x<<1
    else:
        x=(x<<1)^0xB0004B7679FA26B3
    i=i+1

逆向求解

这里我们需要注意,输入被转为 signed long long(有符号 int64)存为 v4

每次运算前需要判断 v4 的正负

但是我们逆向写代码时是不能根据正负来判断运算分支的!!!

原因就是我们无法得知 x = (x << 1) ^ 0xB0004B7679FA26B3 或者 x << 1 运算结束后,x 作为有符号数到底是正数负数

即,即使 a 为正/负数,经过上述运算之后也可能变成相反符号的 b;因此我们在求逆时,不能根据 b 为正数,就使用 b << 1 来运算,这就会出问题

那如何才能准确判断分支呢?

我们注意到,一个数乘 2 之后一定是偶数,一个偶数 ^ 0xB0004B7679FA26B3 一定是奇数。因此我们求逆运算时必须根据奇偶性判断分支

即,若 x 为偶数,使用 x >> 1 求逆

若 x 为奇数,使用 (x ^ 0xB0004B7679FA26B3) >> 1 求逆

这就是本题最核心的地方

程序中的 v4 是一个有符号数,这就会导致一些正数溢出变成负数,即正数不会一直乘 2 下去,超过 long long 的取值范围 0x7fffffffffffffff 后就会溢出变成负数,通过下面代码也能明显看出正负交替(PS. 乘 2 操作是通过左移 1 位实现的)

image-20200430141140593

另一处需要注意的就是:

加密运算时,负数 x 经过 (x << 1 ) ^ 0xB0004B7679FA26B3 变成了正数 y ;解密时,正数 y 经过 (y ^ 0xB0004B7679FA26B3) >> 1 一定还是正数,因此,当在负数分支时,解密脚本最后要和 0x800000000000000 进行或运算,这样只会修改第一位变成 1(有符号数第一位决定正负,正为 0 负为 1)

完整解密脚本

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
origin = [0xbc8ff26d43536296,
          0x520100780530ee16,
          0x4dc0b5ea935f08ec,
          0x342b90afd853f450,
          0x8b250ebcaa2c3681,
          0x55759f81a2c68ae4]
key = 0xB0004B7679FA26B3
data = ""

for value in origin:
    for i in range(0, 64):
     	  # 判断奇偶
        parity = value & 1 
        if parity == 1:
            value = (value ^ key) >> 1
            value = value | 0x8000000000000000
        else:
            value = value >> 1
    print(hex(value))
    j = 0
    while (j < 8):
        # 因为是小端序,需要从最后一个字节开始取
        data += chr(value & 0xFF)
        # 右移 8 位,倒着取字节
        value = value >> 8
        j += 1
print(data)

附:各种类型的取值范围:

类型 字节 范围
short int 2byte(word) 0~32767(0~0x7fff) -32768~-1(0x8000~0xffff)
unsigned short int 2byte(word) 0~65535(0~0xffff)
int 4byte(dword) 0~2147483647(0~0x7fffffff) -2147483648~-1(0x80000000~0xffffffff)
unsigned int 4byte(dword) 0~4294967295(0~0xffffffff)
long int 8byte(qword) 正: 0~0x7fffffffffffffff 负: 0x8000000000000000~0xffffffffffffffff
unsigned long int 8byte(qword) 0~0xffffffffffffffff

运行结果

1
2
3
4
5
6
7
8
[Running] python -u "polyre.py"
0x6666367b67616c66
0x63362d3039333932
0x2d363563342d3032
0x3539612d30376162
0x6631643365383537
0x7d38
flag{6ff29390-6c20-4c56-ba70-a95758e3d1f8}

参考链接

利用符号执行去除控制流平坦化

https://paper.seebug.org/1059/#polyre