阿里2015第二届安全挑战赛第三题题解

阿里2015第二届安全挑战赛第三题题解
2020-07-06 02:14:04 Author: bbs.pediy.com(查看原文) 阅读量:411 收藏

这里有这题的解答，这位大佬通过分析IDA Trace分析出算法逻辑，然后写出逆向算法，求得答案。实在强大。不过这解法太考验耐性了，我的想法还是尽可能的过掉混淆，还原出代码真实面目，然后分析算法。所以，我的解法就是先去除混淆，然后通过动态分析，定位到关键代码后，再还原算法。

接下来的内容分两部分，反混淆，包括机器代码和ollvm的反混淆和算法分析。

后端反混淆

后端混淆包含一个后端实现的控制流平坦混淆（CFF）和几组隐藏函数调用，无条件跳转，全局变量，常量引用的花指令。

不了解控制流程平坦混淆反混淆的朋友可以先自行研究下ollvm的反混淆。后端实现的CFF反混淆做法和ir实现的是通用的，
我们都需要先获取块编号到真实块地址的映射关系，然后将跳转到分发器的边修改为真实代码的块。

先看下外层CFF混淆。

任意混淆后的函数都有类似下面的入口：

LOAD:0000F72C                 PUSH            {R0,R1,LR}
LOAD:0000F72E                 NOP
LOAD:0000F730                 LDR             R0, =0x52A
LOAD:0000F732                 LDR             R1, switch_dispatcher
LOAD:0000F734
LOAD:0000F734 switch_dispatcher                       ; CODE XREF: LOAD:00011078j
LOAD:0000F734                                         ; LOAD:00012890j ...
LOAD:0000F734                 BL              loc_2A584
LOAD:0000F734 ; ---------------------------------------------------------------------------
LOAD:0000F738 dword_F738      DCD 0x52A               ; LR_init

最后一行跳转，最终走到下面的代码片段

LOAD:00001F4C                 PUSH            {R0,R1}
LOAD:00001F50                 MOV             R1, LR
LOAD:00001F54                 MOV             R1, R1,LSR#1
LOAD:00001F58                 MOV             R0, R0,LSL#2
LOAD:00001F5C                 ADD             R0, R0, #4
LOAD:00001F60                 MOV             R1, R1,LSL#1
LOAD:00001F64                 LDR             R1, [R1,R0]
LOAD:00001F68                 ADD             LR, LR, R1
LOAD:00001F6C                 POP             {R0,R1}
LOAD:00001F70                 LDR             R0, [SP,#arg_8]
LOAD:00001F74                 STR             LR, [SP,#arg_8]
LOAD:00001F78                 MOV             LR, R0
LOAD:00001F7C                 POP             {R0,R1,PC}

为了弄清这个代码片段的作用，我使用miasm进行符号执行

R0 = @32[SP_init]
R1 = @32[SP_init + 0x4]
SP = SP_init + 0xC
LR = @32[SP_init + 0x8]
PC = LR_init + @32[(LR_init & 0xFFFFFFFE) + (R0_init << 0x2) + 0x4]

可以看到，执行该代码片段之后，会恢复R0, R1, LR，平衡栈，并跳转到

PC = LR_init + @32[(LR_init & 0xFFFFFFFE) + 4 + (R0_init << 0x2)]

这其实就是把 LR_init + 4作为跳转表基址， R0为索引的switch-case实现。把

LR_init = 0000F738
R0 = 0x52A

代入，可计算得跳转目标0xF738 + @32[0x10BE4] = 0xF738 + 0x97DC = 0x18F14

LOAD:00018F14                 PUSH            {R4-R7,LR}
LOAD:00018F16                 ADD             R7, SP, #0xC
LOAD:00018F18                 SUB             SP, SP, #0x114
LOAD:00018F1A                 PUSH            {R0,R1,LR}
LOAD:00018F1C                 LDR             R0, =0x5AA
LOAD:00018F1E                 BL              switch_dispatcher
LOAD:00018F22 ; ---------------------------------------------------------------------------
LOAD:00018F22                 NOP
LOAD:00018F22 ; ---------------------------------------------------------------------------
LOAD:00018F24 dword_18F24     DCD 0x5AA               ; DATA XREF: LOAD:00018F1Cr

在这块代码最后，设置R0后又跳转回函数入口。计算0x5AA的目标块地址为0x00019B68

LOAD:00019B68                 MOV             R6, SP
LOAD:00019B6A                 ADDS            R2, R6, #7
LOAD:00019B6C                 ADDS            R2, #0xED
LOAD:00019B6E                 PUSH            {R0,R1,LR}
LOAD:00019B70                 LDR             R0, =0x5AB
LOAD:00019B72                 BL              switch_dispatcher
LOAD:00019B76 ; ---------------------------------------------------------------------------
LOAD:00019B76                 NOP
LOAD:00019B76 ; ---------------------------------------------------------------------------
LOAD:00019B78 dword_19B78     DCD 0x5AB               ; DATA XREF: LOAD:00019B70r

经过上面简单分析，我们知道这个crackme的最外层有如下结构

r0 = 0x52A
while (1) {
    switch (r0) {
        case xxx:
        ...
        case 0x52A:
            ...
            r0 = 0x5AA
            break
        case 0x5AA:
            ...
            r0 = 0x5AB
            break
    }
}

这是个典型的CFF混淆。我们只需要遍历跳转表，将各case最后的跳转指令定向到真实的块，就完成了外层的CFF反混淆。要遍历跳转表，我们还得知道跳转表的大小。
我是通过第一个case的地址计算的

jump_table_start = LR_init + 4
jump_table_end = LR_init + @32[(LR_init & 0xFFFFFFFE) + 0x4 + (0 << 0x2)]     # 第一个case body地址
jump_table_entry_count = (jump_table_end - jump_table_start) / 4
     => (LR_init + @32[(LR_init & 0xFFFFFFFE) + 0x4 + (0 << 0x2)] - (LR_init + 4)) / 4 
     => (@32[(LR_init & 0xFFFFFFFE) + 0x4] - 4)/ 4 
     => (0x16B8 - 4) / 4
     => 0x5AD

即第一个((case的偏移地址 - 4) / 4)就是跳转表大小。
处理完之后，我们尝试在0x0000F72C创建新函数（快捷键p），发现部分代码已经恢复，但是反编译出来的代码还不完整。

发现有如下代码干扰的IDA的分析：

LOAD:000199A0                 STR             R0, [R6,#0x4C] ; case 596
LOAD:000199A2                 SUB             SP, SP, #8
LOAD:000199A4                 PUSH            {R0,R1,LR}
LOAD:000199A6                 NOP
LOAD:000199A8                 BL              sub_2A5A4 ; -> 00001F80

LOAD:00001F80                 MOV             R1, LR
LOAD:00001F84                 MOV             R1, R1,LSR#1
LOAD:00001F88                 MOV             R1, R1,LSL#1
LOAD:00001F8C                 MOV             R0, R1
LOAD:00001F90                 LDR             R1, [R1]
LOAD:00001F94                 ADD             R1, R1, R0
LOAD:00001F98                 LDR             R0, [R1]
LOAD:00001F9C                 STR             R0, [SP,#0x10]
LOAD:00001FA0                 ADD             LR, LR, #4
LOAD:00001FA4                 STR             LR, [SP,#0xC]
LOAD:00001FA8                 POP             {R0,R1,LR}
LOAD:00001FAC                 POP             {PC}

使用miasm辅助分析00001F80

R0 = @32[@32[LR_init & 0xFFFFFFFE] + (LR_init & 0xFFFFFFFE)]
   => @32[@32[0x000199AC] + 0x000199AC]
   => @32[0xFFFFDE68 + 0x000199AC]
   => @32[0x17814]
   => 0x135C6
PC = LR_init + 4

现在可以知道000199A2-000199A8的作用是加载一个常量到R0，然后跳转到LR_init + 4继续执行。
直接使用movw, movt拼接这个常量到r0就可以去除该混淆。清理后的代码：

LOAD:000199A0                 STR             R0, [R6,#0x4C]
LOAD:000199A2                 MOV             R0, #0x135C6
LOAD:000199AA                 NOP
LOAD:000199AC                 NOP
LOAD:000199AE                 NOP
LOAD:000199B0                 NOP
LOAD:000199B2                 ADD             R0, PC  ; _GLOBAL_OFFSET_TABLE_
LOAD:000199B4                 B.W             loc_198E8

crackme里面还有几组类似的混淆，通过前面的CFF反混淆，我们已经知道各case块的起始地址，进而可以计算出case块的大小，遍历case块中的所有指令，使用简单的模式匹配就可以去除所有的后端混淆。

感兴趣的朋友可以自行分析。附件包含我清除后端混淆后的二进制和完整的ida脚本。

后端混淆清理完之后，就可以IDA反编译所有函数了。

反混淆前的代码：

反混淆后的效果：

ollvm反混淆

在IDA中随意反编译一个函数，发现这crackme还有ollvm的混淆等着我们，控制流平坦，指令替换，假分支一个都不少。
网上关于ollvm反混淆的研究已经很多了，相信大家都有自己反混淆方案，或Unicorn，或符号执行。下面简单介绍我使用的方法。

反流程平坦混淆

我之前的方案是使用Binary Ninja进行控制流平坦反混淆，但只支持arm64，而这里的crackme是32位，用不上。
使用IDA的微码进行反流程平坦混淆应该是一种通用的，跟体系无关的方案。我也尝试过使用IDA微码进行反混淆，在经历无数次修改微码IDA崩溃后，我崩溃了，彻底放弃修改微码这条路。
考虑到以后分析虚拟机保护的代码，我觉得还有必要维护自己的一个反编译器，看比较高级控制流结构的伪码总比看汇编效率高，所以决定自己实现反编译器。

这次的控制流平坦的反混淆就是用的我自己的反编译器进行的。反混淆的流程如下

IDA 微码 -> IR -> 在IR进行分析和反混淆 -> 生成类C伪码

之前不好处理的case，现在自己的IR上就很好办了。
如
难以处理case

r0_10是state变量，在BB_0093这个块定义后并没有回到分发器，并且回到分发器（BB_0012）路径上的BB_0095还存在个条件跳转，这种情况应该怎么处理？
BB_0097这个块，r0_10的值有两个，意味着他有两个真实后继，这应该怎么patch？
BB_0096这个块，从这个块流出的r0_10值有5个，有5个真实后继，这种情况又该如何处理？

我的做法是使用指令和代码块复制，把他们转换成下面样子：
处理好之后

经过处理之后，就可以统一的把跳转到BB_0012的指令修改为r0_10对应的代码块了。

当然还是有无法处理的case

这里使用变量对state进行更新。

指令替换

指令替换在我自己的IR上进行，IDA已经帮我做好表达式传播，我只需进行简单的模式匹配就可以对表达式进行化简。如

(x & ~y) | (~x & y) => x ^ y

假分支

我当前实现的反编译器还只具备非常有限的优化能力，为了使用IDA的优化能力，假分支的反混淆是用Binary ninja进行分析和patch，然后把结果导入IDA。
假分支的识别在Binary Ninja MLIL的SSA形式上进行。
如对于下面指令序列,x为全局变量

a = x
b = x - 1
c = a * b
if (c & 1) {
    goto xxx;
} else {
    goto yyy;
}

判断c & 1是否是不透明的谓词的步骤

c & 1 => (a * b) & 1 => (x * b) & 1 => (x * (x - 1)) & 1 => 转换成z3表达式，使用z3判断 (x * (x - 1)) & 1 == 0 或者 (x * (x - 1)) & 1 != 0是否只有一个能成立

附件包含反混淆前后的两个关键，反混淆的效果我还是很满意的，当然还有巨大的改进空间。

之前一些关于这个crackme的分析都是基于IDA trace, 而我则是试水我的内存trace工具，测试他是否能处理现实中程序。
逆向的时候有两个非常常见的需求，找到数据在哪被使用和相关数据的来源。对于这个crackme就是找到我们输入的座位编号在哪被处理，处理过程中用到的数据来源。

为了解决两问题，我实现了自己的内存读写trace工具，这个工具可以记录每条指令对内存读写的地址和内容。

打开附件libcrackme-clean-memory-trace.txt，输入座位号"zzzzzzzzszzzzzzz"，马上定位到关键函数sub_F72C。

0x00017b85(libcrackme.so                 ) r 0xb4b39400  1 z  7a 7a 7a 7a 7a 7a 7a 73 7a 7a 7a 7a 7a 7a 7a 7a zzzzzzzszzzzzzzz

搜索地址0xb4b39400，它有如下引用

0x00011c25(libc.so  strlen + 0024   ) r 0xb4b39400  8 .. 7a 7a 7a 7a 7a 7a 7a 7a 7a 7a 7a 7a 7a 7a 7a 7a zzzzzzzzzzzzzzzz
0x000118d3(libc.so  strcpy + 0002   ) r 0xb4b39400  1 z  7a 7a 7a 7a 7a 7a 7a 7a 7a 7a 7a 7a 7a 7a 7a 7a zzzzzzzzzzzzzzzz
0x00017b85(libcrackme.so                 ) r 0xb4b39400  1 z  7a 7a 7a 7a 7a 7a 7a 73 7a 7a 7a 7a 7a 7a 7a 7a zzzzzzzszzzzzzzz
0x0001877d(libcrackme.so                 ) r 0xb4b39400  1 z  7a 7a 7a 7a 7a 7a 7a 73 7a 7a 7a 7a 7a 7a 7a 7a zzzzzzzszzzzzzzz

打开附件sub_F72C_check-deobfuscated.c，0x0001877d位于一个循环内，循环256次

  while ( 0x1 ) {
    // 对输入进行循环位移 
    anonymous17 = r0_39 { 0x0 }  // 0x00014a38 idx [0 - 255]
    r0_1 = 0x9a7a67fa  // 0x00014a3a
    r2_264 = anonymous24  // 0x00017dec
    @32[(anonymous24 + 0x64)] = anonymous17  // 0x000180c2
    r0_1 = 0xb7d7896c  // 0x00017da8
    r1_24 = 0x119e6fc1  // 0x00017db6
    if ((@32[(r2_264 + 0x64)] > 0xff)) {
      break
    }
    ...

每次循环读取的地址和内容，都可以在trace找到：

0x0001877d(libcrackme.so                 ) r 0xb4b39400  1 z  7a 7a 7a 7a 7a 7a 7a 73 7a 7a 7a 7a 7a 7a 7a 7a zzzzzzzszzzzzzzz
0x0001877d(libcrackme.so                 ) r 0xb4b39401  1 z  7a 7a 7a 7a 7a 7a 7a 73 7a 7a 7a 7a 7a 7a 7a 7a zzzzzzzszzzzzzzz
0x0001877d(libcrackme.so                 ) r 0xb4b39402  1 z  7a 7a 7a 7a 7a 7a 7a 73 7a 7a 7a 7a 7a 7a 7a 7a zzzzzzzszzzzzzzz
0x0001877d(libcrackme.so                 ) r 0xb4b39403  1 z  7a 7a 7a 7a 7a 7a 7a 73 7a 7a 7a 7a 7a 7a 7a 7a zzzzzzzszzzzzzzz
0x0001877d(libcrackme.so                 ) r 0xb4b39404  1 z  7a 7a 7a 7a 7a 7a 7a 73 7a 7a 7a 7a 7a 7a 7a 7a zzzzzzzszzzzzzzz
0x0001877d(libcrackme.so                 ) r 0xb4b39405  1 z  7a 7a 7a 7a 7a 7a 7a 73 7a 7a 7a 7a 7a 7a 7a 7a zzzzzzzszzzzzzzz
0x0001877d(libcrackme.so                 ) r 0xb4b39406  1 z  7a 7a 7a 7a 7a 7a 7a 73 7a 7a 7a 7a 7a 7a 7a 7a zzzzzzzszzzzzzzz
0x0001877d(libcrackme.so                 ) r 0xb4b39407  1 s  7a 7a 7a 7a 7a 7a 7a 73 7a 7a 7a 7a 7a 7a 7a 7a zzzzzzzszzzzzzzz
0x0001877d(libcrackme.so                 ) r 0xb4b39408  1 z  7a 7a 7a 7a 7a 7a 7a 73 7a 7a 7a 7a 7a 7a 7a 7a zzzzzzzszzzzzzzz
0x0001877d(libcrackme.so                 ) r 0xb4b39409  1 z  7a 7a 7a 7a 7a 7a 7a 73 7a 7a 7a 7a 7a 7a 7a 7a zzzzzzzszzzzzzzz
0x0001877d(libcrackme.so                 ) r 0xb4b3940a  1 z  7a 7a 7a 7a 7a 7a 7a 73 7a 7a 7a 7a 7a 7a 7a 7a zzzzzzzszzzzzzzz
0x0001877d(libcrackme.so                 ) r 0xb4b3940b  1 z  7a 7a 7a 7a 7a 7a 7a 73 7a 7a 7a 7a 7a 7a 7a 7a zzzzzzzszzzzzzzz
0x0001877d(libcrackme.so                 ) r 0xb4b3940c  1 z  7a 7a 7a 7a 7a 7a 7a 73 7a 7a 7a 7a 7a 7a 7a 7a zzzzzzzszzzzzzzz
0x0001877d(libcrackme.so                 ) r 0xb4b3940d  1 z  7a 7a 7a 7a 7a 7a 7a 73 7a 7a 7a 7a 7a 7a 7a 7a zzzzzzzszzzzzzzz
0x0001877d(libcrackme.so                 ) r 0xb4b3940e  1 z  7a 7a 7a 7a 7a 7a 7a 73 7a 7a 7a 7a 7a 7a 7a 7a zzzzzzzszzzzzzzz
...

一次迭代对输入的处理过程：

236: anonymous2 = zx.32(@8[(anonymous19 + r0_286)])  // 0x0001877e 用户输入
...
253: anonymous2 = (((anonymous2 << (0x8 - anonymous4)) & (anonymous2 u>> anonymous4)) | ((~(anonymous2 << (0x8 - anonymous4)) ^ 0x6d0d23eb) ^ (~(anonymous2 u>> anonymous4) ^ 0x6d0d23eb)))  // 0x000171e0
···
260: anonymous37 = anonymous2  // 0x000171f4
...
280: @32[(@32[(anonymous24 + 0x4)] + @32[(anonymous24 + 0x64)])] = anonymous37  // 0x00014a28
...

人肉化简anonymous2

anonymous4 = @32[(anonymous24 + 0x64)]  // 0x000188b8 idx
anonymous4 = (anonymous4 %s 0x8)  // 0x00018b14
anonymous2 = (anonymous2 << (0x8 - anonymous4)) | (anonymous2 u>> anonymous4) // a = b | c => a = (b & c) | (b ^ c)

最后在0x00014a28写入结果，首次写入的地址和内容

0x00014a29(libcrackme.so                 ) w 0xbea4aca0  1 z  7a 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 z...............

这个循环对应Python伪码

key = 'zzzzzzzszzzzzzz'
plain_data = []
for idx in range(256):
    c = ord(key[idx % len(key)])
    c = ((c << (0x8 - idx % 0x8)) | (c >> (idx % 8))) & 0xff
    plain_data.append(c)

同样，在trace文件过滤出0xbea4aca0就可以找到对他的处理过程。

0x00010634(libc.so  memset + 0018   ) w 0xbea4aca0 32 .. 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................
0x00014a29(libcrackme.so                 ) w 0xbea4aca0  1 z  7a 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 z...............
0x00014175(libcrackme.so                 ) r 0xbea4aca0  1 z  7a 3d 9e 4f a7 d3 e9 e6 7a 3d 9e 4f a7 d3 e9 f4 z=.O搂脫茅忙z=.O搂脫茅么
0x000117e9(libcrackme.so                 ) w 0xbea4aca0  1 d3 d3 3d 9e 4f a7 d3 e9 e6 7a 3d 9e 4f a7 d3 e9 f4 脫=.O搂脫茅忙z=.O搂脫茅么
0x00012ab5(libcrackme.so                 ) w 0xbea4aca0  1 14 14 3d 9e 4f a7 d3 e9 e6 7a 3d 9e 4f a7 d3 e9 f4 .=.O搂脫茅忙z=.O搂脫茅么
0x00011d75(libcrackme.so                 ) w 0xbea4aca0  1 14 14 3d 9e 4f a7 d3 e9 e6 7a 3d 9e 4f a7 d3 e9 f4 .=.O搂脫茅忙z=.O搂脫茅么

0x00008ad9(libcrackme.so                 ) r 0xbea4aca0  1 14 14 0d 20 0f c3 08 63 bb df 9f 87 e5 ed 81 af 6e .. .脙.c禄脽..氓铆.炉n
0x00008b1d(libcrackme.so                 ) w 0xbea4aca0  1 =  3d 0d 20 0f c3 08 63 bb df 9f 87 e5 ed 81 af 6e =. .脙.c禄脽..氓铆.炉n
0x00008a1b(libcrackme.so                 ) r 0xbea4aca0  1 =  3d 0d 20 0f c3 08 63 bb df 9f 87 e5 ed 81 af 6e =. .脙.c禄脽..氓铆.炉n
0x0000801f(libcrackme.so                 ) w 0xbea4aca0  1 =  3d 0d 20 0f c3 08 63 bb df 9f 87 e5 ed 81 af 6e =. .脙.c禄脽..氓铆.炉n

0x000181e1(libcrackme.so                 ) r 0xbea4aca0  4 .. 3d 48 24 31 ae 24 92 49 f6 6d ba 66 4c 15 a1 a3 =H$1庐$.I枚m潞fL.隆拢
0x000181c1(libcrackme.so                 ) w 0xbea4aca0  4 .. 02 ca 22 ab ae 24 92 49 f6 6d ba 66 4c 15 a1 a3 .脢"芦庐$.I枚m潞fL.隆拢
0x00015ae9(libcrackme.so                 ) r 0xbea4aca0  1 03 02 ca 22 ab 91 a6 94 d3 c9 ef bc fc 73 97 a7 39 .脢"芦.娄.脫脡茂录眉s.搂9
0x0001578d(libcrackme.so                 ) r 0xbea4aca0  1 02 02 ca 22 ab 91 a6 94 d3 c9 ef bc fc 73 97 a7 39 .脢"芦.娄.脫脡茂录眉s.搂9

依次分析对这个地址的写入内容，就可以弄清整个算法处理过程。

这个crackme使用的算法是应该是rc4，sbox使用0xf6f8开始代码构建，使用sbox解密0x2d01c，256字节大小的密文即可得到座位号，与标准rc4差异是，
在跟sbox异或前后多了对数据进行循环位移或者加密的操作。

可以看到，通过内存trace，我们可以很快就定位到关键代码，再结合反混淆后的伪码，这道压轴题已经变成送分题了。

对算法细节有兴趣的朋友可以结合附件trace，伪码里面关键点注释和solve.py，自行分析。

附件内容：

ali-crackme-deobfuscation.py 清理后端混淆ida脚本
solve.py 解答，包含加解密算法
sub_*.c 关键函数，反混淆前后伪码
libcrackme-clean.so 清理后端混淆后的二进制
libcrackme-clean-memory-trace.txt 反混淆后抓的一个内存trace，测试输入"zzzzzzzszzzzzzz"。反混淆前的trace比较巨大，需要请到github仓库下载。
libcrackme-clean-database.idc 在IDA导入该idc后，所有函数都可以正常反编译。

以上内容均可从我的github仓库获取：msc2-crackme3

[看雪官方培训]《安卓高级研修班(网课)》9月班开始招生！挑战极限、工资翻倍！

文章来源: https://bbs.pediy.com/thread-260507.htm
如有侵权请联系:admin#unsafe.sh