Notice

本文首发于安全客，欢迎各位捧场：链接

简介

这次的TCTF 2021 Final有队友们的鼎力相助，拿了Rising Star的冠军，十分刺激。其中收获比较大的是0bf这道题目，这是一个10轮的加密算法，代码有大量混淆，加密逻辑没法直观地看出来。赛后官方的writeup是去混淆再解，但在比赛时没有足够的时间来研究混淆的规律，只能硬着头皮分析。这道题目也是我第一次用Unicorn来模拟函数逻辑，收获还是很大。

程序逻辑

由于代码经过了混淆，函数严重膨胀，首先要修改IDA的配置文件，将函数大小的上限调高，IDA反编译插件的配置文件在IDA安装目录\cfg\hexrays.cfg，打开找到MAX_FUNCSIZE，改成一个大数，再重新分析程序的加密函数sub_11C9，等上十几分钟，反编译完成后把代码复制到一个文件中，重新格式化成每个赋值语句一行的形式，方便查看。我上传了一份反编译后的代码，有需要可以下载。

这时从VSCode的代码缩略图中就可以看出，该加密函数有明显的重复部分，例如函数入口的两行：

1
2

  v2 = 12 * (*a1 & 0x4138B65C) + 8 * ~(*a1 & 0xBEC749A3) + (*a1 & 0xBEC749A3) + 1 - 6 * (*a1 ^ 0xBEC749A3) + 8 * ~*a1 + *a1 + 1 - 2 * (*a1 | 0xBEC749A3) - 4 * ~(*a1 | 0xBEC749A3) - 4 * ~(*a1 | 0x4138B65C) + 5 * (*a1 & 0xBEC749A3) + 1688020449;
  v3 = 2636545543LL * v1;

和第二轮开始的部分：

1
2

  v106 = 12 * (v103 & 0x70E38EE0) + 8 * ~(v103 & 0x8F1C711F) + (v103 & 0x8F1C711F) + 1 - 6 * (v103 ^ 0x8F1C711F) + 8 * ~v103 + v103 + 1 - 2 * (v103 | 0x8F1C711F) - 4 * ~(v103 | 0x8F1C711F) - 4 * ~(v103 | 0x70E38EE0) + 5 * (v103 & 0x8F1C711F) + 1583631427;
  v107 = 4225108746u * v105;

以及第三轮开始的部分：

1
2

  v209 = 12 * (v206 & 0xEEE7AAAE) + 8 * ~(v206 & 0x11185551) + (v206 & 0x11185551) + 1 - 6 * (v206 ^ 0x11185551) + 8 * ~v206 + v206 + 1 - 2 * (v206 | 0x11185551) - 4 * ~(v206 | 0x11185551) - 4 * ~(v206 | 0xEEE7AAAE) + 5 * (v206 & 0x11185551) + 1862844314;
  v210 = 3734538576u * v208;

仔细寻找类似的代码，可以将整个加密函数分成10轮，每轮之间传递两个32位的值。第一轮的输入是a1开始的8字节，第二轮输入是第一轮计算产生的v103和v105两个值，依次类推，第10轮完成后计算结果作为加密后的8字节。

第一轮代码大致结构如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

  v1 = (unsigned int)a1[1];
  v2 = 12 * (*a1 & 0x4138B65C) + 8 * ~(*a1 & 0xBEC749A3) + ...;
  v3 = 2636545543LL * v1;
  if (2636545543LL * v1) {
    ...
    v10 = 6 * ~((HIDWORD(v9) - 1) | ~(_DWORD)v9 | 0x9D267E07) + 2 * (v9 & ((HIDWORD(v9) - 1) | 0x9D267E07)) - ...;
  } else {
    ...
    v10 = 4 * (~((v1 - 1) | 0x9D267E05) - 3 * ~((v1 - 1) | 0x62D981FA)) - ...;
  }
  v12 = 300216365LL * (21 * (v10 & ~v2 & 0xEE1B0FD2) + 10 * ~(v10 | ~v2 | 0xEE1B0FD2) + ...;
  if (v12) {
    v1222 = -4 * (-(__int64)HIDWORD(v12) ^ (unsigned int)v12);
    v1182 = 6 * (v12 | (HIDWORD(v12) - 1)) + 5 * (~(unsigned __int64)(unsigned int)v12 & (v12 | (HIDWORD(v12) - 1)) ^ -(__int64)HIDWORD(v12));
    ...
  } else {
    v20 = 2 * ~((21 * (v10 & ~v2 & 0xEE1B0FD2) + 10 * ~(v10 | ~v2 | 0xEE1B0FD2) + ....;
    v21 = v20 - (-(21 * (v10 & ~v2 & 0xEE1B0FD2) + 10 * ~(v10 | ~v2 | 0xEE1B0FD2) + ...;
    ...
  }
  ...
  v103 = 4 * (v2 & v93 & v101) - 21 * (v2 & v93 & ~(_DWORD)v101) + ...;
  v105 = 26 * (v10 & v101 & ~v97) + ((unsigned int)v101 & v10 | v97 ^ v101) + ...;

从上面的代码可以将一轮的加密过程总结如下：

1、将本轮输入*a1，a1[1]经过短暂的处理，变为两个新的32位数v2 = s(*a1)和v10 = t(a[1])，再用这两个数计算第三个值v12 = r(v2, v10)。

2、此后的计算仅依赖于第三个值v12（注意计算出v12后，下面的代码对v2和v10的使用形式与v12完全相同，均为21 * (v10 & ~v2 & 0xEE1B0FD2) + ...，实际上这个表达式还是v12）。

3、将第二步的计算结果记为f(v12)，则两个输出32位值v103和v105分别为g(v2, f(v12))和h(v10, f(v12))。

r，s，t，f，g，h的具体操作未知。

分析

在没法去除混淆的情况下，只能将各段代码分别看作不同的黑盒，通过改变黑盒的输入，观察黑盒的输出，来猜测黑盒中的逻辑。

IDA的反汇编代码中用到的_DWORD，LOWORD，__CFADD__等宏定义可以从IDA安装目录\plugins\defs.h中找到，以分析v2 = s(*a1)中的s函数为例，将IDA反汇编重新改为C代码：

 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

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#include "defs.h"

void f(unsigned int* a1) {
  unsigned int v2 = 12 * (*a1 & 0x4138B65C) + 8 * ~(*a1 & 0xBEC749A3) +
                    (*a1 & 0xBEC749A3) + 1 - 6 * (*a1 ^ 0xBEC749A3) + 8 * ~*a1 +
                    *a1 + 1 - 2 * (*a1 | 0xBEC749A3) - 4 * ~(*a1 | 0xBEC749A3) -
                    4 * ~(*a1 | 0x4138B65C) + 5 * (*a1 & 0xBEC749A3) +
                    1688020449;
  printf("%x %x\n", *a1, v2);
}

int main() {
  srand((unsigned)time(NULL));
  unsigned int a, x;
  for (a = 0; a < 256; a++) {
    x = a;
    f(&x);
  }
  for (a = 0; a < 256; a++) {
    x = rand();
    f(&x);
  }
  return 0;
}

输入0-255的所有值，再输入一些随机的值，可以观察出s函数实际为s(x) = x + 0x6e62d8bf，通过类似的方法还可以确定r(x, y) = g(x, y) = h(x, y) = x ^ y，t(x) = (x*0x9d267e07-((x*0x9d267e07)>>32))&0xFFFFFFFF。剩余f过于复杂，没法直接观察出结果。单轮加密可以总结如下：

1
2
3
4
5
6
7

输入：32位值a，b
输出：32位值x，y
v1=(a*C1-((a*C1)>>32))&0xFFFFFFFF
v2=b+C2
v3=v1^v2
x=v1^f(v3)
y=v2^f(v3)

解法

不去混淆的情况下，程序中唯一无法求逆的是f函数，但观察得知f函数的可以通过异或来消去。给定加密结果x，y，若取v1'=x^y, v2'=0，则v3'=x^y，x'=v1'^f(v3')=x^y^f(x^y)，y'=v2'^f(v3')=f(x^y)，可以发现新的加密中的y'即原先的加密时f函数的输出，再将y'分别与x，y异或，可以求出原先加密时的v1和v2。

再取a'=0, b'=1，则v1'=C1, v2'=C2，加上上一步解出的v1和v2，就可以推出最初的a和b。这样就可以在不对f函数求逆的情况下进行解密。

利用Unicorn可以方便地对代码片段进行部分模拟。模拟执行的关键在于找到一个合适的起点和终点，将二者之间的代码视为一个黑盒，并且使该黑盒对外部信息的依赖尽可能地小，方便模拟。

加密函数sub_11C9的开头部分如下：

 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

.text:00000000000011C9                   ; __unwind {
.text:00000000000011C9 F3 0F 1E FA                       endbr64
.text:00000000000011CD 55                                push    rbp
.text:00000000000011CE 48 89 E5                          mov     rbp, rsp
.text:00000000000011D1 41 57                             push    r15
.text:00000000000011D3 41 56                             push    r14
.text:00000000000011D5 41 55                             push    r13
.text:00000000000011D7 41 54                             push    r12
.text:00000000000011D9 53                                push    rbx
.text:00000000000011DA 48 89 7D C0                       mov     [rbp+var_40], rdi
.text:00000000000011DE 48 8B 45 C0                       mov     rax, [rbp+var_40]
.text:00000000000011E2 8B 00                             mov     eax, [rax]
.text:00000000000011E4 41 89 C5                          mov     r13d, eax
.text:00000000000011E7 48 8B 45 C0                       mov     rax, [rbp+var_40]
.text:00000000000011EB 48 83 C0 04                       add     rax, 4
.text:00000000000011EF 8B 00                             mov     eax, [rax]
.text:00000000000011F1 41 89 C4                          mov     r12d, eax
.text:00000000000011F4 B8 A3 49 C7 BE                    mov     eax, 0BEC749A3h
.text:00000000000011F9 4C 31 E8                          xor     rax, r13
.text:00000000000011FC 48 89 C2                          mov     rdx, rax
.text:00000000000011FF 48 89 D0                          mov     rax, rdx
.text:0000000000001202 48 C1 E2 02                       shl     rdx, 2
.text:0000000000001206 48 29 D0                          sub     rax, rdx
.text:0000000000001209 48 01 C0                          add     rax, rax
.text:000000000000120C 48 89 C1                          mov     rcx, rax
.text:000000000000120F 4C 89 E8                          mov     rax, r13

可以将0x11F4作为模拟的起点，此时r12和r13寄存器中分别存放了首轮的输入值。第一轮的结束位于0xF7AD，此时加密结果也存放在r12和r13寄存器中。我们同时还需要中途控制v3并检查v1和v2的值，因此还需要找到一个中间点，可以选在0x241A，此时r12和r13寄存器中分就是v1和v2。代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

void solve(uint64_t start,
           uint64_t middle,
           uint64_t end,
           uint64_t x,
           uint64_t y,
           uint64_t* ox,
           uint64_t* oy) {
  uint64_t z, w, s, t;
  uint32_t a, b;
  do_emulation(binary, start, middle, 1, 0, &s, &t);
  do_emulation(binary, middle, end, x ^ y, 0, &z, &w);
  printf("z=%lx w=%lx s=%lx t=%lx\n", z, w, s, t);
  b = (w ^ y) - t;
  uint64_t m, n;
  assert(exgcd(0x100000001, s, &m, &n) == 1);
  a = ((x ^ w) * n) % 0x100000001;
  if (n & (1UL << 63)) {
    a -= 1;
  }
  printf("n=%lx a=%x b=%x\n", n, a, b);
  *ox = a;
  *oy = b;
}

其中do_emulation是用Unicorn模拟执行代码片段，第一次我们从起点开始，a和b分别取1和0，运行到中间点，根据上面的分析，此时r12=C2, r13=C1，将结果保存为s和t。第一次我们从中间点开始，v1和v2分别取x^y和0，运行到终点，根据上面的分析，此时r12=x^y^f(x^y), r13=f(x^y)，将结果保存为z和w。再通过v1=w^x, v2=w^y继续逆推出v1和v2。b=v2-C2, a=(v1*n)%0x100000001，其中n是C1对0x100000001的乘法逆元。

Unicorn的使用

接下来是do_emulation的实现：

 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

void do_emulation(FILE* fp,
                  uint64_t start,
                  uint64_t end,
                  uint64_t r12,
                  uint64_t r13,
                  uint64_t* x,
                  uint64_t* y) {
  uc_engine* uc;
  uint64_t size = end - start;
  uint64_t rsp = 0x280000, rbp = 0x2c0000;

  assert(uc_open(UC_ARCH_X86, UC_MODE_64, &uc) == UC_ERR_OK);
  assert(uc_mem_map(uc, 0x1000, 0x100000, UC_PROT_ALL) == UC_ERR_OK);
  assert(uc_mem_map(uc, 0x200000, 0x100000, UC_PROT_ALL) == UC_ERR_OK);
  assert(fseek(fp, start, SEEK_SET) == 0);
  assert(fread(buf, size, 1, fp) == 1);
  assert(uc_mem_write(uc, start, buf, size) == UC_ERR_OK);
  assert(uc_reg_write(uc, UC_X86_REG_RSP, &rsp) == UC_ERR_OK);
  assert(uc_reg_write(uc, UC_X86_REG_RBP, &rbp) == UC_ERR_OK);
  assert(uc_reg_write(uc, UC_X86_REG_R12, &r12) == UC_ERR_OK);
  assert(uc_reg_write(uc, UC_X86_REG_R13, &r13) == UC_ERR_OK);
  assert(uc_emu_start(uc, start, end, 0, 0) == UC_ERR_OK);
  assert(uc_reg_read(uc, UC_X86_REG_R12, x) == UC_ERR_OK);
  assert(uc_reg_read(uc, UC_X86_REG_R13, y) == UC_ERR_OK);
  uc_close(uc);
}

题目是PIE程序，为了省去重定位过程，直接将.text段映射到0x1000地址处。再分配一个空的栈段，将rsp和rbp都指向栈段，r12和r13填入输入值，调用uc_emu_start开始运行即可。

将Unicorn下载下来并编译，一般不建议将自己编译的东西用make install安装到系统目录，避免和已有的东西冲突。网上很多教程编译OpenSSL都敢直接安装到/usr/lib，很多依赖OpenSSL的系统程序都会因此载入错误版本的libssl而无法运行。

采用静态链接+局部包含路径的方式可以很方便地使用自编译的第三方库，同时不污染环境，适合编译仅运行一次的程序，链接到Unicorn时可以使用如下指令：

1

gcc solve.c -I /xxx/download/unicorn/include/ /xxx/download/unicorn/libunicorn.a -lm -lpthread

-I选项指定头文件的搜索目录，同时把静态库libunicorn.a直接作为链接器输入，再链接到libm和libpthread即可编译出一个可独立运行的模拟程序。

完整代码如下：

  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

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

#include <unicorn/unicorn.h>

unsigned char buf[0x100000];
FILE* binary;

uint64_t exgcd(uint64_t a, uint64_t b, uint64_t* x, uint64_t* y) {
  if (b == 0) {
    *x = 1;
    *y = 0;
    return a;
  }
  uint64_t r = exgcd(b, a % b, x, y);
  uint64_t t = *y;
  *y = *x - (a / b) * (*y);
  *x = t;
  return r;
}

void do_emulation(FILE* fp,
                  uint64_t start,
                  uint64_t end,
                  uint64_t r12,
                  uint64_t r13,
                  uint64_t* x,
                  uint64_t* y) {
  uc_engine* uc;
  uint64_t size = end - start;
  uint64_t rsp = 0x280000, rbp = 0x2c0000;

  assert(uc_open(UC_ARCH_X86, UC_MODE_64, &uc) == UC_ERR_OK);
  assert(uc_mem_map(uc, 0x1000, 0x100000, UC_PROT_ALL) == UC_ERR_OK);
  assert(uc_mem_map(uc, 0x200000, 0x100000, UC_PROT_ALL) == UC_ERR_OK);
  assert(fseek(fp, start, SEEK_SET) == 0);
  assert(fread(buf, size, 1, fp) == 1);
  assert(uc_mem_write(uc, start, buf, size) == UC_ERR_OK);
  assert(uc_reg_write(uc, UC_X86_REG_RSP, &rsp) == UC_ERR_OK);
  assert(uc_reg_write(uc, UC_X86_REG_RBP, &rbp) == UC_ERR_OK);
  assert(uc_reg_write(uc, UC_X86_REG_R12, &r12) == UC_ERR_OK);
  assert(uc_reg_write(uc, UC_X86_REG_R13, &r13) == UC_ERR_OK);
  assert(uc_emu_start(uc, start, end, 0, 0) == UC_ERR_OK);
  assert(uc_reg_read(uc, UC_X86_REG_R12, x) == UC_ERR_OK);
  assert(uc_reg_read(uc, UC_X86_REG_R13, y) == UC_ERR_OK);
  uc_close(uc);
}

void solve(uint64_t start,
           uint64_t middle,
           uint64_t end,
           uint64_t x,
           uint64_t y,
           uint64_t* ox,
           uint64_t* oy) {
  uint64_t z, w, s, t;
  uint32_t a, b;
  do_emulation(binary, middle, end, x ^ y, 0, &z, &w);
  do_emulation(binary, start, middle, 1, 0, &s, &t);
  printf("z=%lx w=%lx s=%lx t=%lx\n", z, w, s, t);
  b = (w ^ y) - t;
  uint64_t m, n;
  assert(exgcd(0x100000001, s, &m, &n) == 1);
  a = ((x ^ w) * n) % 0x100000001;
  if (n & (1UL << 63)) {
    a -= 1;
  }
  printf("n=%lx a=%x b=%x\n", n, a, b);
  *ox = a;
  *oy = b;
}

void decrypt(uint32_t xx, uint32_t yy, uint32_t* a, uint32_t* b) {
  uint64_t x = xx, y = yy;
  solve(0x83A25, 0x84C19, 0x92756, x, y, &x, &y);
  solve(0x75467, 0x76695, 0x83A25, x, y, &x, &y);
  solve(0x66ED9, 0x680D2, 0x75467, x, y, &x, &y);
  solve(0x58191, 0x5938A, 0x66ED9, x, y, &x, &y);
  solve(0x4949C, 0x4A68D, 0x58191, x, y, &x, &y);
  solve(0x3AF70, 0x3C19B, 0x4949C, x, y, &x, &y);
  solve(0x2CA30, 0x2DC24, 0x3AF70, x, y, &x, &y);
  solve(0x1E4DE, 0x1F70E, 0x2CA30, x, y, &x, &y);
  solve(0xF7AD, 0x109DB, 0x1E4DE, x, y, &x, &y);
  solve(0x11F4, 0x241A, 0xF7AD, x, y, &x, &y);
  *a = x;
  *b = y;
}

int main() {
  uint32_t x[] = {0xc94dac3e, 0xb2d4f81d, 0xd9c808c2, 0x483a21f1,
                  0x4e9d5687, 0xa3c64916, 0xa7459ba4, 0x6ff8306e};
  uint32_t *a, *b;
  char plain[33];
  int i;
  assert((binary = fopen("./chall", "rb")) != NULL);
  for (i = 0; i < 4; i++) {
    a = (uint32_t*)(plain + 8 * i + 4);
    b = (uint32_t*)(plain + 8 * i);
    decrypt(x[i * 2 + 1], x[i * 2], a, b);
  }
  fclose(binary);
  plain[32] = '\0';
  printf("flag{%s}\n", plain);
  return 0;
}

flag: flag{0o0..MBA_0bF_1s_S0_1ntEresT1ng!!}

总结

这道题目因为不懂去混淆还是费了很大的力气，最后还是靠加密函数中的异或结构巧妙地重用了已有的二进制代码，还是要提高自己的知识水平，学习去混淆。