文章 - TCTF/0CTF sixology详解

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

题目拿到手，一个dll和一个binary。

binary直接用ida打开只是binary，暂时看不出什么。

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

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

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

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

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

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

处理器模块简介

直接逆处理器模块可能有些无从下手，好在手边有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结构体则包含了每条指令相关的信息。这里以文档上的结构体为主，权威指南上的不全。

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

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

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表示)

再来分析下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。

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

经过分析，可以看出这条指令是load指令（当然也可以用mov表示）

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

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

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

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

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

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

binary逆向

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

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函数。

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作为参考

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, 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个数。

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

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里的或非最后其实都是异或

最终的脚本

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)