看雪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

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

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真好用,感觉可以自己试着写一个污点分析(吗?)的工具。