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字节,第二轮输入是第一轮计算产生的v103v105两个值,依次类推,第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、将本轮输入*a1a1[1]经过短暂的处理,变为两个新的32位数v2 = s(*a1)v10 = t(a[1]),再用这两个数计算第三个值v12 = r(v2, v10)

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

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

rstfgh的具体操作未知。

分析

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

IDA的反汇编代码中用到的_DWORDLOWORD__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 ^ yt(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函数的可以通过异或来消去。给定加密结果xy,若取v1'=x^y, v2'=0,则v3'=x^yx'=v1'^f(v3')=x^y^f(x^y)y'=v2'^f(v3')=f(x^y),可以发现新的加密中的y'即原先的加密时f函数的输出,再将y'分别与xy异或,可以求出原先加密时的v1v2

再取a'=0, b'=1,则v1'=C1, v2'=C2,加上上一步解出的v1v2,就可以推出最初的ab。这样就可以在不对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作为模拟的起点,此时r12r13寄存器中分别存放了首轮的输入值。第一轮的结束位于0xF7AD,此时加密结果也存放在r12r13寄存器中。我们同时还需要中途控制v3并检查v1v2的值,因此还需要找到一个中间点,可以选在0x241A,此时r12r13寄存器中分就是v1v2。代码如下:

 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模拟执行代码片段,第一次我们从起点开始,ab分别取10,运行到中间点,根据上面的分析,此时r12=C2, r13=C1,将结果保存为st。第一次我们从中间点开始,v1v2分别取x^y0,运行到终点,根据上面的分析,此时r12=x^y^f(x^y), r13=f(x^y),将结果保存为zw。再通过v1=w^x, v2=w^y继续逆推出v1v2b=v2-C2, a=(v1*n)%0x100000001,其中nC10x100000001的乘法逆元。

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!!}

总结

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