首页
社区
课程
招聘
问答 CTF 排行榜 知识库 工具下载 看雪峰会 看雪商城 证书查询
  1. 看雪社区
  2. CTF对抗
    3. 发新帖
[原创]看雪.深信服 2021 KCTF 春季赛 第六题 寻回宝剑
2021-5-19 00:15 6726

[原创]看雪.深信服 2021 KCTF 春季赛 第六题 寻回宝剑

mb_mgodlfyn 活跃值
12
2021-5-19 00:15
6726

IDA打开，发现代码加了混淆，但规律性很强。

 

解混淆是一个迭代的过程：

  1. 首先注意到一个反复出现的代码片段：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    push   rax
    push   rax
    pushf
    call $+5
    pop    rax
    xor    rax,XXXXXXXX
    mov    QWORD PTR [rsp+0x10],rax
    popf
    pop    rax

    这段代码的效果等同于push一个地址，其值等于pop rax指令的地址异或上xor指令里的常量，是一个能够静态计算出来的确定的值。（注意文件头的IMAGE_DLLCHARACTERISTICS_DYNAMIC_BASE没有置位，程序没有开启动态基址，因此xor运算后的地址才有效）
    这样的代码片段可以统一替换为VIRTUAL push XXXXYYYY（VIRTUAL前缀是人为加的，为了区分程序里真实的push指令）

  2. 替换之后，程序里出现大量的

    1
    2
    VIRTUAL push XXXXYYYY
    ret

    等同于一条无条件跳转指令VIRTUAL jmp XXXXYYYY

  3. 对同一个寄存器连续的push和pop，可以直接去除

    1
    2
    push AAA
    pop AAA
    1
    2
    3
    4
    push AAA
    push BBB
    pop BBB
    pop AAA

  4. 对VIRTUAL jmp连接的代码块重新排序让它们顺序连在一起，从而省略掉无用的VIRTUAL jmp指令。在完成这一步后，重做第3步。

  5. 出现了一个新的模式（这个模式只有在前4步都做完之后才能看出来，因为这些指令在源程序中并不是连续的）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    push   rax
    push   rax
    pushf
    VIRTUAL push XXXXXXXX
    pop    rax
    add    rax,YYYYYYYY
    mov    QWORD PTR [rsp+0x10],rax
    popf
    pop    rax

    与第1步类似，整个片段等价为push一个常量。可以将整个片段替换为VIRTUAL push XXXXYYYY，然后重做第2步

  6. 反复迭代以上的步骤，重点是指令块的重新排序（第4步），每次重新排序后再次搜索第1、2、3、5步的代码模式做替换。直到代码不再能化简，打印输出即可。

由于混淆模式非常固定，所以先用objdump工具获得反汇编：objdump -d -M intel KCTF.exe > KCTF_objdump.txt，然后对字符串做操作。
（更好的方法应该使用Capstone这样的反汇编引擎，可惜不太熟悉）

 

代码如下：（与上面的步骤描述有少许不同，但主要思路是一致的）

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
class Instruction:
    __slots__ = ["va", "s"]
    def __init__(self, va, s):
        self.va = va
        self.s = s
    def __str__(self):
        return hex(self.va)+"\t"+self.s
 
class Block:
    __slots__ = ["startva", "jmpva", "insts"]
    def __init__(self):
        self.startva = None
        self.jmpva = None
        self.insts = []
    def __str__(self):
        r = ""
        r += f"; {hex(self.startva)}, {hex(self.jmpva) if self.jmpva else None}:\n"
        for inst in self.insts:
            r += str(inst)+"\n"
        return r
 
    def simplify1(self):
        i = 0
        while (i < len(self.insts)):
            tmp = self.insts[i].s
            i += 1
            if tmp.split()[0] == "push" and i < len(self.insts):
                tmp2 = self.insts[i].s
                i += 1
                if tmp2.split()[0] == "pop" and tmp2.split()[1] == tmp.split()[1]:
                    "push xxx ; pop xxx"
                    i -= 2
                    if self.startva == 0x14007def2:
                        print("xxx", self.insts[i])
                    self.insts.pop(i)
                    self.insts.pop(i)
                else:
                    i -= 1
 
    def simplify2(self):
        i = 0
        while i+8 < len(self.insts):
            if self.insts[i].s.startswith("push   rax") \
               and self.insts[i+1].s.startswith("push   rax") \
               and self.insts[i+2].s.startswith("pushf") \
               and self.insts[i+3].s.startswith("call") \
               and self.insts[i+4].s.startswith("pop    rax") \
               and self.insts[i+5].s.startswith("xor    rax,") \
               and self.insts[i+6].s.startswith("mov    QWORD PTR [rsp+0x10],rax") \
               and self.insts[i+7].s.startswith("popf") \
               and self.insts[i+8].s.startswith("pop    rax"):
                const1 = self.insts[i+4].va
                tmp1 = self.insts[i+3].s
                assert(int(tmp1.split()[1],16) == const1)
                tmp2 = self.insts[i+5].s
                const2 = int(tmp2[tmp2.index(",")+1:], 16)
                newinst = Instruction(self.insts[i].va, f"VIRTUAL push {hex(const1^const2)}")
                for _ in range(9):
                    self.insts.pop(i)
                self.insts.insert(i, newinst)
            i += 1
 
    def simplify3(self):
        i = 0
        while i+8 < len(self.insts):
            if self.insts[i].s.startswith("push   rax") \
               and self.insts[i+1].s.startswith("push   rax") \
               and self.insts[i+2].s.startswith("pushf") \
               and self.insts[i+3].s.startswith("VIRTUAL push") \
               and self.insts[i+4].s.startswith("pop    rax") \
               and self.insts[i+5].s.startswith("add    rax,") \
               and self.insts[i+6].s.startswith("mov    QWORD PTR [rsp+0x10],rax") \
               and self.insts[i+7].s.startswith("popf") \
               and self.insts[i+8].s.startswith("pop    rax"):
                tmp1 = self.insts[i+3].s
                const1 = int(tmp1.split()[2],16)
                tmp2 = self.insts[i+5].s
                const2 = int(tmp2[tmp2.index(",")+1:], 16)
                newinst = Instruction(self.insts[i].va, f"VIRTUAL push {hex((const1+const2) & 0xffffffffffffffff)}")
                for _ in range(9):
                    self.insts.pop(i)
                self.insts.insert(i, newinst)
            i += 1
 
    def simplify4(self):
        if len(self.insts) >= 2:
            if self.insts[-2].s.startswith("VIRTUAL push") \
               and self.insts[-1].s.startswith("ret"):
                tmp1 = self.insts[-2].s
                self.jmpva = int(tmp1.split()[2], 16)
                self.insts.pop(-1)
                self.insts.pop(-1)
 
    def simplify(self):
        lastlen = 0x7fffffff
        while len(self.insts) < lastlen:
            #print("aa", len(self.insts), lastlen)
            lastlen = len(self.insts)
            self.simplify1()
            self.simplify1()
            self.simplify2()
            self.simplify3()
            self.simplify4()
 
with open("KCTF_objdump.txt", "r") as f:
    lines = f.readlines()
 
allinsts = []
instaddr2index = {}
 
def initialize():
    global allinsts
    global instaddr2index
    for line in lines:
        tokens = line.split("\t")
        if len(tokens) == 3:
            va = int(tokens[0].rstrip(":"), 16)
            s = tokens[2].strip()
            if s != "int3":
                #print(hex(addr), s)
                inst = Instruction(va, s)
                allinsts.append(inst)
                instaddr2index[va] = len(allinsts)-1
 
def searchblock(va):
    global allinsts
    global instaddr2index
    bb = Block()
    bb.startva = va
    i = instaddr2index[va]
    while True:
        inst = allinsts[i]
        tokens = inst.s.split()
        bb.insts.append(inst)
        if (tokens[0] == "ret"):
            break
        i += 1
    return bb
 
def mergeblocklist(blocklist):
    bbb = Block()
    bbb.startva = blocklist[0].startva
    bbb.jmpva = blocklist[-1].jmpva
    bbb.insts = []
    for i in range(len(blocklist)):
        bb = blocklist[i]
        bbb.insts.extend(bb.insts)
    return bbb
 
def deobfuscation1(nextva):
    blocklist = []
    seenva = set()
    while nextva and nextva not in seenva:
        seenva.add(nextva)
        #print(hex(nextva))
        bb = searchblock(nextva)
        bb.simplify()
        #print(bb)
        blocklist.append(bb)
        nextva = bb.jmpva
    bbb = mergeblocklist(blocklist)
#    print(bbb)
    bbb.simplify()
#    print(bbb)
    return bbb    # mostly single instruction
 
def deobfuscation2(nextva):
    blocklist = []
    seenva = set()
    while nextva and nextva not in seenva:
        seenva.add(nextva)
        bbb = deobfuscation1(nextva)
        blocklist.append(bbb)
        nextva = bbb.jmpva
    bbbb = mergeblocklist(blocklist)
#    print(bbbb)
    return bbbb    # mostly deep first block instructions
 
 
def recognize_function(va):    # notice: must do block.simplify4 before do this
    blocklist = []
    seenva = set()
    while va and va not in seenva:
        #print(hex(va))
        seenva.add(va)
        block = deobfuscation2(va)
 
        newblock = Block()
        newblock.startva = block.startva
        newblock.jmpva = block.jmpva
        newblock.insts = []
 
        i = 0
        while i < len(block.insts):
            #print(i)
            inst = block.insts[i]
            if inst.s.startswith("VIRTUAL push"):
                const1 = int(inst.s.split()[2],16)
                newblock.insts.append(Instruction(inst.va,f"VIRTUAL call {hex(block.insts[i+1].va)}"))
                newblock.jmpva = const1
                break
            else:
                newblock.insts.append(inst)
            i += 1
        #print("newblock:", newblock)
        blocklist.append(newblock)
        va = newblock.jmpva
 
    bbbbb = mergeblocklist(blocklist)
    print(bbbbb)
    return bbbbb
 
 
initialize()
 
#deobfuscation2(0x14005FE4C)    # start
 
#recognize_function(0x14005FE4C)    # start:part1
#recognize_function(0x1400bf93f)    # start:part2
 
#recognize_function(0x140083814)    # main

简单解释一下代码：

  • Instruction类：对应一句汇编指令
  • Block类：对应一个“块”（不同于通常意义的“基本块”，这里的“块”指的是VIRTUAL jmp XXXXYYYY结束的一组指令序列）
  • searchblock(va)函数：给定一个虚拟地址，搜索以该地址为起点、以ret指令为终点的、在原程序中顺序排布的所有语句序列。一组语句序列构成了一个Block。
  • mergeblocklist函数：将“连续”的“块”合并为一个（“连续”定义为前一个块末尾的跳转目标等于后一个块的开头）
  • deobfuscation1函数：迭代前面的解混淆逻辑，主要针对在在原程序里真实连续的指令序列
  • deobfuscation2函数：迭代前面的解混淆逻辑，主要针对“块”合并后的“连续”指令序列
  • recognize_function(va)函数:给定一个虚拟地址，识别出从这里开始的一个函数

其实deobfuscation2之后得到的代码就已经完全没有了混淆，但是注意到里面出现了孤立的VIRTUAL push XXXXXXXX指令，且若干条指令之后一定会在栈平衡的情况下出现一个ret指令。
这种模式其实是函数调用，其中VIRTUAL push XXXXXXXX的常量是压栈的返回地址，即在原始函数中的真实的下一条指令。
deobfuscation2的输出结果是深入调用函数内部后的指令序列；recognize_function函数对这种情况进行了处理，从而恢复出“完整”的原始函数。（缺陷是，由于Block不是真正意义上的基本块，所以原始程序里的条件分支只能看到一条路径，不过问题不大，对另一条路径的起始地址也调用一次该函数即可）

 

有了解混淆脚本，现在可以分析程序逻辑了

 

从start函数开始（recognize_function(0x14005FE4C)），找出真正的main函数位于0x140083814
（可以自己写一个小程序再反汇编与之对比）

 

(在deobfuscation2(0x14005FE4C)的输出中看到调用了很多反调试函数，应该是在main之前的initterm中调用的。从后面的算法看，本题无需动态调试。如果需要调试，只要程序启动后再附加调试器即可)

 

main函数很长，截取若干个片段如下：(recognize_function的输出)

  1. 片段1

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    0x14000f17c    VIRTUAL call 0x140026de8    # call std::cin
    0x14001eb47    lea    rcx,[rsp+0x1010]
    0x14003a798    lea    rdx,[rip+0xfffffffffffc9ddf]        # *** 0x14000457e, char[] "1743"
    0x1400beaab    mov    QWORD PTR [rsp+0x50],rax
    0x140002c25    VIRTUAL call 0x1400d4a33    # *** 140004C88, strcmp with "1743"  # 0x1400d4a33
    0x1400f1dda    movsxd rcx,eax
    0x14009f9b9    cmp    rcx,0x0
    0x1400a988a    jne    0x1400a98a3    # 0x1400dab0e
    0x14009954a    lea    rcx,[rip+0xfffffffffff6af6d]        # 0x1400044be    # " >>> 阁下的数学功底十分扎实，只可惜与在下的绝世武学无缘，请回吧。"
    0x14002587c    VIRTUAL call 0x1400cd482
    0x1400dab0e    lea    rcx,[rsp+0x1010]
    0x14008475a    VIRTUAL call 0x140050476    # get input string length
    0x140083333    cmp    rax,0x54    # 84
    0x140035698    je     0x1400356b1
    0x140048e00    lea    rcx,[rip+0xfffffffffffbb695]        # 0x14000449c    # " >>> 阁下的数学成绩堪忧，请回吧。"

    可以看出，真正的输入长度为84，下一阶段的检查逻辑在0x1400356b1

  2. 片段2

    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
    ; 0x1400877ad, None:
    0x1400877ad    push   rax
    0x1400da463    mov    BYTE PTR [rsp+0x7],cl
    0x1400254a5    movsx  eax,BYTE PTR [rsp+0x7]
    0x140027b39    cmp    eax,0x30
    0x140087ceb    jl     0x140087d04    # 0x140045036
    0x1400d1b0f    movsx  eax,BYTE PTR [rsp+0x7]
    0x1400cbfad    cmp    eax,0x39
    0x140032877    mov    cl,0x1
    0x14004cbd4    mov    BYTE PTR [rsp+0x6],cl
    0x14005134f    jle    0x140051368
    0x140045036    movsx  eax,BYTE PTR [rsp+0x7]
    0x1400a27a9    cmp    eax,0x41
    0x1400db7db    jl     0x1400db7f4
    0x1400dabed    movsx  eax,BYTE PTR [rsp+0x7]
    0x1400a07d9    cmp    eax,0x5a
    0x1400ed537    mov    cl,0x1
    0x140025ead    mov    BYTE PTR [rsp+0x6],cl
    0x140032ada    jle    0x140032af3    # 0x14005e3af
    0x1400388fa    movsx  eax,BYTE PTR [rsp+0x7]
    0x140045713    cmp    eax,0x2b
    0x1400779b8    mov    cl,0x1
    0x1400ca53a    mov    BYTE PTR [rsp+0x6],cl
    0x1400bdc5a    je     0x1400bdc73    # 0x14005e3af
    0x1400b40d3    movsx  eax,BYTE PTR [rsp+0x7]
    0x140071b51    cmp    eax,0x2d
    0x140031fa6    mov    cl,0x1
    0x1400a85c9    mov    BYTE PTR [rsp+0x6],cl
    0x140021689    je     0x1400216a2
    0x140059269    movsx  eax,BYTE PTR [rsp+0x7]
    0x1400f5da9    cmp    eax,0x2a
    0x140067a65    mov    cl,0x1
    0x1400477a2    mov    BYTE PTR [rsp+0x6],cl
    0x14005d81b    je     0x14005d834
    0x140082dcc    movsx  eax,BYTE PTR [rsp+0x7]
    0x140014c52    cmp    eax,0x2f
    0x1400afc6d    mov    cl,0x1
    0x14006091f    mov    BYTE PTR [rsp+0x6],cl
    0x1400020ec    je     0x140002105
    0x1400dde99    movsx  eax,BYTE PTR [rsp+0x7]
    0x140081c7a    cmp    eax,0x25
    0x1400f43b2    mov    cl,0x1
    0x1400200b9    mov    BYTE PTR [rsp+0x6],cl
    0x1400819ac    je     0x1400819c5
    0x140085a98    movsx  eax,BYTE PTR [rsp+0x7]
    0x140003a93    cmp    eax,0x3d
    0x1400f9bac    sete   cl
    0x140080797    mov    BYTE PTR [rsp+0x6],cl
    0x14005e3af    mov    al,BYTE PTR [rsp+0x6]
    0x14006e388    and    al,0x1
    0x1400bd7f2    movzx  eax,al
    0x1400d73bf    pop    rcx
    0x140095d39    ret

    合法的输入字符有42种：0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ+-*/%=

  3. 片段3

    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
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    ; 0x14005828f, None:
    0x14005828f    sub    rsp,0x38
    0x1400ab750    mov    QWORD PTR [rsp+0x30],rcx
    0x1400466c5    mov    rax,QWORD PTR [rsp+0x30]
    0x14003423a    mov    cl,BYTE PTR [rax]
    0x1400158bf    VIRTUAL call 0x1400d5e04
    0x1400ba991    imul   rax,rax,0x2a
    0x1400ea00d    mov    rdx,QWORD PTR [rsp+0x30]
    0x140039bc9    mov    cl,BYTE PTR [rdx+0x1]
    0x14005c2d0    mov    QWORD PTR [rsp+0x28],rax
    0x140063827    VIRTUAL call 0x1400d5e04
    0x140037cf1    mov    rdx,QWORD PTR [rsp+0x28]
    0x1400a7df8    add    rdx,rax
    0x1400d4395    mov    rax,rdx
    0x140057c71    add    rsp,0x38
    0x1400da66e    ret
    #
    ; 0x1400d5e04, None:
    0x1400d5e04    sub    rsp,0x10
    0x1400731d7    mov    BYTE PTR [rsp+0x7],cl
    0x1400882ca    movsx  eax,BYTE PTR [rsp+0x7]
    0x1400938d7    cmp    eax,0x30
    0x14009a8bf    jl     0x14009a8d8
    0x1400b54f4    movsx  eax,BYTE PTR [rsp+0x7]
    0x14001a372    cmp    eax,0x39
    0x1400794c2    jg     0x1400794db
    0x140043279    movsx  rax,BYTE PTR [rsp+0x7]
    0x140069cab    sub    rax,0x30
    0x14002e028    mov    QWORD PTR [rsp+0x8],rax
    0x14008bbcc    mov    rax,QWORD PTR [rsp+0x8]
    0x1400831f7    add    rsp,0x10
    0x14002974f    ret
    ; 0x1400794db, None:
    0x140084ba0    movsx  eax,BYTE PTR [rsp+0x7]
    0x14000224d    cmp    eax,0x41
    0x14002e600    jl     0x14002e619
    0x14000ddd0    movsx  eax,BYTE PTR [rsp+0x7]
    0x1400b2dc9    cmp    eax,0x5a
    0x14001e7d0    jg     0x14001e7e9
    0x1400ded3f    movsx  rax,BYTE PTR [rsp+0x7]
    0x14004b966    sub    rax,0x41
    0x140094d9c    add    rax,0xa
    0x1400dbb0c    mov    QWORD PTR [rsp+0x8],rax
         jmp 0x14008bbcc
    ; 0x14001e7e9, None:
    0x14004a292    movsx  eax,BYTE PTR [rsp+0x7]
    0x1400f5a62    cmp    eax,0x2b
    0x1400d174f    jne    0x1400d1768
    0x140003a25    mov    QWORD PTR [rsp+0x8],0x24
    ; 0x1400d1768, None:
    0x14003c4fe    movsx  eax,BYTE PTR [rsp+0x7]
    0x140096d4f    cmp    eax,0x2d
    0x140086754    jne    0x14008676d
    0x1400528a1    mov    QWORD PTR [rsp+0x8],0x25
    ; 0x14008676d, None:
    0x1400d50cf    movsx  eax,BYTE PTR [rsp+0x7]
    0x14001e900    cmp    eax,0x2a
    0x1400301db    jne    0x1400301f4
    0x14005337e    mov    QWORD PTR [rsp+0x8],0x26
    ; 0x1400301f4, None:
    0x140082b7c    movsx  eax,BYTE PTR [rsp+0x7]
    0x1400f3d8e    cmp    eax,0x2f
    0x140068739    jne    0x140068752
    0x14000c5fa    mov    QWORD PTR [rsp+0x8],0x27
    ; 0x140068752, None:
    0x14005d795    movsx  eax,BYTE PTR [rsp+0x7]
    0x140064edf    cmp    eax,0x25
    0x1400706d1    jne    0x1400706ea
    0x1400aef1c    mov    QWORD PTR [rsp+0x8],0x28
    ; 0x1400706ea, None:
    0x14003deb0    movsx  eax,BYTE PTR [rsp+0x7]
    0x1400c9de1    cmp    eax,0x3d
    0x1400237d8    jne    0x1400237f1
    0x14007b859    mov    QWORD PTR [rsp+0x8],0x29

    输入的2个字符被转换为1个字符，转换方式是先转为[0,41]的数字（对应前面的合法字符列表的索引），然后第一个数字*42再加第二个数字

  4. 片段4

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    0x14007c870    VIRTUAL call 0x14005828f    # 片段3
    0x140014acc    mov    rcx,QWORD PTR [rsp+0xa8]
    0x1400787fe    mov    QWORD PTR [rsp+rcx*8+0xec0],rax
    0x1400afe42    cmp    QWORD PTR [rsp+0xa8],0x0
    0x140022c16    je     0x140022c2f    # 0x1400297ba
    0x1400cd021    mov    rax,QWORD PTR [rsp+0xa8]
    0x1400ea72c    mov    rax,QWORD PTR [rsp+rax*8+0xec0]
    0x1400abe1c    mov    rcx,QWORD PTR [rsp+0xa8]
    0x1400e81e3    sub    rcx,0x1
    0x1400906db    cmp    rax,QWORD PTR [rsp+rcx*8+0xec0]
    0x1400a9b93    jg     0x1400a9bac    # 0x1400297ba
    0x140059bab    lea    rcx,[rip+0xfffffffffffaa8ea]        # 0x14000449c    # " >>> 阁下的数学成绩堪忧，请回吧。"

    把输入的84个字符转换为42个整数，要求严格单调递增

  5. 片段5

    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
    ; 0x140016058, 0x1400e1e42:
    0x140001a0a    xor    eax,eax
    0x1400ccbf8    lea    rcx,[rsp+0xe90]
    0x14004662e    mov    edx,eax
    0x14004a3b8    mov    r8d,0x2a
    0x14006ea24    mov    QWORD PTR [rsp+0x48],r8
    0x140098b05    mov    DWORD PTR [rsp+0x44],eax
    0x1400c9eb2    VIRTUAL call 0x1400c9bcf
    0x1400930c5    lea    rcx,[rsp+0xe60]
    0x1400ee6c6    mov    edx,DWORD PTR [rsp+0x44]
    0x1400450f9    mov    r8,QWORD PTR [rsp+0x48]
    0x1400311f7    VIRTUAL call 0x1400c9bcf
    0x14007d9d5    mov    QWORD PTR [rsp+0xa0],0x0
    #
    0x140002310    cmp    QWORD PTR [rsp+0xa0],0x2a
    0x140003980    jge    0x140003999                                               #
    0x140001f98    mov    rax,QWORD PTR [rsp+0xa0]
    0x14002d5ac    mov    rax,QWORD PTR [rsp+rax*8+0xec0]
    0x140046c25    cqo
    0x140073e00    mov    ecx,0x2a
    0x14009ea4f    idiv   rcx
    0x14006ec35    mov    QWORD PTR [rsp+0x98],rdx
    0x140060863    mov    rdx,QWORD PTR [rsp+0xa0]
    0x140063300    mov    rdx,QWORD PTR [rsp+rdx*8+0xec0]
    0x140017083    mov    rax,rdx
    0x1400c5cff    cqo
    0x1400bcf6c    idiv   rcx
    0x14008cce3    mov    QWORD PTR [rsp+0x90],rax
    0x1400bf3ef    mov    rax,QWORD PTR [rsp+0x98]
    0x14004b8f8    test   BYTE PTR [rsp+rax*1+0xe90],0x1
    0x1400ece6a    jne    0x1400ece83
    0x14005224c    mov    rax,QWORD PTR [rsp+0x90]
    0x140015f89    test   BYTE PTR [rsp+rax*1+0xe60],0x1
    0x14006633f    je     0x140066358
    0x1400cd302    lea    rcx,[rip+0xfffffffffff37193]        # 0x14000449c
    0x140045e9b    VIRTUAL call 0x1400cd482
    0x140027ace    mov    rax,QWORD PTR [rsp+0x98]
    0x1400e4c50    mov    BYTE PTR [rsp+rax*1+0xe90],0x1
    0x1400ac622    mov    rax,QWORD PTR [rsp+0x90]
    0x1400b5248    mov    BYTE PTR [rsp+rax*1+0xe60],0x1
    0x140037cd0    mov    rax,QWORD PTR [rsp+0xa0]
    0x140026abb    add    rax,0x1
    0x1400258e6    mov    QWORD PTR [rsp+0xa0],rax
         jmp 0x140002310

    前面得到的42个整数，分别除以42，取整作为横坐标，取余作为纵坐标，要求横纵坐标分别都没有重复（从这里看出，输入的84个字符其实是42个坐标，横纵交替）

  6. 片段6

    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
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    ; 0x140003999, 0x1400f9bfa:
    0x14006b00f    xor    edx,edx
    0x140088714    lea    rax,[rsp+0xc0]
    0x1400ca071    mov    rcx,rax
    0x140062801    mov    r8d,0xd9e
    0x1400a6a82    VIRTUAL call 0x1400c9bcf
    0x1400c86f5    mov    QWORD PTR [rsp+0x88],0x0         # [rsp+0x88]: i: [0, 42)
    #
    0x1400d320e    cmp    QWORD PTR [rsp+0x88],0x2a
    0x140056b2f    jge    0x140056b48
    0x1400cbe10    mov    rax,QWORD PTR [rsp+0x88]
    0x140052e9d    add    rax,0x1
    0x140078f7f    mov    QWORD PTR [rsp+0x80],rax         # [rsp+0x80]: j: [1,42)
    #
    0x1400286db    cmp    QWORD PTR [rsp+0x80],0x2a
    0x14000d91a    jge    0x14000d933
    #
    0x1400f755c    mov    rax,QWORD PTR [rsp+0x88]         # i
    0x140098656    mov    rax,QWORD PTR [rsp+rax*8+0xec0]    # 42*row+col
    0x140001584    cqo
    0x1400a4adc    mov    ecx,0x2a
    0x14001f9e4    idiv   rcx
    0x14009d9ea    mov    r8,QWORD PTR [rsp+0x80]       # j
    0x1400eda1e    mov    r8,QWORD PTR [rsp+r8*8+0xec0]    # 42*row+col
    0x14000ea19    mov    rax,r8
    0x1400a04c3    mov    QWORD PTR [rsp+0x38],rdx    # rdx是余数
    0x140037898    cqo
    0x14008a550    idiv   rcx
    0x1400399f2    mov    r8,QWORD PTR [rsp+0x38]
    0x1400d4106    sub    r8,rdx                                       # col[i] - col[j]
    0x1400901f7    mov    QWORD PTR [rsp+0x78],r8      # col[i] - col[j]
    0x14009daad    mov    rdx,QWORD PTR [rsp+0x88]
    0x14000e4e3    mov    rdx,QWORD PTR [rsp+rdx*8+0xec0]
    0x1400ee409    mov    rax,rdx
    0x1400c5ee9    cqo
    0x140020832    idiv   rcx
    0x14008c074    mov    r8,QWORD PTR [rsp+0x80]
    0x14006079f    mov    r8,QWORD PTR [rsp+r8*8+0xec0]
    0x140013395    mov    QWORD PTR [rsp+0x30],rax
    0x1400c5ce1    mov    rax,r8
    0x14002fff8    cqo
    0x14007539e    idiv   rcx
    0x14006bf8a    mov    rcx,QWORD PTR [rsp+0x30]
    0x1400db4a6    sub    rcx,rax                                     # row[i]-row[j]
    0x1400e127d    mov    QWORD PTR [rsp+0x70],rcx
    0x140073b88    cmp    QWORD PTR [rsp+0x78],0x0    # col[i] - col[j]
    0x14006437e    jge    0x140064397                # 0x1400b368c
    0x1400bff7e    xor    eax,eax
    0x1400eacb4    mov    ecx,eax
    0x140080a4a    mov    rdx,rcx
    0x1400a7967    sub    rdx,QWORD PTR [rsp+0x78]
    0x1400517ac    mov    QWORD PTR [rsp+0x78],rdx    # col[j]-col[i]
    0x14000b3c6    sub    rcx,QWORD PTR [rsp+0x70]
    0x14008da3a    mov    QWORD PTR [rsp+0x70],rcx     # row[j]-row[i]
    #
    0x1400b368c    mov    rax,QWORD PTR [rsp+0x70]
    0x140079e70    add    rax,0x29
    0x1400de855    mov    QWORD PTR [rsp+0x70],rax     # 41+(row[i]-row[j]) / 41+(row[j]-row[i])
    0x14007c0c8    imul   rax,QWORD PTR [rsp+0x70],0x2a
    0x1400dc9b8    lea    rcx,[rsp+0xc0]
    0x140038fe8    add    rcx,rax
    0x140067202    mov    rax,QWORD PTR [rsp+0x78]    # col[i]-col[j] / col[j]-col[i]
    0x14008b8fd    test   BYTE PTR [rcx+rax*1],0x1
    0x140063b11    je     0x140063b2a
    0x1400999f4    lea    rcx,[rip+0xfffffffffff6aaa1]        # 0x14000449c
    0x1400d80be    VIRTUAL call 0x1400cd482
    0x1400f9bfc    imul   rax,QWORD PTR [rsp+0x70],0x2a
    0x14007f148    lea    rcx,[rsp+0xc0]
    0x1400eb582    add    rcx,rax
    0x140065e6f    mov    rax,QWORD PTR [rsp+0x78]
    0x1400f535f    mov    BYTE PTR [rcx+rax*1],0x1
    0x140013fc1    mov    rax,QWORD PTR [rsp+0x80]
    0x140073e8d    add    rax,0x1
    0x1400b9738    mov    QWORD PTR [rsp+0x80],rax
         jmp 0x1400286db
    #
    ; 0x14000d933, 0x1400f9bfa:
    0x14001811b    mov    rax,QWORD PTR [rsp+0x88]
    0x1400aa05a    add    rax,0x1
    0x1400df403    mov    QWORD PTR [rsp+0x88],rax
         jmp 0x1400d320e

    最复杂的检查，二重循环遍历点对，计算纵坐标之差和横坐标之差（如果纵坐标之差为负则两个值都取反），然后计算后者*42+前者，要求这个值不重复（实际上是要求，不存在位置相对值一样的点对）

  7. 片段7

    1
    2
    3
    4
    5
    6
    7
    8
    ; 0x140056b48, None:
    0x140039540    lea    rcx,[rsp+0x1010]
    0x1400ce591    lea    rdx,[rip+0xfffffffffff35f89]        # 0x140004521    # "02152S3X4Z5Q6C7T819/ADB%C*DL"
    0x14004cacf    mov    r8d,0x1c
    0x14004fed9    call   QWORD PTR [rip+0xfffffffffffb4db9]        # 0x140004c98    # strncmp
    0x140025175    movsxd rcx,eax
    0x140021803    cmp    rcx,0x0
    0x1400b7446    je     0x1400b745f

    最后一处检查，限定了输入的前28个字符（其实依次是42*42棋盘的前14行的点的坐标，每行一个）

 

检查逻辑有点像N皇后，只不过斜线规则改成了更复杂的点对相对位置检查

 

求解：回溯法爆破（参考了网上的一段代码），修改了验证规则

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
QUEEN = 42
 
q = [-10000]*42
 
checkmap = [0]*83*42
def updatecheckmap(row, col):
    for i in range(row):
        x = i-row
        y = q[i]-col
        if y < 0:
            x, y = -x, -y
        x += 41
        #print(x, y)
        if checkmap[42*x+y]:
            return False
    for i in range(row):
        x = i-row
        y = q[i]-col
        if y < 0:
            x, y = -x, -y
        x += 41
        #print(x, y)
        checkmap[42*x+y] += 1
    return True
 
def unupdatecheckmap(row, col):
    for i in range(row):
        x = i-row
        y = q[i]-col
        if y < 0:
            x, y = -x, -y
        x += 41
        #print(x, y)
        if checkmap[42*x+y]:
            checkmap[42*x+y] -= 1
        else:
            assert(0)
 
 
def valid(row, col):
    tmp = [False]*84*42
    for i in range(row):
        if q[i]==col:    # or abs(i-row)==abs(q[i]-col):
            return False
    return True
 
# https://blog.csdn.net/Hackbuteer1/article/details/6657109
def queen():
    global q
    for i in range(14):
        r = updatecheckmap(i, q[i])
        assert(r)
    i = 14
    j = 0
    while i < QUEEN:
        #print(i)
        while j < QUEEN:
            if valid(i,j) and updatecheckmap(i,j):
                q[i] = j
                j = 0
                break
            else:
                j += 1
        if q[i] == -10000:
            if i == 13:
                break
            else:
                i -= 1
                unupdatecheckmap(i, q[i])
                j = q[i]+1
                q[i] = -10000
                continue
        if i == QUEEN-1:
            return
        i += 1
 
chartable = '0123456789'+'ABCDEFGHIJKLMNOPQRSTUVWXYZ'+"".join(map(chr,[0x2b,0x2d,0x2a,0x2f,0x25,0x3d]))
 
partial = "02152S3X4Z5Q6C7T819/ADB%C*DL"
 
for i in range(14):
    q[i] = chartable.index(partial[2*i+1])
 
queen()
 
print(q)
 
answer = ""
for i in range(42):
    answer += chartable[i]
    answer += chartable[q[i]]
 
print(answer)

算法性能不高，cpython跑不出来，换用pypy3跑了17分钟才出答案

 

最终答案：

 

02152S3X4Z5Q6C7T819/ADB%C*DLEIFUG3HRIHJ6K7L0MBNKOJPPQ=RNS+TEUOVWWGXYYMZ9+4-8*F/-%V=A


[培训]二进制漏洞攻防（第3期）；满10人开班；模糊测试与工具使用二次开发；网络协议漏洞挖掘；Linux内核漏洞挖掘与利用；AOSP漏洞挖掘与利用；代码审计。

最后于 2021-5-19 00:30 被mb_mgodlfyn编辑 ，原因：
收藏
点赞・4
打赏
分享
最新回复 (0)
游客
登录 | 注册 方可回帖
　回帖　 表情 雪币赚取及消费
高级回复
返回