-
-
[推荐]2019 KCTF 总决赛 | 第三题《街机少年》点评及解题思路
-
发表于: 2019-12-11 18:41
-
大众代表队的mb_ibocelll深夜发起攻击，拿到此题的一血，总用时约14小时。眼见攻破战队数越来越多，此题即将关闭，其他战队也毫不示弱，迎头赶上，Acehub战队和A2战队通宵破题，终于在7号凌晨成功破解，获得积分与前几位选手相差不大。
1、题目简介
历经一番唇舌之争，我终于完成了上场任务，还没等我仔细思考微型世界的奥秘，就来到了下一个环节。
环顾四周，我身处的场景不正是熟悉的拳皇吗？人物选择，自然是我最喜欢的八神庵了。
而对方则是成功复活的大蛇一族的最强黑暗力量主人：OROCHI！
生死一刻，凭借我印象中的街机招式究竟能否打败他，我并不能确定。
不过既然来了，也只好一战了。
攻破此题的战队排名一览：
2、看雪评委crownless点评
出题人通过数学方法，保证玩家有必胜解，且序列号有唯一性。这道题有四种解法，开放性和趣味性十足！
3、出题团队简介
队长和全部队员就是：大龙猫，如果不算上兔斯基的话。
这只大龙猫不是普通的二次元生物，玩红警3能单挑四家凶残！
此次比赛，再次感谢老婆对我的大力支持，老婆永远是我的女神！
这次图片不秀兔斯基了，我要继续给老婆做好吃的：
4、设计思路
小游戏部分
本题的主体是一个小游戏——经典游戏捡石子。笔者小时候特别喜欢和同学玩这个游戏，现在笔者把这个游戏的玩法做成了AI。（鉴于AI就在程序里，破解者如果自己没有发现制胜方法，也可以把AI逆了，得到必胜玩法）
捡石子规则如下：
1）有n堆石子，对于我的程序来说，我设置了15堆石子，是个数组。此数组由用户名参与初始化，来实现用户名/游戏的多样性。（用户名只用在两个地方，一个是这里，另一处是用用户名的第一字节参与初始化了一个字符转换算法的底数，下文“转码部分”会再次提到）
2）玩家和AI轮流拿走其中一些石子，每次只能从其中一堆石子中拿，拿走的数量至少是1，最多可以把这堆拿空，但不能拿成负数。在此限制下，拿哪堆拿多少任意。
3）谁把最后一堆石子拿空，谁赢。（AI赢自然就是玩家输了，玩家都输了我就赢了，哈哈哈哈）
比如，有石子量为 3，4 的两堆石子。玩家操作后，变成 1，4 两堆。AI 操作后变成 1，1 两堆。玩家操作后，又变成 0，1 两堆。最后 AI 操作，变成 0，0两堆，AI胜！
怎么保证唯一解呢？数学上可以证明，如果拿其中某一堆石子能保证胜利，那么拿这堆其它数量的石子，则是把必胜的地位交给对方。对于人类来说，可以寄希望于对方失误。
而我的AI一旦拿到必胜的机会，绝不会失去。由此可见必胜操作序列由操作的堆序号来决定，因为对序号决定了操作数量。那么我规定人类玩家必须以可作为必胜操作的堆中最右侧（序号最大）的堆作为操作对象，其它都是违规。那么就保证了对序号的序列唯一性，进而保证了不存在多解。
我的AI是左优先，与用户相反，所以破解者需要真正破解AI，而不能简单的修改程序流让AI对战直接出Key.
破解这部分有4条路可走：Path 1，逆向AI。不用自研算法。Path 2，把AI修改成右优先，让AI对战。不用自研算法，也不用彻底逆向AI。（推荐）Path 3，自研算法，破解者只需要针对KCTF用户这一个特殊的场景得出解即可。（有效，但不好玩）Path 4，自研通用算法，自写AI，不用逆向AI。（推荐）
转码部分
转码部分分为两个部分，第一部分纯粹为了把用户输入转变为二进制数组，采用的是base64算法的变体。除了正文对应是变体之外，为了避免多解翻车，尾部转码是特殊的。
第二部分是为了增加破解难度的转码。通过用户名第一字节初始化base。假设此步转码前是A，转码后是B，用 B = pow(base, A) % p（p为素数） 来完成 A -> B 的转换（费尔马小定理）。由于 A，B，p都小于32。离散对数可轻易求出。每次转码后更新base.这部分特征太明显，为了抵抗IDA，我用编程技巧进行了处理。
总结
破解本程序，有好多方法。一款好游戏，常常是开放式的。在此致敬塞尔达传说和勇者斗恶龙！
5、解题思路
应该是非预期了。
IDA载入程序，看到主程序：
if ( get_input() )
{
SetUnhandledExceptionFilter(TopLevelExceptionFilter);
if ( GAME((unsigned __int8 *)name, name_len) )
output("You Win! You are very clever!");
else
output("Game Over");
system("pause");
result =0;
}
else
{
output("Game Over");
system("pause");
result =0;
}
首先读入name和serial：
for ( i =0; i <32; ++i )
{
v4 = read_input();
if ( (v4 <97 || v4 >122) && (v4 <65 || v4 >90) && (v4 <48 || v4 >57) )
{
if ( v4 !=13 && v4 !=10 )
return 0;
name_len = i;
break;
}
name[i] = v4;
}
if ( name_len <4 || name_len >16 )
return 0;
output("Please input your KEY: ( : to z )");
for ( j =0; j <128; ++j )
{
v3 = read_input();
if ( v3 <':' || v3 >'z' )
{
if ( v3 !=13 && v3 !=10 )
return 0;
serial_len = j;
break;
}
serial[j] = v3;
}
if ( !serial_len|| serial_len >128 )
return 0;
dec_len = dec1((int)decode_serial, (int)serial, serial_len);
decode类似一个base64，只是对应处理位不同，直接对照求逆即可：
def dec1(str1):
ans=[]
for iin range(len(str1)/3):
ans.append(ord(str1[i*3])>>2)
ans.append(((ord(str1[i*3])&0b11)<<4)+((ord(str1[i*3+1])&0b11110000)>>4))
ans.append((ord(str1[i*3+1])&0b1111)+((ord(str1[i*3+2])&0b11000000)>>2))
ans.append(ord(str1[i*3+2])&0b00111111)
s=""
for iin ans:
s+=chr(i+ord(":"))
return s
#后面不足对应相同位置并补'z'即可
在GAME中，首先使用大量数组查表隐藏了算法和计算过程：
首先将第一轮table扣下来：
def func1(x, m):
s = x
none_primitive_root =0
for iin range(1, m):
y = min(x, s)
z = max(x, s)
s = y * y %17 ^ triangle_at(xor_table, y, z)
......
根据返回值发现是一个乘方运算(取模意义下)，计算pow(x,m)
故而在第一层：
for ( i =1; i <16; ++i )
{
v35 = v38;
v27 = v51;
if ( v38 > (signed int)v51 )
{
v35 = v51;// 乘方
v27 = v38;
}
v38 = v35 * v35 %17 ^ table[(unsigned __int8)(v27 + (v35 -1) * (34 - v35) /2 - v35)];
if ( v38 ==1 && i !=15 )// (p-1)/2不满足
{
v51 = (v51 +1) %16 +1;
v38 =0;
break;
}
}
其实际计算的是相对v51步长2的模17下最近的非二次剩余。
而后其根据输入name初始化了一个256长度数组（前16参与运算）。
而后大致流程可以取下：
from base64import b64decode,b64encode
import os
from functoolsimport reduce
xor_table = [0,3,2,5,4,7,6,9,8,11,10,13,12,15,14,17,0,2,12,14,8,10,20,5,7,1,3,13,15,9,11,0,5,6,8,13,14,3,4,25,11,12,1,2,7,0,19,23,27,31,18,22,26,30,17,21,25,29,0,5,9,14,3,24,12,1,6,10,15,4,0,10,12,1,11,13,6,8,18,7,9,0,10,3,13,6,31,9,2,12,5,0,9,1,14,6,15,7,12,4,0,8,3,11,2,10,29,5,0,7,14,4,11,1,8,0,15,5,3,14,4,0,11,7,2,13,0,28,24,20,0,15,10,0,6,0]
with open('E:/Totoro.exe','rb')as f:
f.seek(0x16088, os.SEEK_SET)
bytes_397288 = f.read(65536)
bytes_397288 = [ifor iin bytes_397288]
f.seek(0x26088, os.SEEK_SET)
bytes_3A7288 = f.read(256)
bytes_3A7288 = [ifor iin bytes_3A7288]
f.seek(0x14E88, os.SEEK_SET)
bytes_396088 = f.read(256)
bytes_396088 = [ifor iin bytes_396088]
f.seek(0x14F88, os.SEEK_SET)
bytes_396188 = f.read(4096)
bytes_396188 = [ifor iin bytes_396188]
f.seek(0x15F88, os.SEEK_SET)
bytes_417188 = f.read(256)
bytes_417188 = [ifor iin bytes_417188]
def quadratic_residues(x, m):
while True:
s = x
for iin range(1, m):
y = s
z = x
if s > x:
y = x
z = s
idx = (z + (y -1) * (34 - y) //2 - y)%256
s = (y * y %17) ^ xor_table[idx]
if s ==1 and i !=15:
x = (x +1) %16 +1
s =0
break
if s ==1:
break
return x
def _pow(x, m):
s = x
global flag
for iin range(1, m):
y = s
z = x
if s > x:
y = x
z = s
idx = (z + (y -1) * (34 - y) //2 - y)%256
s = (y * y %17) ^ xor_table[idx]
if s ==1 and i !=15:
flag =1
return s
def triangle_index(y, z):
return z + (y -1) * (34 - y) //2 - y
def triangle_at(mat, y, z):
return mat[triangle_index(y, z)]
def get_inv(x):
while True:
s = x
for iin range(1,16):
y = min(x, s)
z = max(x, s)
s = y * y %17 ^ triangle_at(xor_table, y, z)
if s ==1 and i !=16 -1:
x = (x +1) %16 +1
s =0
break
if s ==1:
break
return x
def pows(x, m):
s = x
none_primitive_root =0
for iin range(1, m):
y = min(x, s)
z = max(x, s)
s = y * y %17 ^ triangle_at(xor_table, y, z)
if s ==1 and i != m-1:
none_primitive_root =1
return s,none_primitive_root
def map_username(username,bytes_417188):
for iin range(len(username) -1):
ch = username[i +1]
if i >=7:
if i >=10:
if i >=13:
bytes_417188[i] = ch %8 +8
else:
bytes_417188[i] =7 - ch %7
else:
bytes_417188[i] = ch %8 +8
else:
bytes_417188[i] =7 - ch %7
return bytes_417188
def get_idx(a, b, c):
lo = ((b >>2) ^ ((c <<4) &0xC0)) ^ ((a <<2) &0x3C) ^0xC7
hi = (c &3) ^ ((b <<2) &0xf) ^2
x = lo | (hi <<8)
return x
def unknown(a, b, c):
'''a^b^c'''
return bytes_397288[((a + b + c) %16) | (a <<4) | (b <<8) | (c <<12)]
def check(username, key):
#key= [61, 136, 200, 67, 168, 249, 66, 246, 42, 33, 212, 253, 243, 246, 246, 244, 246, 249, 244, 255, 237]
key_len = len(key)
ch = username[0] %16 +1
username = map_username(username,bytes_417188)
primitive_root = quadratic_residues(ch,16)
kidx =0
x =5
while kidx < key_len:
key_low = key[kidx] %16 +1
key_high = (key[kidx]>>4) %16 +1
flag =1
if primitive_rootand key_low <=16 and key_high <=16:
flag =0
key_low = _pow(primitive_root, key_low)
r2 = quadratic_residues(key_low,16)
key_high = _pow(r2, key_high)
if flag:
break
primitive_root = quadratic_residues(key_high,16)
primitive_flag = (key_high * bytes_396088[username[key_low -1] - key_high])&0xff
for iin range(key_low,128):
v4 = int(username[i] ==0)
v5 = (((v4 + bytes_396188[get_idx(username[key_low -1], username[i], key_high)])%256) * primitive_flag)&0xff
primitive_flag = (((v5 +1) & int(v5 !=0)) + v5)&0xff
username[key_low -1] = (username[key_low -1] + ((((2 * ((primitive_flag +1) &1) -1)&0xff) * key_high)&0xff))&0xff
#print("test xor is {}".format(reduce(lambda x, y: x ^ y, username)))
if not primitive_flag:
break
if not any(username):
return kidx == key_len -1
key_low_ = (key[kidx] >>4) %16 +1
key_high_ = key[kidx +1] %16 +1
bytes_396088[key_low_ //2] = (bytes_396088[key_low_ //2] + key_high_) %127 +1
kidx +=1
tmp = unknown(username[2], username[1], username[0])
tmp = unknown(username[4], username[3], tmp)
tmp = unknown(username[6], username[5], tmp)
tmp = unknown(username[8], username[7], tmp)
tmp = unknown(username[10], username[9], tmp)
tmp = unknown(username[12], username[11], tmp)
tmp = unknown(username[14], username[13], tmp)
if tmp:
for iin range(15):
val = bytes_3A7288[tmp | (username[i] <<4)]
if val &1:
username[i] = val >>1
break
else:
print(kidx)
fflag =0
while True:
if username[x] ==1:
username[x] = (username[x] -1)%256
x = (x +4) %15
fflag =1
break
if username[x] >1:
break
x = (x +4) %15
if fflag ==0:
username[x] = username[x] - ((x * x +1) % username[x] +1)
x = (x +4) %15
if not reduce(lambda x, y: x | y, username):
break
return False
在循环过程中，每轮12bit key参与运算，首先根据第一步结果进行乘方，再进行一次求非平方剩余，再进行一次乘方(不出现单位元)，根据结果及一个数组操作更新一位username数组，而后进行一轮变换(unknown)，根据变换结果更新一位username。
通过观察数组及结果发现unknown操作是进行一组异或。
若异或后不为0则依赖第二个数组将其每位异或结果调整为0。
通过观察正确序列号发现：
正确退出应该是循环过每一位序列号经由最后: 判断username数组变换为0时 根据"循环次数==序列号长度-1"来return
在正确序列号变换下经由unknow变换的tmp值每轮都是0（即username数组每一位异或后为0）
其实到这里也没猜到具体的数学背景是什么，最开始肖神通过unknown中变换的数组搜索到AES的add field，不过后来发现只是一组异或，遂失败。
不过从上面分析可以看到，每轮参与计算的只有12bit，而且通过正确序列号的程序流可以猜测到每一轮tmp=0即为控制条件，以此进行逐位爆破即可得到可能解。
最后肖神用unicorn成功解出(tqlll !!!)(python爆破我写得有点问题没搞定(飞神那边应该快改好了，已经出了几位))：
import sys
import os
import struct
from base64 import b64decode, b64encode
from capstone import *
from capstone.x86_const import *
from unicorn import *
from unicorn.x86_const import *
def p32(n):
return struct.pack("<I", n)
to = b'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/'
base = b':;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxy'
def base64_enc(data):
data = b64encode(data)
res = []
for i in data:
res.append(base[to.index(i)])
return ("".join([chr(i) for i in res])).encode()
def base64_dec(data):
res = []
for i in data:
res.append(to[base.index(i)])
return b64decode("".join([chr(i) for i in res]).encode())
cs = Cs(CS_ARCH_X86, CS_MODE_32)
last_addr = 0
def hook_code(mu, addr, size, user_data):
global last_addr
last_addr = addr
code = mu.mem_read(addr, 10)
ins = next(cs.disasm(code, addr, 1))
disasm = "{:08x}: {} {}".format(addr, ins.mnemonic, ins.op_str)
print(disasm)
mu = None
with open("./Totoro.exe", 'rb') as f:
f.seek(0x400, os.SEEK_SET)
text = f.read(0xf13b - 0x400)
f.seek(0xf320, os.SEEK_SET)
rdata = f.read(0x14c68 - 0xf320)
f.seek(0x14E00, os.SEEK_SET)
data = f.read(0x26C00-0x14E00)
def check(username, key, addr_points=None):
global mu
mu = Uc(UC_ARCH_X86, UC_MODE_32)
text_start , text_end = 0x401000, 0x410000
idata_start, idata_end = 0x410000, 0x410120
rdata_start, rdata_end = 0x410120, 0x416000
data_start , data_end = 0x416000, 0x429000
stack_start, stack_end = 0x7ffa0000, 0x80000000
cache_start, cache_end = 0x100000, 0x110000
stack_curr = 0x7fff0000
mu.mem_map(text_start, data_end - text_start)
mu.mem_write(text_start, text)
mu.mem_write(rdata_start, rdata)
mu.mem_write(data_start, data)
mu.mem_map(stack_start, stack_end - stack_start)
mu.mem_map(cache_start, cache_end - cache_start)
mu.reg_write(UC_X86_REG_ESP, stack_curr)
# key
key_addr = 0x427E38
key_len_addr = 0x427F38
mu.mem_write(key_addr, key)
mu.mem_write(key_addr + len(key), b'\0' * (256 - len(key)))
mu.mem_write(key_len_addr, p32(len(key)))
# username
mu.mem_write(stack_curr + 4, p32(cache_start))
mu.mem_write(cache_start, username)
mu.mem_write(stack_curr + 8, p32(len(username)))
# hook
# mu.hook_add(UC_HOOK_CODE, hook_code)
# execute
check_addr = 0x401480
check_ret_addr = 0x402088
try:
if not addr_points:
mu.emu_start(check_addr, check_ret_addr)
else:
start = check_addr
for addr in addr_points:
mu.emu_start(start, addr)
mu.emu_start(addr, 0, count=1)
start = mu.reg_read(UC_X86_REG_EIP)
except UcError as e:
return False
return True
username = b'KCTF'
key = [0 for i in range(0x20)]
# key = [61, 136, 200, 67, 168, 249, 66, 246, 42, 33, 212, 253, 243, 246, 246, 244, 246, 249, 244, 255, 237, 249]
end = False
for i in range(21):
for ch in range(256):
key[i] = ch
if not check(username, bytes(key), [0x401F00] * (i+1)):
continue
if mu.reg_read(UC_X86_REG_EAX) == 0:
print(i, ch)
break
key[i] = 0x100
if key[i] == 0x100:
break
i += 1
for ch in range(256):
key[i] = ch
if not check(username, bytes(key)):
continue
if mu.reg_read(UC_X86_REG_EAX) == 0:
print(i, ch)
break
print(key)
#Output:[61, 136, 200, 67, 168, 249, 66, 246, 42, 33, 212, 253, 243, 246, 246, 244, 246, 249, 244, 255, 237, 249]
-------------------------------------------------------------------------------
def dec1(str1):
ans=[]
for i in range(len(str1)/3):
ans.append(ord(str1[i*3])>>2)
ans.append(((ord(str1[i*3])&0b11)<<4)+((ord(str1[i*3+1])&0b11110000)>>4))
ans.append((ord(str1[i*3+1])&0b1111)+((ord(str1[i*3+2])&0b11000000)>>2))
ans.append(ord(str1[i*3+2])&0b00111111)
ans.append(ord(str1[21])>>2)
ans.append((ord(str1[21])&0b11)<<4)
s=""
for i in ans:
s+=chr(i+ord(":"))
return s+"zz"
s=""
final_key=[61, 136, 200, 67, 168, 249, 66, 246, 42, 33, 212, 253, 243, 246, 246, 244, 246, 249, 244, 255, 237, 249]
for i in final_key:
s+=chr(i)
print dec1(s)
#Output:IRrBJtrsJi@dBWnwvyppwIpswIygxJzzEND
[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课
最后于 2019-12-31 15:44
被kanxue编辑
，原因：
|
|
|---|---|
