[原创]看雪.深信服 2021 KCTF 春季赛 第六题 寻回宝剑
source link: https://bbs.pediy.com/thread-267672.htm
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
IDA打开,发现代码加了混淆,但规律性很强。
解混淆是一个迭代的过程:
首先注意到一个反复出现的代码片段:
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指令)替换之后,程序里出现大量的
VIRTUAL push XXXXYYYY
ret
等同于一条无条件跳转指令
VIRTUAL jmp XXXXYYYY
对同一个寄存器连续的push和pop,可以直接去除
push AAA
pop AAA
push AAA
push BBB
pop BBB
pop AAA
对
VIRTUAL jmp
连接的代码块重新排序让它们顺序连在一起,从而省略掉无用的VIRTUAL jmp
指令。在完成这一步后,重做第3步。出现了一个新的模式(这个模式只有在前4步都做完之后才能看出来,因为这些指令在源程序中并不是连续的)
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步反复迭代以上的步骤,重点是指令块的重新排序(第4步),每次重新排序后再次搜索第1、2、3、5步的代码模式做替换。直到代码不再能化简,打印输出即可。
由于混淆模式非常固定,所以先用objdump工具获得反汇编:objdump -d -M intel KCTF.exe > KCTF_objdump.txt
,然后对字符串做操作。
(更好的方法应该使用Capstone这样的反汇编引擎,可惜不太熟悉)
代码如下:(与上面的步骤描述有少许不同,但主要思路是一致的)
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的输出)
-
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
-
;
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+-*/%=
-
;
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再加第二个数字
-
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个整数,要求严格单调递增
-
;
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个坐标,横纵交替)
-
;
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+前者,要求这个值不重复(实际上是要求,不存在位置相对值一样的点对)
-
;
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皇后,只不过斜线规则改成了更复杂的点对相对位置检查
求解:回溯法爆破(参考了网上的一段代码),修改了验证规则
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
[看雪官方培训] Unicorn Trace还原Ollvm算法!《安卓高级研修班》2021年6月班火热招生!!
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK