2019 0CTF/TCTF Quals

标签:算法, VM

0ctf/Tctf线下打完了,这次以Aurora的身份打新星赛。最终第16没能进入决赛。不过还是学到终极多东西。

这次题目挺不错的,一道数学题一道算法题一道逆向题,从简到难。

element有点送分的感觉,就是感觉自己数学水平退步了,明明有很简单很简单的做法,却解个方程解半天,真是不如高中的时候啦。

sanitize真的体会到自己算法的薄弱,最终用了个很蠢很蠢的方法做出来的,有点小丢人。

sixology这题挺厉害,出题人真厉害。这题全场也就两解。希望下次遇到这种难题时能够有头绪,而不是直接放弃

比赛时间:2019年3月23日14:00——2019年3月25日14:00

题目下载:下载地址

Element

这题流程十分简单,先check格式,一共44位,flag{12位十六进制数a-12位十六进制数b-12位十六进制数c}

之后字符串转整数,以及给出了a = 0x391BC2164F0A

接下来有一段不太常见的汇编指令punpckldq subpd pshufd addpd,查找资料发现应该是整数转浮点。

然后就是一堆数学算式的check。题目意思是:

  • 已知三角形最短边a,内切圆半径r,外接圆半径R,求剩余两边b和c。

就难度来说只是高中数学的难度,列出两条方程求解。至于求解的方法,可以用z3,fsolve,Mathematical等等,甚至可以用一些高级计算器手动输方程求解。

至于精度其实没必要考虑的太多,因为上述工具解出来的结果基本正确,跟正确值的差距在1-2左右。可以自己写个脚本,把题目中的计算过程抄一遍看最后R和r的误差,在b和c左右两边浮动一两位,找到误差最低的那个值就是了。

Sanitize

这是道算法题,但是我也没搞清它的算法23333,因为我是爆破出的结果。

这道题比较特殊,不像常规的加密解密题有个常量对比,这题没有一个常量可以比较,因此不能直接爆破,而且长度很长,所以得用一些骚方法爆。这里分享一下我的爆破解题的思路。

程序流程

  1. 从同目录下的flag文件读取flag字符串。
  2. 输入一个字符串s,长度大于3小于32。
  3. 输入一个整数n,接下来的n行,每行接受一个整数输入,存入数组num。所有的num对flag长度取模,且不能重复。
  4. 接下来会新建一张类似图的数据结构,依次向图里面添加结点。结点的结构:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
00000000 node            struc ; (sizeof=0x20, mappedto_6)
00000000 ch              db ? ; 该节点存放的字符
00000001                 db ? ; undefined 没用
00000002                 db ? ; undefined 没用
00000003                 db ? ; undefined 没用
00000004 d               dd ? ; 我也不清楚有啥用,大概跟变形有关
00000008 p0              dq ? ; 指向一个结点                  
00000010 p1              dq ? ; 指向一个结点                 
00000018 p2              dq ? ; 指向一个结点                 
00000020 node            ends

添加结点分为两步:

(1).在一个恰当的位置插入新的结点,一般是根结点或根节点的下一个结点。

(2).根据每个节点数据的大小,对这张图进行修改与平衡

这里其实比较像红黑树或二叉平衡树,总之这张图一直都是在变化的。

重点:添加结点/修改形状的过程中必然有许多if else分支,在6030B8记录进入每个分支的次数(关键,以此来计算/爆破flag),以及某些函数的调用次数(这里其实用处不大,一般都跟字符串s的长度或输入整数的数目n有关,对flag的内容没啥关系)

添加结点的顺序:先将输入的字符串按顺序依次添加,再按照num数组的内容,找到对应的flag字符添加。比如输入了 3 2 0 1,则依次添加'a','f','l'这三个字符

main函数结束后,进入函数sub_401980,将6030B8开始的每个字节输出。(这里的指针qword_603230确实是指向6030B8的,在程序最开头有定义)

解法

理清整个流程,思考解题的方法:

分析清题目的算法,根据每个分支的不同计算出flag。

然而我个人水平有限,在分析算法过程中耗费太多时间,也没有分析出个所以然,只能摸清个大概。

常规方法走不通,想想其他方法。

思考:每次加入结点的顺序都相同,只有最后一个(或其中某一个)加入的结点不同,返回给我们的表应该是不同的。我们可以选一段字符串输入,然后再依次加入结点'f','l',以及一个不同的字符结点,看看输出的内容有何变化。

先打本地找找规律。

 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
from __future__ import print_function
from pwn import *  
from time import *
context.log_level = 'error'
seed = int(time())
def rand():
    global seed
    seed = seed * 0x343FD + 0x269EC3
    return (seed >> 16) & 0x7FFF  

flag = 'flag{'
payload = ''
for j in range(5):
    payload += chr((rand()%(0x7f-0x20))+0x20)#随机生成一段字符串,测试下来发现长度为5时变化比较大

for i in range(0x20,0x7f):
    f = open('flag','w+')
    f.write(flag+chr(i)+'a'*20)  #第六位为测试的字符,每轮写入不同的字符
    f.close()

    payload += '\n'
    payload+=str(3)+'\n'+str(0)+'\n'+str(1)+'\n'+str(5)+'\n'
    p = process('./sanitize')
    p.send(payload)
    s = p.recv()
    p.close()

#对接受到的数据稍微处理一下输出。大部分都是根字符串s的长度/整数数量n有关,或是不变的1或0,比较有用的就38,39,42
    t=[]
    tt = []
    for j in range(len(s)/8):
        t.append(s[j*8:j*8+8])
    # print(t)
    for j in range(len(t)):
        temp = 0
        for k in range(4):
            temp+=int(t[j][2*k:2*k+2],16)*(256**k)
        tt.append(temp)
    print('%4d'%tt[38],end = '')
    print('%4d'%tt[39],end = '')
    print('%4d'%tt[42],end = ' ')
    print(chr(i))

部分输出如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
xd}zg          #payload字符串内容
...前面都一样...
   2   5   5 c
   2   5   5 d←分界点1
   1   6   6 e
   1   6   6 f←分界点2
   0   7   7 g
   0   7   7 h
   0   7   7 i
   0   7   7 j
   0   7   7 k←分界点3
   1   6   6 l
   1   6   6 m
   1   6   6 n
   1   6   6 o
   1   6   6 p
   1   6   6 q
   1   6   6 r
...后面都一样...

上面这个例子可以发现,在这种payload(随机生成的)的情况下当第六位字符小于f或者g到k或者大于l,会有三种不同的输出,这样我们就有了三个区间,来区分三个区间内的字符了。

由于构造的payload不一样,分界点也不同,因此理论上可以构造出(0x7f-0x20)种不同的payload组合,就能鉴定每一个字符了。

由于不懂原理,因此只能粗暴的使用随机数构造字符串,尝试找到不同的payload能够区分每一个字符。

于是有了下面一段代码:

 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
from pwn import *  
from time import *
context.log_level = 'error'

seed = int(time())
def rand():
    global seed
    seed = seed * 0x343FD + 0x269EC3
    return (seed >> 16) & 0x7FFF  
flag = 'flag{'
check0 = []
compare = []

g = open('payload','w')
h = open('check','w')
for i in range(0x20,0x7e):
    while(True):
        f = open('flag','w+')
        f.write(flag+chr(i)+'a'*20)
        f.close()
        payload = ''
        for j in range(5):
            payload += chr((rand()%(0x7f-0x20))+0x20)
        payload += '\n'
        payload+=str(3)+'\n'+str(5)+'\n'+str(1)+'\n'+str(0)+'\n'
        p = process('./sanitize')
        p.send(payload)
        s = p.recv()
        p.close()

        f = open('flag','w+')
        f.write(flag+chr(i+1)+'a'*20)
        f.close()

        p = process('./sanitize')
        p.send(payload)
        r = p.recv()
        p.close()

        if s!=r:#第五位为i和i+1时,返回的结果不同
            g.write(payload)
            h.write(s)
            check0.append(s)
            print(chr(i))
            break
g.close()
h.close()

这样我们得到了一组payload,他能区分从0x20到0x7f的每一位,使这一位和下一位返回的数据不同,返回的数据保存在check内。

这样理论上我们就能够区分每一个不同的字符了。尝试写爆破脚本:

 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
from __future__ import print_function
from pwn import *  
from time import *
context.log_level = 'error'
flag = 'flag{this_is_a_testing_flag_TESTING_0123456P)+_)!@#":}'
f = open('flag','w+')
f.write(flag)
f.close()
payloads = []
check = []
g = open('payload','r')
h = open('check','r')
for i in range(0x7f-0x20):
    s = g.read(14)
    payloads.append(s)
    s = h.read(657)
    check.append(s)

for i in range(5,0x7f):
    for j in range(0x20,0x7f):
        payload = payloads[j-0x20][0:8]+str(i)+payloads[j-0x20][9:]
        p = process('./sanitize')
        p.send(payload)
        s = p.recv()
        p.close()

        payload = payloads[j-0x20+1][0:8]+str(i)+payloads[j-0x20+1][9:]
        p = process('./sanitize')
        p.send(payload)
        r = p.recv()
        p.close()

        if s!= check[j-0x20] and r == check[j-0x20+1]:#这一个字符的payload返回数据相同,下一位不同,它有可能是此字符。
            print(chr(j+1),end = '')
            break

输出:

1
"!!""!""""""""!"!"!""!"""""""""&&&&&&&")+")!"#"&"

仔细分析:

我们有了对应的payload和check,假设第五位是't',它肯定能通过t的那一个check,但也通过了双引号"的check,才会有上面这种情况。也就是说我们拿到了一个必要不充分的条件。

另一方面想,对于不同的字符,能通过的check应当是不同的。

测试一下:

 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
from __future__ import print_function
from pwn import *  
from time import *
context.log_level = 'error'

payloads = []
check = []
g = open('payload','r')
h = open('check','r')
for i in range(0x7f-0x20):
    s = g.read(14)
    payloads.append(s)
    s = h.read(657)
    check.append(s)
g.close()
h.close()
check1 = []


for i in range(0x7f-0x20):
    check1.append('')
print(check1)

print('flag{')
for ii in  range(0x20,0x7f):
    f = open('flag','w+')
    f.write('flag{'+chr(ii))
    f.close()
    print(chr(ii),end=' ')
    t = open('check2','a')
    for i in range(0x20,0x7f-2):
        payload = payloads[i-0x20][0:8]+str(5)+payloads[i-0x20][9:]
        p = process('./sanitize')
        p.send(payload)
        s = p.recv()
        p.close()
        payload = payloads[i-0x20+1][0:8]+str(5)+payloads[i-0x20+1][9:]
        p = process('./sanitize')
        p.send(payload)
        r = p.recv()
        p.close()

        if s!= check[i-0x20] and r == check[i-0x20+1]:
            t.write(chr(i+1))
            print(chr(i+1),end = '')
    t.write('\n') 
    t.close()       
    print('')

部分输出

1
2
3
4
5
6
7
8
p "%(,/259>ADHQp
q "%(,/259>ADHQq
r "%(,/2579>ADHQr
s "%(,/2579>ADHQs
t "%(,/2579>ADHQt
u "%(,/2579>ADHQu
v "%(,/2579>ADHQv
w "%(,/2579>ADHQw

可以看到,对于字符't',它确实通过了t的check,但同时也通过了对其他一些字符的check。

同时可以发现,左边的字符和右边的字符串是一一对应的(或许会有重复,但一般就两到三个重复)。

有了一一对应的关系,就能爆破出flag了

 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
from __future__ import print_function
from pwn import *  
from time import *
context.log_level = 'error'
flag = 'flag{this_is_a_testing_flag_TESTING_0123456P)+_)!@#":}'
f = open('flag','w+')
f.write(flag)
f.close()
payloads = []
check = []
check2 = []
result = []
g = open('payload','r')
h = open('check','r')
t = open('check2','r')
for i in range(0x7f-0x20):
    s = g.read(14)
    payloads.append(s)
    s = h.read(657)
    check.append(s)
    s = t.readline()
    check2.append(s[0:-1])
    result.append('')
flag = 'flag{'
for i in range(5,0x7f):
    for j in range(0x20,0x7f-2):
        payload = payloads[j-0x20][0:8]+str(i)+payloads[j-0x20][9:]
        # p = process('./sanitize')
        # p = remote("111.186.63.16",20193)
        p.send(payload)
        s = p.recv()
        p.close()
        payload = payloads[j-0x20+1][0:8]+str(i)+payloads[j-0x20+1][9:]
        p = process('./sanitize')
        # p = remote("111.186.63.16",20193)
        p.send(payload)
        r = p.recv()
        p.close()

        if s!= check[j-0x20] and r == check[j-0x20+1]:
            print(chr(j+1),end = '')
            result[i-5]+=(chr(j+1))
    print('')
    flag+=chr(check2.index(result[i-5])+0x20)
    print(flag)

部分输出:

1
2
3
4
5
6
flag{this_is_a_testing_flag_TESTING_0123456P)+)!
flag{this_is_a_testing_flag_TESTING_0123456P)+)!@
flag{this_is_a_testing_flag_TESTING_0123456P)+)!@#
flag{this_is_a_testing_flag_TESTING_0123456P)+)!@#"
flag{this_is_a_testing_flag_TESTING_0123456P)+)!@#":
flag{this_is_a_testing_flag_TESTING_0123456P)+_)!@#":}

本地能打远程也能打,不过速度比本地慢,五分钟内应该能爆完= =

总感觉我的方法有些取巧,这题还有很多地方没搞懂,期待官方writeup以及各位大佬的讲解。

sixology

弘扬中华文化,文体两开花

题目拿到手,一个dll和一个。

binary直接用ida打开只是binary,没任何用。

一开始连这题是干嘛的都不知道,对着dll看了好久也没看出啥来。

不过如果细心点,还是能找到线索的。

先搜字符串,看到一堆666,跟着引用走,最后看到一个叫LPH的结构体。

2019tctfxs1

Google一下LPH结构体,发现它出现在了IDA Pro权威指南的目录里,刚好手头有一本IDA权威指南,打开一看,这竟然是个IDA的处理器模块,它负责ida内部的反汇编工作。

先将dll放到ida根目录下的procs文件夹中,再用ida打开binary。在Processor type中多了一个叫0CTF2019的选项。打开后这些binary就能被反汇编了。

2019tctfxs2

按C分析,所有的指令和寄存器都用6和_表示了。这时候应该能大致猜到,我们要做的就是逆处理器模块,找到对应的指令还原出来,然后逆binary。本质上还是一道vm题

2019tctfxs3

处理器模块简介

直接逆处理器模块可能有些无从下手,好在手边有IDA Pro权威指南。不过版本有点旧,对应的ida还是5.5版本,我们只需大概了解一下处理器模块的结构就行了。

其次IDA SDK文档也是很重要的,所有结构体和IDA API函数的定义都在里面。

参考资料:权威指南,IDA SDK文档

根据权威指南,处理器模块最重要的一个结构体叫processor_t结构体,它包含了所有处理器相关的重要信息,结构体名称为LPH。对比文档我们可以看到LPH的所有成员和数值,比较重要的是指令名,寄存器名,和一个叫notify的函数。

这里我们可以直接用hexeditor把寄存器名改成R0到R39。

notify函数的作用是对事件做出相应,它里面应包含三个最核心的函数:分析器,模拟器,输出器。

分析器:分析指令,填充指令相关的信息,比如指令用到的操作数及操作数种类等。一般叫ana函数

模拟器:基于指令的行为创建代码和数据的交叉引用。在此过程中有模拟执行的部分,我们可以根据此推测出指令的种类。此外模拟器还用于跟踪栈指针的变化,并创建局部变量(这个功能在本题中没用到)一般叫emu函数

输出器:将经过反汇编的指令输出到IDA窗口中。一般叫out函数。

为了方便分析,最好根据文档将op_t和insn_t结构体抄下来导入ida。op_t包括了与每个指令操作数相关的信息,insn_t结构体则包含了每条指令相关的信息。这里以文档上的结构体为主,权威指南上的不全。

2019tctfxs4

notify就在LPH里就能找到。在notify的case A的函数里有大量的case。参数类型设成insn_t后,可以看到对各种操作数的属性设置,这个函数就是ana了。

2019tctfxs5

notify函数的case B函数里面,对应着看权威指南上的实例emu函数,可以看出一定的相似性,下面还能找到名为add_cref的ida api,这个大概率就是emu了。

2019tctfxs6

out函数则比较容易找,case 0x13里面出现了"op%d"字符串,之前在binary里出现过“op1”,“op”

指令分析

出题人给了源码

分析指令之前要找对方向。在ana中主要是对操作数的类型进行修改,这里可以作为一点参考。在emu中有模拟执行的过程,对操作数的数值进行了修改,这里其实更重要。在emu中到处找找,发现一个函数sub_1800026E0很长,有很多case,还有一些关键的数值运算及操作,大概可以猜到这是修改寄存器数值。大多数指令可以从这两个函数中分析出来。

举两个例子 第一条指令:

在ana中,首先用get_bytes获取了四个字节作为一条opcode。insn的itype成员被设置为opcode>>0xC&0x1F,这部分就是每个指令的编号了。指令的编号和在dll中排列的顺序是一致的,可以先在hexeditor将指令名按顺序编号方便之后寻找与修改。

来到binary的第一条指令,在hex中可以看到直接被识别成八个字节一条,EF BA 72 2F 30 43 54 46。ana中读取八个字节的只有case 0xb。而且注意到操作数1的实际大小被设置为了获取到的数值异或了0x46544330,显示出来的却又是0x66546330。对比hex可以看到真实值应该是0x46544330^0x46544330。out中也能看到^0x66546330的字样。

来到emu,之前修改数值的函数的case B里可以看到将操作数1的数值幅给了一个变量。对比其他case大致能猜出这个变量最终去向操作数0。

因此这条指令将一个立即数异或0x46544330,幅值给操作数0。因此这应该是li(当然也可以用mov表示)

2019tctfxs7

再来分析下binary中00000038位置的指令,这里操作数1是op1,不太清楚是什么。opcode是00D3F247

先来到ana,opcode右移12位再与31得到指令编号31,case 31中可以看到根据opcode的对应位置先设置了操作数0的数值类型是dword(查文档看类型编码对应的意义),再根据opcode switch了三个分支,分别将操作数1设置成了不同的类型,这里设置成的是dword。同时注意到还设置了操作数1对应着一个寄存器R3(D3F247>>22&0x1f),因此这里的Op1应该是寄存器R3。

2019tctfxs8

来到emu,看到这里将操作数1的一个叫地址的成员赋给a4,再对a4调用get_byte/get_word/get_dword。猜测一下应该是从操作数1寻址,找到一个对应类型的数据幅值给操作数0,对应汇编代码里的[R1]这样。

2019tctfxs9

经过分析,可以看出这条指令是load指令(当然也可以用mov表示)

类似的,我们也能得到下方的store指令,与load相反,将操作数0的值保存到操作数1的地址中。

大部分指令都可以用这种方式分析出,比较简单的像add sub nor和cmp。

注意这里有两种cmp,一种是正常的cmp,另一种比较的是字符串的大小(“2”>“1000”),这在之后的逆向中十分重要。

比较不常见的有个exchange指令,交换了两个操作数中的内容。

此外一些不太明白的指令可以在逆binary时联系上下文得到。

逆完的指令直接用hexeditor在dll里修改就行了

binary逆向

我一开始直接用python抄了一遍代码,然而直接跑就挂了,因为它的算法并没有经过优化,一个循环40多亿,根本顶不住,所以还是老老实实逆算法吧

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
ROM:00000000                 li      R5, 0x66546330  ;; 0
ROM:00000008                 li      R4, 0x66546334  ;; 4
ROM:00000010                 li      R7, 0x66546372 ;; 'B' ;; 0x42
ROM:00000018                 li      R8, 0x665468B0  ;; 0xB80
ROM:00000020                 li      R9, 0x66546F90  ;; 0xCA0
ROM:00000028                 li      R16, 0x66546BB8 ;; 0x888
ROM:00000030                 loop    loc_34, R7
ROM:00000034
ROM:00000034 loc_34:                                 ;; CODE XREF: ROM:00000054↓j
ROM:00000034                 add     R3, R8, R5
ROM:00000038                 load    R0, op1         ;; R3
ROM:0000003C                 add     R3, R9, R5
ROM:00000040                 load    R1, op1         ;; R3
ROM:00000044                 call    sub_1E0
ROM:00000048                 add     R3, R16, R5
ROM:0000004C                 store   R0, op1         ;; R3
ROM:00000050                 add     R5, R5, R4
ROM:00000054                 endloop loc_34

开头赋值了一些变量,然后进入一个长度位66的循环。从0xB80和0xCA0开始获取两个dword作为参数传入函数

sub_1E0,返回值存入0x888,这里没什么复杂的。

进入sub_1E0函数。

 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
ROM:000001E0                 in3     0x66546230
ROM:000001E4                 mov     R10, R0
ROM:000001E8                 mov     R11, R1
ROM:000001EC                 li      R25, 0x66544329 ;; 0x2019
ROM:000001F4                 li      R23, 0x66546330 ;; 0x0
ROM:000001FC                 li      R24, 0x66546330 ;; 0x0
ROM:00000204                 li      R19, 0x66546334 ;; 0x4
ROM:0000020C                 li      R18, 0x66546331 ;; 0x1
ROM:00000214                 loop    loc_218, R0
ROM:00000218
ROM:00000218 loc_218:                                ;; CODE XREF: sub_1E0+54↓j
ROM:00000218                 add     R6, R23, R1
ROM:0000021C                 div     R14, R15, R6, R0
ROM:00000220                 add     R15, R15, R18
ROM:00000224                 add     R17, R25, R24
ROM:00000228                 store   R15, op1        ;; R17
ROM:0000022C                 add     R23, R23, R18
ROM:00000230                 add     R24, R24, R19
ROM:00000234                 endloop loc_218
ROM:00000238                 li      R15, 0x66546331 ;; 1
ROM:00000240                 li      R23, 0x66546331 ;; 1
ROM:00000248                 sub     R2, R0, R15
ROM:0000024C                 loop    loc_250, R2
ROM:00000250
ROM:00000250 loc_250:                                ;; CODE XREF: sub_1E0+BC↓j
ROM:00000250                 li      R24, 0x66546330 ;; 0
ROM:00000258                 li      R22, 0x66546330 ;; 0
ROM:00000260                 sub     R3, R0, R23
ROM:00000264                 loop    loc_268, R3
ROM:00000268
ROM:00000268 loc_268:                                ;; CODE XREF: sub_1E0+B4↓j
ROM:00000268                 add     R26, R25, R22
ROM:0000026C                 load    R12, op1        ;; R26
ROM:00000270                 add     R27, R26, R19
ROM:00000274                 load    R13, op1        ;; R27
ROM:00000278                 strcmp  op0, R12, R13   ;; R32
ROM:0000027C                 jmpcmp  R32, loc_28C
ROM:00000280                 exchange R12, R13
ROM:00000284                 store   R12, op1        ;; R26
ROM:00000288                 store   R13, op1        ;; R27
ROM:0000028C
ROM:0000028C loc_28C:                                ;; CODE XREF: sub_1E0+9C↑j
ROM:0000028C                 add     R24, R24, R15
ROM:00000290                 add     R22, R22, R19
ROM:00000294                 endloop loc_268
ROM:00000298                 add     R23, R23, R15
ROM:0000029C                 endloop loc_250         ;; 0
ROM:000002A0                 li      R24, 0x66546330 ;; 0
ROM:000002A8                 cmp     op0, R1, R15    ;; R33
ROM:000002AC                 jmpcmp  R33, loc_2C0
ROM:000002B0                 sub     R2, R1, R15
ROM:000002B4                 loop    loc_2B8, R2
ROM:000002B8
ROM:000002B8 loc_2B8:                                ;; CODE XREF: sub_1E0+DC↓j
ROM:000002B8                 add     R24, R24, R19
ROM:000002BC                 endloop loc_2B8
ROM:000002C0
ROM:000002C0 loc_2C0:                                ;; CODE XREF: sub_1E0+CC↑j
ROM:000002C0                 add     R26, R25, R24
ROM:000002C4                 load    R0, op1         ;; R26
ROM:000002C8                 in5
ROM:000002CC                 retn

第一条指令我也不知道有啥用

func函数包括两个参数a,b

第一个循环:b从b+1到b+a+1不断的模a,结果以dowrd存在0x2019中

第二个循环中,可以看到有两层循环,次数都是之前获得的数组的长度,每次比较相邻两个元素并根据大小交换。不难发现这是一个排序。特别的,它排序并非是按照数值大小排序的(这样就是从1到a所有的数了),而是之前提到过的字符串大小比较(将整数转成字符串)

排好序后,将第b个数返回。

稍微简化一下,贴出python代码及fun(233,144)的输出和list作为参考

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def icmp(a,b):
    return cmp(str(a),str(b))

def fun(a,b):
    r = []
    for i in range(a):
        r.append((b+i)%a+1)
    r.sort(icmp)
    print(r)
    return r[b-1]

print(fun(233,144))

输出:

1
2
[1, 10, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 11, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 12, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 13, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 14, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 15, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 16, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 17, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 18, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 19, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 2, 20, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 21, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 22, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 23, 230, 231, 232, 233, 24, 25, 26, 27, 28, 29, 3, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 4, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 5, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 6, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 7, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 8, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 9, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]
228

可以看到与常规排序的不同。然而光用上面的代码没办法求出结果,因为数值实在太大了,占用空间也太多了,甚至无法编译通过。

我们需要找到一种映射,给出一个b,在限定范围的a内,找到a按字符串排序后的第b个元素。

分析:可以看出来,以1开头的数都在前面,然后是2开头,3开头。。。由于a不同,1、2、3。。。开头的数目也不同。我们先分析999个数,每个字符开头的数的数目是一样的。

对于1到999这999个数,1开头的数有:

1 1个

10,11,12 …… 19 10个

100,101,102 …… 199 100个

每个字符开头的数目都是111个,这样把要求的n除以111再加以,就能得到它是几开头的了

注意,对于111,由于1是第一个数,并没有第0个数。第111个数是199,然而111//111 == 1。实际上除以111的到结果为0的值范围在[0,110],因此除以的时候要先-1。

对于所有的1开头的111个数,n-1模111(同样的,这里也要减一)后得到的数,就是这些1开头的数种的第几个了。模后的结果如果为0,就直接返回1本身。大于0时,不难看出,以10开头的数共有11个,以11开头的数共有11个,以12开头的数也有11个……又回到相似的地方。不同的,第一位是从1到9共9个数,而第二位有从0到9共10个数。

分析完可以写出快速求解的代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
def func(a,b):
    ret = ''
    table = [1,11,111,1111,11111,111111,1111111,11111111,111111111,1111111111,11111111111]
    n = b
    lenth = len(str(a))
    num = (n-1) // table[lenth-1]
    ret+=str(num+1)
    n = (n-1) % table[lenth-1]
    if n == 0:
        return int(ret)
    i = lenth - 2
    while(True):
        num = (n-1) // table[i]
        n = (n-1) % table[i]
        ret+=str(num)
        if n == 0:
            return int(ret)
        i -= 1
    return int(ret)

此函数逆完,剩下的部分没有需要优化的,抄抄代码就行了。注意下面几个case里的或非最后其实都是异或

最终的脚本

 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
def func(a,b):
    ret = ''
    table = [1,11,111,1111,11111,111111,1111111,11111111,111111111,1111111111,11111111111]
    n = b
    lenth = len(str(a))
    num = (n-1) // table[lenth-1]
    ret+=str(num+1)
    n = (n-1) % table[lenth-1]
    if n == 0:
        return int(ret)
    i = lenth - 2
    while(True):
        num = (n-1) // table[i]
        n = (n-1) % table[i]
        ret+=str(num)
        if n == 0:
            return int(ret)
        i -= 1
    return int(ret)

p = [0xFA730603, 0xF8084C29, 0xF4290A55, 0xF17A02CD, 0xF1E59BC4, 0xF41ABBF1, 0xFDF84718, 0xF0083FD1, 0xF1BAED2B, 0xFA2AEAC7, 0xF652CC03, 0xF178B08D, 0xF1198EB5, 0xF0672595, 0xF1753690, 0xF2E67825, 0xF2B0197A, 0xF84C8755, 0xFB72A68F, 0xF656D307, 0xFC005E80, 0xF350372A, 0xF27B843E, 0xF1AE2E9B, 0xF2ECB793, 0xF2CF233D, 0xFDAB487F, 0xFB7989EE, 0xF585E8A7, 0xFB155234, 0xF8615835, 0xFE982EE1, 0xF6C42E3E, 0xF96E377C, 0xF102A7E0, 0xFE2391E8, 0xFA7500A5, 0xF640F391, 0xF1E1670F, 0xF9D0235F, 0xF7C12D7D, 0xF863762C, 0xFBED5B8A, 0xFDB8DEC7, 0xF186136E, 0xF2DFACF3, 0xFE5D1AC8, 0xF25E770D, 0xFB56D6DD, 0xF33EB123, 0xF4B7FADA, 0xF6242889, 0xF59F048F, 0xFC86FA29, 0xFCD04769, 0xF14B8063, 0xFAA6F222, 0xF0D23990, 0xF6846A8C, 0xF3CD8234, 0xFA440DE1, 0xF5DE4EE7, 0xF40C2BCA, 0xF0590358, 0xF4A968CB, 0xF65A2DFF]
q = [0x2FA2377, 0x6D1C33E, 0x1B22D44, 0x171F345, 0x183FF47, 0x2879609, 0x36EB9D7, 0x811BB, 0xC12DB0, 0x1B7DB20, 0x54F2EC9, 0x11A893B, 0x48DB44, 0x1F61D0, 0x8B7372, 0x1A717EF, 0x167692A, 0x55ACE9B, 0x47D0923, 0x9E4F8E, 0x2036162, 0x2F9AC19, 0x1E0DBF7, 0x1852D9B, 0x26D4EBA, 0x20E3486, 0xBB0F702, 0x3E40DF6, 0x24284B, 0x447418E, 0x7BB11A6, 0x6A330BC, 0xC5815A, 0x2EFAA0D, 0xC1E170, 0x628F151, 0x1C629CF, 0x2E04C82, 0x15445D, 0x1BDE2A7, 0x46ABA70, 0x11A1341, 0xB733982, 0x6E87A60, 0xF7715D, 0x24F3682, 0x181C131, 0x23AA7F6, 0xA44B51, 0x29E1B4F, 0x2686A1, 0x1956047, 0x214B4AC, 0xF3BF0, 0x9701B3, 0x1C3E00, 0x6B4AAF, 0x773A9A, 0x2BCB4D1, 0x1690AF8, 0x4139BD8, 0xE04630, 0x17E5300, 0x473799, 0x401B105, 0x373A611]
a = [  0x4E, 0xE4, 0x4C, 0x7A, 0xFE, 0xC9, 0xB7, 0x4E, 0xFE, 0xF1, 
  0x1E, 0x3B, 0xBE, 0x41, 0xB3, 0x5A, 0xD6, 0xBB, 0x52, 0x37, 
  0x62, 0xEE, 0x67, 0x32, 0xF6, 0x03, 0x55, 0x0B, 0x56, 0xB4, 
  0x12, 0x59, 0x13, 0xA6, 0x8E, 0x56, 0x04, 0x74, 0x6A, 0x12, 
  0xE5, 0xC3, 0x3F, 0x97, 0xF4, 0x82, 0x47, 0xA6, 0xCB, 0x46, 
  0x97, 0xBD, 0x65, 0x13, 0x07, 0xF0, 0x2E, 0xDE, 0x36, 0x4C, 
  0x44, 0x26, 0x02, 0xFB, 0xA3, 0x42]
b = [  0x97, 0x15, 0x43, 0x98, 0x11, 0x2F, 0x3E, 0x06, 0x6D, 0x12, 
  0x45, 0x33, 0x58, 0x0F, 0x6A, 0x8E, 0x84, 0x23, 0x3E, 0xAD, 
  0x4D, 0x79, 0x21, 0x1D, 0x7B, 0x40, 0x1C, 0xC8, 0x8F, 0x11, 
  0x6A, 0x18, 0x37, 0x97, 0x2E, 0x82, 0x2D, 0x2E, 0x28, 0x7C, 
  0x3C, 0x8B, 0x0C, 0x68, 0x14, 0x7D, 0x49, 0x35, 0x37, 0x63, 
  0x54, 0x13, 0x73, 0xCC, 0x9C, 0x54, 0x7C, 0x1F, 0x19, 0x59, 
  0x40, 0x30, 0x13, 0x20, 0xCE, 0x64]


r = []
for i in range(66):
    r.append(func(p[i],q[i]))
# print(r)
s = ''
for i in range(66):
    case = a[i]&3
    if case == 0:
        s+=chr((((r[i]%0x100)^a[i])+b[i]))
    elif case == 1:
        s+=chr((((r[i]%0x100)^a[i])+b[i]))
    elif case == 2:
        s+=chr((((r[i]%0x100)^a[i])-b[i]))
    elif case == 3:
        s+=chr((((r[i]%0x100)^a[i])-b[i]))
print(s)
1
flag{H1gHLigH7_Th3_Cu1tuRe_0f_CN_4nD_wen_TI_OpEN_fl0w3R_Together!}

评论