狗儿

热爱的话就坚持吧~

0%

控制流平坦化的去除 (rctf2020 play_the_game)

很有趣。

安卓模拟器打开后,发现是五子棋,挺奇怪的,有个问题,flag是以什么样的算法包含在程序里的?

正常的初始化流程走一波,解压apk,拿到jar。

打开jar,第一眼就是这个:

1591456763323

啊,aes?后来才知道没用到aes.

然后发现了三个native层的函数:

1591456828771

本题主要是native层的考察,和java层基本没有关系。

来看一下native层:

随便点了一个函数,发现函数拓扑图是这样的:

1591457037591

伪代码基本上这样的:

1591457107900

因为上学期初我听过FXTI学长的python去除控制流平坦化的这一报告(记得那时我刚进入BXS,完全听不懂学长的报告内容),所以我立即反应过来,这就是**控制流平坦化 **。

学长的成果:

控制流平坦化

控制流平坦化(control flow flattening)的基本思想主要是通过一个主分发器来控制程序基本块的执行流程,例如下图是正常的执行流程

img

经过控制流平坦化后的执行流程就如下图

img

deflat镜像

deflat是去除控制流平坦化的一个脚本,基于angr,详细设计思路可以前往利用符号执行去除控制流平坦化查阅。

由于angr的版本更新,原作者的脚本已经不能用了,有大佬在其原本的基础上进行维护,项目在https://github.com/cq674350529/deflat

由于angr被建议需要python virtual enviroment,所以我直接做了个docker镜像,开箱直用。

同时,原脚本每次运行只能去除一个函数的控制流平坦化,所以我添加了几行代码,使得可以一次处理多个函数的控制流平坦化。

启动容器

1
docker run -v /tmp/dist/:/root/bin --name deflat -it iyzyi/deflat /bin/bash

-v是路径映射,容器的/root/bin映射到宿主机的/tmp/dist,二进制文件放到宿主机的/tmp/dist即可在容器的/root/bin中访问到。

路径映射可以随便改。

使用

原deflat.py

1
python3 deflat.py -f /root/bin/libcalculate.so --addr 0x41FEA0

-f 是需要修改的文件,–addr是要去除控制流平坦化的函数的起始地址。

1591461097462

我修改的deflat.py

1
2
python3 deflat-more.py -f /root/bin/libcalculate.so --addr 0x41FEA0
python3 deflat-more.py -f /root/bin/libcalculate.so --addr 0x4010340 0x401070 0x401090 0x4010d0

允许多个函数的起始地址,以空格为间隔。

因为我修改的版本没有经过深度测试,不知道有没有bug,所以请优先使用原deflat.py.

注意事项

  • 运行deflat.py时,所在路径必须是默认~/deflat/flat_control_flow,因为脚本import了相对路径的am_graph:

1591459061987

  • ida中看到的函数地址是4、5位的,如0x1fea0,但是本脚本运行时提示It is being loaded with a base address of 0x400000.所以函数的起始地址要写0x41fea0

1591459301685

对于本题

1
python3 deflat-more.py -f /root/bin/libcalculate.so --addr 0x4010340 0x401070 0x401090 0x4010d0 0x4010eb 0x401100 0x402b30 0x403810 0x404790 0x4054f0 0x406890 0x4075c0 0x408ad0 0x409130 0x409150 0x409970 0x409d20 0x409f70 0x40a120 0x40a140 0x40ad90 0x40b2c0 0x40b3b0 0x40c210 0x40c960 0x40cf60 0x40d560 0x40da80 0x40e2b0 0x40f1b0 0x40fe30 0x4116a 0x411c60 0x412770 0x413930 0x414dd0 0x415f30 0x4190a0 0x41c570 0x41ca10 0x41e120 0x41fd40 0x41fdc0 0x41fdf0 0x41fea0 0x4201c0

得跑个一个小时左右才能处理完成。

去除了控制流平坦化的函数拓扑图:

1591460012261

逻辑分析:

修复好的so文件中发现了字符串:

1591460097907

所以flag是某个数据的十六进制的md5。但是这个数据是啥呢?

函数一栏里发现了一个函数(__android_log_print),作用是输出log信息,根据交叉引用来到此处:

1591460313298

推测dword_2200C就是这个数据。

Nu1L的题解中说此题就是和电脑下五子棋,每下赢电脑一次,就会更新一次dword_2200C,直到满足某个条件,此时dword_2200C就是flag中的%x这个数据。

按照这个思路的话,那么本题不需要逆向,只需要将计算dword_2200C的代码提取出来,**删掉下棋的相关代码,相当于每大循环一次就是下赢了电脑一次 **,直接正向运行即可,直到满足条件,输出结果。

sub_6890中蕴涵dword_2200C的运算:

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
int sub_6890()
{
int v0; // ebx
unsigned __int8 v1; // ah
int v2; // edx
int v4; // [esp+128h] [ebp-70h]
signed int v5; // [esp+180h] [ebp-18h]

v5 = (signed int)((sqrt((double)(1 - -8 * (dword_22008 - 334816931))) - 1.0) / 2.0 + 1.0);
dword_22008 += v5;
v4 = dword_22008 % 4;
if ( dword_22008 % 4 )
{
if ( v4 == 1 )
{
if ( !((~((unsigned __int8)~(y_11 < 10) | (unsigned __int8)~(((x_10 - 1) * x_10 & 1) == 0)) & 1 | (unsigned __int8)(~(y_11 < 10) ^ ~(((x_10 - 1) * x_10 & 1) == 0))) & 1) )
goto LABEL_20;
while ( 1 )
{
dword_2200C *= v5;
if ( ((unsigned __int8)((y_11 < 10) ^ (((x_10 - 1) * x_10 & 1) == 0)) | (y_11 < 10
&& ((x_10 - 1) * x_10 & 1) == 0)) & 1 )
break;
LABEL_20:
dword_2200C *= v5;
}
}
else
{
while ( !(((unsigned __int8)((y_11 < 10) ^ (((x_10 - 1) * x_10 & 1) == 0)) | (y_11 < 10
&& ((x_10 - 1) * x_10 & 1) == 0)) & 1) )
;
if ( v4 == 2 )
{
if ( !((~((unsigned __int8)~(y_11 < 10) | (unsigned __int8)~(((x_10 - 1) * x_10 & 1) == 0)) & 1 | (unsigned __int8)(~(y_11 < 10) ^ ~(((x_10 - 1) * x_10 & 1) == 0))) & 1) )
goto LABEL_22;
while ( 1 )
{
dword_2200C <<= v5 % 8;
v2 = (x_10 - 43 + 42) * x_10 & 1;
if ( ((unsigned __int8)((y_11 < 10) ^ (v2 == 0)) | (y_11 < 10 && v2 == 0)) & 1 )
break;
LABEL_22:
dword_2200C <<= v5 % 8;
}
}
else if ( v4 == 3 )
{
dword_2200C += dword_22008;
}
while ( !(((unsigned __int8)((y_11 < 10) ^ (((x_10 - 1) * x_10 & 1) == 0)) | (y_11 < 10
&& ((x_10 - 1) * x_10 & 1) == 0)) & 1) )
;
}
while ( !(((unsigned __int8)((y_11 < 10) ^ (((x_10 - 1) * x_10 & 1) == 0)) | (y_11 < 10
&& ((x_10 - 1) * x_10 & 1) == 0)) & 1) )
;
}
else
{
v0 = (x_10 - 81 + 80) * x_10 & 1;
if ( !((~((unsigned __int8)~(y_11 < 10) | (unsigned __int8)~(v0 == 0)) & 1 | (unsigned __int8)(~(y_11 < 10) ^ ~(v0 == 0))) & 1) )
goto LABEL_19;
while ( 1 )
{
dword_2200C = (dword_22008 & 0x99533284 | ~dword_22008 & 0x66ACCD7B) ^ (dword_2200C & 0x99533284 | ~dword_2200C & 0x66ACCD7B);
v1 = ~(((x_10 - 1) * x_10 & 1) == 0);
if ( (~((unsigned __int8)~(y_11 < 10) | v1) & 1 | (unsigned __int8)(~(y_11 < 10) ^ v1)) & 1 )
break;
LABEL_19:
dword_2200C = (dword_22008 & 0x6C814E7D | ~dword_22008 & 0x937EB182) ^ (dword_2200C & 0x6C814E7D | ~dword_2200C & 0x937EB182);
}
}
return 0;
}

删掉下棋相关的代码(while循环就是下棋的判定,我觉得,不太确定),有如下代码:(为了直观地体现删除了哪些代码,我没有用switch-case结构来优化下面的代码的嵌套if)

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
int sub_6890(){
v5 = (signed int)((sqrt((double)(1 - -8 * (dword_22008 - 334816931))) - 1.0) / 2.0 + 1.0);
dword_22008 += v5;
v4 = dword_22008 % 4;
if ( v4 )
{
if ( v4 == 1 )
{
dword_2200C *= v5;
}
else
{
if ( v4 == 2 )
{
dword_2200C <<= v5 % 8;
}
}
else if ( v4 == 3 )
{
dword_2200C += dword_22008;
}
}
else
{
dword_2200C = (dword_22008 & 0x6C814E7D | ~dword_22008 & 0x937EB182) ^ (dword_2200C & 0x6C814E7D | ~dword_2200C & 0x937EB182);
}
return 0;
}

sub_1100函数调用了上面的sub_6890,sub_1100函数代码近五百行,所以不在此处粘贴了。

对于我们求flag来说,该函数的作用主要是使用了一个死循环:

1591463116652

然后循环内部调用了sub_6890。

唯一能跳出的循环的地方是:

1591463893007

此外的其他代码与flag的求解无关,所以不用看。

然后我们把dword_2200C和dword_22008的(已知的)初值写入程序,加上循环:

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
#include <stdio.h>
#include <math.h>

int dword_22008 = 0x13F4E6A3;
int dword_2200C = 0xDEF984B1;

int sub_6890(){
int v4, v5;
v5 = (signed int)((sqrt((double)(1 - -8 * (dword_22008 - 334816931))) - 1.0) / 2.0 + 1.0);
dword_22008 += v5;
v4 = dword_22008 % 4;
if ( v4 )
{
if ( v4 == 1 )
{
dword_2200C *= v5;
}
else
{
if ( v4 == 2 )
{
dword_2200C <<= v5 % 8;
}
else if ( v4 == 3 )
{
dword_2200C += dword_22008;
}
}
}
else
{
dword_2200C = (dword_22008 & 0x6C814E7D | ~dword_22008 & 0x937EB182) ^ (dword_2200C & 0x6C814E7D | ~dword_2200C & 0x937EB182);
}
return 0;
}

int main(){
while (dword_22008 + 2003757756 < 2338579637)
{
sub_6890();
}
printf("%d",dword_2200C);
}

解出dword_2200C为955939368,取十六进制并md5后为flag.

总结

本文主要是记录控制流平坦化的去除,和我做的deflat镜像。

后半部分的算法原理,我还有些不太懂,特别是删掉下棋的代码那部分,以及如何发现的dword_2200C就是flag的%x?