Reverse

看雪2018 Rev叹息之墙

看雪大佬太强了，菜鸡误入结果一个国庆都飞掉了。。。


看雪2018 Rev叹息之墙

题目之所以叫叹息之墙似乎是因为这个题目在IDA里面看起来是这样的:

太吓人了。。。

分析逻辑

首先执行程序：

输入数字，然后程序内部会对数字进行运算处理，从而检查输入是否正确。不过其中最坑的地方在于不超过9个数字。这样似乎输入的限制就有、、小了。。。

模块分析

逆向第一步自然是分析逻辑。。。但是这个程序这么大，实在是难以分析的样子。不过调试了几下之后发现了几个规律:

  • 程序由跳转模块和执行模块组成
  • 跳转模块中，通过减去一个存放在局部变量的值来决定是否跳转
  • 执行模块中有大量无意义代码块，但是对于有特征的代码段可以识别出其真实作用。并且在最后放入一个跳转魔数，指定下一个跳转的位置。

对于第三点，我们可以看到，程序中大部分的混淆逻辑都是这个样子的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
.text:008C3BE9                 mov     bh, [esi+39Ch]
.text:008C3BEF                 xor     bh, 0FFh
.text:008C3BF2                 mov     [esi+39Bh], al
.text:008C3BF8                 mov     al, dl
.text:008C3BFA                 xor     al, 0
.text:008C3BFC                 mov     [esi+39Ah], al
.text:008C3C02                 mov     al, [esi+39Bh]
.text:008C3C08                 or      al, bh
.text:008C3C0A                 mov     bh, [esi+39Ah]
.text:008C3C10                 or      bh, 0
.text:008C3C13                 xor     al, 0FFh
.text:008C3C15                 and     al, bh
.text:008C3C17                 mov     bh, dl
.text:008C3C19                 xor     bh, 1
.text:008C3C1C                 mov     [esi+399h], al
.text:008C3C22                 mov     al, ah
.text:008C3C24                 xor     al, bh
.text:008C3C26                 and     al, ah
.text:008C3C28                 mov     bh, [esi+39Ch]
.text:008C3C2E                 xor     bh, 0FFh
.text:008C3C31                 mov     [esi+398h], al

还有一种是使用add/sub的混淆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
.text:008C2E4B                 add     eax, ecx
.text:008C2E4D                 add     eax, 0BC19503Ah
.text:008C2E52                 sub     eax, 0B65E8C5Bh
.text:008C2E57                 sub     eax, 0BC19503Ah
.text:008C2E5C                 mov     ecx, ebx
.text:008C2E5E                 sub     ecx, 25A9CB13h
.text:008C2E64                 sub     ecx, 1E9698EBh
.text:008C2E6A                 add     ecx, 25A9CB13h
.text:008C2E70                 mov     [esi+424h], eax
.text:008C2E76                 mov     eax, edi
.text:008C2E78                 mov     [esi+420h], ecx
.text:008C2E7E                 mov     ecx, [esi+424h]
.text:008C2E84                 sub     eax, ecx
.text:008C2E86                 mov     ecx, [esi+420h]
.text:008C2E8C                 sub     ecx, eax
.text:008C2E8E                 sub     edi, 1E9698EBh
.text:008C2E94                 sub     ecx, edi

这两种运算本质上并没有做什么有意义的事情，但是如果出现strlen,__aullrem这类函数的话，很有可能就是一个重要的内容，于是这边用idapython标记了一下当前的程序中用到这些函数的地方:

1
2
3
4
5
6
7
8
9
10
11
from idaapi import *
print "================="
danger_func = ["_strlen","_strcmp"]
for func in danger_func:
    addr = LocByName(func)                           
    if addr != BADADDR:
        cross_refs = CodeRefsTo(addr, 0)
        for ref in cross_refs:
            print "%08x" % ref
            SetColor(ref, CIC_ITEM, 0x0000ff)

顺着这几个地方，找到了输入进行处理的逻辑

输入流追踪

1
2
3
4
5
6
7
8
.text:008EE9CA                 lea     eax, aXD        ;"x%d"
.text:008EE9D0                 lea     ecx, a0x1x23x45x67 ; ""
.text:008EE9D6                 xor     edx, edx
.text:008EE9D8                 mov     edi, 400h
.text:008EE9DD                 mov     ebx, [esi+302Ch]
.text:008EE9E3                 mov     ebx, [ebx]
.text:008EE9E5                 mov     ebx, GlobalIndex[ebx*4]
.text:008EE9EC                 sub     esp, 4

这里出现了第一个全局变量GlobalIndex，这个变量会将通过了程序验证的数字存放在这个整数数组中。r顺着这个变量，找到了第二个全局变量

1
2
3
4
5
6
7
8
9
10
11
12
13
.text:0090C195 loc_90C195:                             ; CODE XREF: sub_8C9FF0+1299↑j
.text:0090C195                 mov     eax, [esi+302Ch] ; 这个位置存放的是index
.text:0090C19B                 mov     eax, [eax]
.text:0090C19D                 mov     eax, GlobalIndex[eax*4] 
.text:0090C1A4                 mov     eax, TargetMagic[eax*4] 
.text:0090C1AB                 mov     ecx, [esi+3024h]
.text:0090C1B1                 mov     edx, [ecx]
.text:0090C1B3                 mov     ecx, [ecx+4]
.text:0090C1B6                 add     edx, eax        
.text:0090C1B8                 adc     ecx, 0
.text:0090C1BB                 mov     eax, [esi+3024h]
.text:0090C1C1                 mov     [eax], edx
.text:0090C1C3                 mov     [eax+4], ecx

吐槽一下，这个变量其实有好几个地方都有引用，但是似乎不是所有的地方都执行了一遍。。。
这个TargetMagic是一个存放了351个整数的变量。观察上面的这段逻辑，我做出一个猜测：这个地方可能在操作一个64bit的数字，因为这个地方用了adc汇编（好像没有啥道理？只是直觉）
整体的逻辑大概是这样的:

1
2
3
4
5
int GlobalIndex[];
long long sum = 0;
for(i = 0; i < length(GlobalIndex); i++){
	sum += TargetMagic[GlobalIndex[i]];
}

大概就猜测到这个地方，好像就没有思路了。。。于是我们检查一下有没有什么可疑的字符串:

1
2
3
4
5
6
7
8
.rdata:00958218 asc_958218      db '格式错误',0Ah,0         ; DATA XREF: sub_8C9FF0:loc_8F7DB2↑o
.rdata:00958218                                         ; sub_8C9FF0:loc_8F922E↑o ...
.rdata:00958222 asc_958222      db '输入错误',0Ah,0         ; DATA XREF: sub_8C9FF0:loc_90EC31↑o
.rdata:00958222                                         ; sub_8C9FF0:loc_91BBD5↑o
.rdata:0095822C a3E             db '输入正确',0Ah           ; DATA XREF: sub_8C9FF0:loc_90F13D↑o
.rdata:0095822C                 db '赶快去报看雪，前3名有奖励哦;-)',0Ah
.rdata:0095822C                 db '看雪祝你国庆快乐！',0Ah
.rdata:0095822C                 db 0Ah,0

找到这个地方又有了新的线索：这一段显然是用于判断输入逻辑的，不过我们发现跟踪进去并不方便，因为这个程序本身被切分成了跳转模块和执行模块，这个跳转模块和执行模块之间的关系还特别复杂，存在很多用于混淆视听的需要跳转模块。。所以我这里决定用IDAPython再次辅助检查程序。通过使用idapython找到当前模块中的跳转和入口的对应关系，然后进行程序流的逆向追踪，然后大致就写了一个忙放辅助的脚本

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
#!python
import idc
print "====[+]===="
def find_target_jmp(begin_addr, end_addr):
    #addr = idc.NextHead(addr)
    #if idc.GetDisasm(addr) == "mov"
    addr = begin_addr
    target_addrs = []
    while addr != end_addr:
        second_type = idc.get_operand_type(addr, 1)
        op = GetMnem(addr)
        disas = idc.GetDisasm(addr)
        Op_2_type = GetOpType(addr, 1)
        Opnd_1 = idc.GetOpnd(addr, 0)
        # print(Opnd_1)
        #op_num
        if "mov" == op and Opnd_1 == "dword ptr [esi+301Ch]" and o_imm == Op_2_type:
            # addr_str = "addr:%x, %s"%(addr,disas)
            magic_number = idc.GetOperandValue(addr, 1)
            # print("addr:%x, %s"%(addr,disas))
            target_addrs.append(magic_number)

        addr = idc.NextHead(addr)
    return target_addrs

def jmp_real_target(begin_addr, end_addr):
    addr = begin_addr
    target_addrs = {}
    while addr != end_addr:
        # print('[+]')
        op = GetMnem(addr)
        Opnd_1 = idc.GetOpnd(addr, 0)
        Opnd_2 = idc.GetOperandValue(addr, 1)
        # print(Opnd_2)
        if "sub" == op and (Opnd_1 == "ecx" or Opnd_1 == "eax"):
            # mov to jz 
            target_addrs[Opnd_2] = ""
            while idc.GetMnem(addr) != "jz":
                addr = idc.NextHead(addr)

            disas = idc.GetDisasm(addr)
            # print("addr:%x, %s"%(addr, disas))
            # print(hex(idc.GetOperandValue(addr, 0)))
            target_addrs[Opnd_2] = idc.GetOperandValue(addr, 0)

        addr = idc.NextHead(addr)
    return target_addrs

emmmm…里面也有一些变量命名有点奇怪。。不过最后还是成功的找到了几个关键的调试逻辑

核心判断逻辑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
.text:0090D170                 mov     eax, [esi+3024h]
.text:0090D176                 mov     ecx, [eax]
.text:0090D178                 mov     eax, [eax+4]
.text:0090D17B                 xor     edx, edx
.text:0090D17D                 mov     edi, SRC
.text:0090D183                 sub     esp, 10h
.text:0090D186                 mov     ebx, esp
.text:0090D188                 mov     [ebx+0Ch], eax
.text:0090D18B                 mov     [ebx+8], ecx
.text:0090D18E                 mov     [ebx+4], edx
.text:0090D191                 mov     [ebx], edi
.text:0090D193                 call    GroupMul
.text:0090D198
.text:0090D198 loc_90D198:
.text:0090D198                 add     esp, 10h
.text:0090D19B                 mov     ecx, 0B571D678h
.text:0090D1A0                 mov     edx, 0E7210A91h
.text:0090D1A5                 mov     bl, 1
.text:0090D1A7                 xor     edi, edi
.text:0090D1A9                 cmp     eax, DST
.text:0090D1AF                 setnz   bh
.text:0090D1B2                 and     bh, 1

通过脚本分析可以发现，这个地方的逻辑会最终影响是否跳转到“成功”逻辑上，因此这个地方显然是一个关键的函数逻辑，其中这个SRC和DST分别对应字符串eux2和nak4。不过这个地方其本身是作为一个整数存在的。这段逻辑翻译一下的话就是:

1
2
3
4
5
6
int num = GroupMul(sum, SRC);
if(num == DST){
	//跳转正确
}else{
	//输入错误
}

于是现在的关键变成了这个GroupMul函数。我们跟踪进去，会发现两个关键的比较逻辑：

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
.text:008C5685                 mov     eax, [esi+5B0h] ; sum
.text:008C568B                 mov     ecx, [eax]
.text:008C568D                 mov     eax, [eax+4]
.text:008C5690                 mov     edx, eax
.text:008C5692                 shld    edx, ecx, 1Fh   
.text:008C5696                 shr     eax, 1
.text:008C5698                 mov     ecx, [esi+5B0h]
.text:008C569E                 mov     [ecx+4], eax    
.text:008C56A1                 mov     [ecx], edx     ;对64bit整数 sum 进行位移
.text:008C56A3                 mov     eax, [esi+5B4h]
.text:008C56A9                 mov     ecx, [eax]
.text:008C56AB                 mov     eax, [eax+4]
.text:008C56AE                 mov     edx, [esi+5B4h]
.text:008C56B4                 mov     edi, [edx]
.text:008C56B6                 mov     edx, [edx+4]
.text:008C56B9                 mov     ebx, ecx
.text:008C56BB                 imul    ebx, edx        
.text:008C56BE                 mov     [esi+26Ch], eax
.text:008C56C4                 mov     eax, ecx
.text:008C56C6                 mul     edi
.text:008C56C8                 add     edx, ebx        
.text:008C56CA                 mov     ecx, [esi+26Ch]
.text:008C56D0                 imul    ecx, edi
.text:008C56D3                 add     edx, ecx
.text:008C56D5                 sub     esp, 10h
.text:008C56D8                 mov     ecx, esp
.text:008C56DA                 mov     [ecx], eax
.text:008C56DC                 mov     [ecx+4], edx
.text:008C56DF                 mov     dword ptr [ecx+0Ch], 0
.text:008C56E6                 mov     dword ptr [ecx+8], 0FFA1CF8Fh
.text:008C56ED                 call    __aullrem       ; 求余数
.text:008C56F2                 mov     ecx, [esi+5B4h]
.text:008C56F8                 mov     [ecx+4], edx
.text:008C56FB                 mov     [ecx], eax

这个关键逻辑处，会将当前我们传入的sum处理，之后会处理SRC变量，翻译一下就是:

1
2
sum >>= 1;
SRC = (SRC*SRC)%0xFFA1CF8F

然后是第二段

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
.text:008C561C                 mov     eax, [esi+5B8h] 
.text:008C5622                 mov     ecx, [eax]
.text:008C5624                 mov     eax, [eax+4]
.text:008C5627                 mov     edx, [esi+5B4h]
.text:008C562D                 mov     edi, [edx]
.text:008C562F                 mov     edx, [edx+4]
.text:008C5632                 mov     ebx, ecx
.text:008C5634                 imul    ebx, edx
.text:008C5637                 mov     [esi+270h], eax
.text:008C563D                 mov     eax, ecx
.text:008C563F                 mul     edi             
.text:008C5641                 add     edx, ebx
.text:008C5643                 mov     ecx, [esi+270h]
.text:008C5649                 imul    ecx, edi
.text:008C564C                 add     edx, ecx
.text:008C564E                 sub     esp, 10h
.text:008C5651                 mov     ecx, esp
.text:008C5653                 mov     [ecx], eax
.text:008C5655                 mov     [ecx+4], edx
.text:008C5658                 mov     dword ptr [ecx+0Ch], 0
.text:008C565F                 mov     dword ptr [ecx+8], 0FFA1CF8Fh
.text:008C5666                 call    __aullrem
.text:008C566B                 mov     ecx, [esi+5B8h]
.text:008C5671                 mov     [ecx+4], edx
.text:008C5674                 mov     [ecx], eax

这一段则是处理关键的返回值的。

将上面两段汇编合并一下，就能够得到一个这样的函数:

1
2
3
4
5
6
while(sum != 0){
	if(???)
		A = (A * SRC)%0xFFA1CF8F
	sum>>=1;
	SRC = (SRC**2)%0xFFA1CF8F
}

调试中发现，第二段判断逻辑似乎不是每一次都会进入的，于是必然是有一个判断的逻辑在。顺着跳转的魔数返回寻找，能够找到这样的两段:

1
2
3
4
5
6
7
8
9
10
11
12
.text:008C42D6                 and     edi, ecx
.text:008C42D8                 sub     edi, 0FFFFFFFFh
.text:008C42DB                 setnz   dh
.text:008C42DE                 and     dh, 1
.text:008C42E1                 mov     [esi+5BFh], dh
....
.text:008C55FB                 mov     eax, 38482BE4h
.text:008C5600                 mov     ecx, 0D99D9385h
.text:008C5605                 mov     dl, [esi+5BFh]  ; 这个地方影响跳转
.text:008C560B                 test    dl, 1
.text:008C560E                 cmovnz  eax, ecx
.text:008C5611                 mov     [esi+5A8h], eax

这两段代码正好决定了此时的程序会不会进入第二段影响返回值（这里设为A）的判断逻辑。通过调试发现，这里是在检查sum的最低位是否为1。那么此时整个判断逻辑就能够重现了:

1
2
3
4
5
6
while(sum != 0){
	if(sum&0x1)
		A = (A * SRC)%0xFFA1CF8F
	sum>>=1;
	SRC = (SRC**2)%0xFFA1CF8F
}

整体逻辑

至此，整个程序逻辑大概为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int list = read_cont();//这里还有输入格式检错

int GlobalIndex[] = ConvertToNum(list);
long long sum = 0;
for(i = 0; i < length(GlobalIndex); i++){
	sum += TargetMagic[GlobalIndex[i]];
}
while(sum != 0){
	if(sum&0x1)
		A = (A * SRC)%0xFFA1CF8F;
	sum>>=1;
	SRC = (SRC**2)%0xFFA1CF8F;
}
if (A == DST){
	//程序正确
}else{
	//输入错误
}

数据处理

有了整体逻辑，那么此时我们的目标就很明确了：

  • 通过选择TargetMagic中的数字，影响sum的值，从而影响跳转
  • 通过在合适的位置跳转，让A的值能够与DST相等

逻辑化简

如果仔细思考上述逻辑的话，会发现其实这个运算过程就是SRC的sum次方模0xFFA1CF8F，于是还能进一步化简为:

1
A = (SRC ** sum)%0xFFA1CF8F

这个时候，SRC的运算相当于是一个群

因此我们第一个目标就很明确了

  • 找到 SRC 的幂次 sum ，满足(SRC**sum)%0xFFA1CF8F == DST

于是尝试爆破:

1
2
3
4
5
6
7
8
9
10
11
for (i = 0; i < 0x900000000; i++) {
	num = (num * src)% 0xFFA1CF8F;

	if (num == dst) {
		printf("find answer!%lld\n", i+1);
		// break;
	}
	if (i % 0x10000000 == 0) {
		puts("[+]waiting.....");
	}
}

这里考虑到，TargetMagic中的数字最大也为0xfeb053fc，若9次都取到这个数字也不会超过0x900000000，所以这里爆破次数仅为
[0,0x900000000]
然后能够得到这几个数字:

1
[0x55121c15,0x154b3eba3,0x25455bb31,0x353f78abf,0x453995a4d,0x5533b29db,0x652dcf969,0x7527ec8f7,0x852209885]

TargetMagic的规律

不过之后就很麻烦了，如果要从这么多的数字里面找到几个数字，相加正好又是我们目标值中的其中一个，实在是太复杂了。瞎摆弄的时候，突然发现如下规律

1
['0xf17b92', '0x1e2f724', '0x2d472b6', '0x3c5ee48'....

无意中对数组进行了排序（原先目的忘记了），突然发现第一个数字是后几个数字的倍数，于是想到

会不会是整个数组都是由这个数字生成的呢？

于是试着找了一下，总共有270个数字是由其生成的。发现这个思路可行，于是写了个脚本，找到了其中所有的生成元:

1
2
3
4
5
6
7
8
9
10
tom =[0]*9
tom[0] = 0xf17b92   # 270
tom[1] = 0x83f06b2  # 30
tom[2] = 0xf0984ae  # 16
tom[3] = 0x13a9fc46 # 12
tom[4] = 0x173d416a # 10
tom[5] = 0x2484d482 # 6
tom[6] = 0x33205cb6 # 4
tom[7] = 0x5535efda # 2
tom[8] = 0x7fd0e7c7 # 1

于是这个题目突然之间转变成了如下的形式

将这几个数字设为变量a,b,c,d…然后进行一个多项式求解，等式的右边就是之前爆破出来的幂次。哪一个幂次能找到合适的解，就利用这个解反推出我们选取的TargetMagic

于是这里使用Z3进行计算:

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
#   -*- coding:utf-8    -*-
from z3 import *
import copy
ans = [Int('x'), Int('y'), Int('z'),Int('a'), Int('b'), Int('c'),Int('d'), Int('e'), Int('f')]

def gen_solver():
    solver = Solver()

    solver.add(ans[0]>=0)
    solver.add(ans[0]<=270)
    solver.add(ans[1]>=0)
    solver.add(ans[1]<=30)
    solver.add(ans[2]>=0)
    solver.add(ans[2]<=16)

    solver.add(ans[3]>=0)
    solver.add(ans[3]<=12)
    solver.add(ans[4]>=0)
    solver.add(ans[4]<=10)
    solver.add(ans[5]>=0)
    solver.add(ans[5]<=6)

    solver.add(ans[6]>=0)
    solver.add(ans[6]<=4)
    solver.add(ans[7]>=0)
    solver.add(ans[7]<=2)
    solver.add(ans[8]>=0)
    solver.add(ans[8]<=1)

    return solver

i = [0x55121c15,0x154b3eba3,0x25455bb31,0x353f78abf,0x453995a4d,0x5533b29db,0x652dcf969,0x7527ec8f7,0x852209885]
toms = [15825810, 138348210, 252282030, 329907270, 389890410, 612684930, 857758902, 1429598170, 2144397255]
for each in i:
    if pow(1702197298, each, 0xFFA1CF8F) != 1851878196:
        print("wrong!")

for each in i:
    solver = gen_solver()
    solver.add(ans[0] * toms[0] + 
               ans[1] * toms[1] +
               ans[2] * toms[2] +
               ans[3] * toms[3] + 
               ans[4] * toms[4] +
               ans[5] * toms[5] + 
               ans[6] * toms[6] + 
               ans[7] * toms[7] +
               ans[8] * toms[8] == each)

    if solver.check() == sat:
        print("find")
        print(each)
        m = solver.model()
        s = []
        for i in range(len(ans)):
            print "%d,"%(m[ans[i]].as_long() * toms[i]),

之后能够发现，在幂次为0x453995a4d的时候，能够得到一个解：

1
1171109940, 553392840, 3027384360, 3958887240, 1559561640, 2450739720, 857758902, 2859196340, 2144397255

我们找到其中每一个下标，最后翻出其位置并且排序（题目要求），就能够得到最终的答案:

完结撒花！

总结

  1. 该利用工具的时候要学会用工具。一开始打算硬看，发现实在是没有办法把跳转之间的关系理清楚，最后用了ipapython虽然没有起到关键的作用，但是辅助了整个分析流程，让思路清晰了很多
  2. 思路中途打结过几次，冷静休息一下反而能够帮助思路的进行
  3. 这个题目似乎用了ollvm进行的混淆，其实本来手头上有一个工具可以试着反混淆但是没有尝试，果然还是应该多学一些东西。
  4. idapython真好用，感觉可以自己试着写一个污点分析（吗？）的工具。