[推荐]2019 KCTF 总决赛 | 第三题《街机少年》点评及解题思路

发表于: 2019-12-11 18:41 3336

[推荐]2019 KCTF 总决赛 | 第三题《街机少年》点评及解题思路

Editor

2019-12-11 18:41

3336

第三道题《街机少年》历时2天，已于7号中午12点关闭攻击通道。共有1624人围观，最终共有8支团队攻破成功。

大众代表队的mb_ibocelll深夜发起攻击，拿到此题的一血，总用时约14小时。眼见攻破战队数越来越多，此题即将关闭，其他战队也毫不示弱，迎头赶上，Acehub战队和A2战队通宵破题，终于在7号凌晨成功破解，获得积分与前几位选手相差不大。

1、题目简介

历经一番唇舌之争，我终于完成了上场任务，还没等我仔细思考微型世界的奥秘，就来到了下一个环节。

环顾四周，我身处的场景不正是熟悉的拳皇吗？人物选择，自然是我最喜欢的八神庵了。

而对方则是成功复活的大蛇一族的最强黑暗力量主人：OROCHI！

生死一刻，凭借我印象中的街机招式究竟能否打败他，我并不能确定。
不过既然来了，也只好一战了。

攻破此题的战队排名一览：

进入游戏世界，将会如何发展？接下来我们一起来看一下这道题的点评和详细解析吧。

2、看雪评委crownless点评

这道题是一道游戏对战题，流程是：获取用户输入->转码->小游戏（对战AI）->出结果。

出题人通过数学方法，保证玩家有必胜解，且序列号有唯一性。这道题有四种解法，开放性和趣味性十足！

3、出题团队简介

本题出题战队兔斯基保护协会：

队长和全部队员就是：大龙猫，如果不算上兔斯基的话。

这只大龙猫不是普通的二次元生物，玩红警3能单挑四家凶残！

此次比赛，再次感谢老婆对我的大力支持，老婆永远是我的女神！

这次图片不秀兔斯基了，我要继续给老婆做好吃的：

4、设计思路

（本题目采用规则二）

题目架构：获取用户输入->转码->小游戏（对战AI）->出结果

难度声明：由VS2017编译链接无后续处理、没有使用虚拟机、没有使用反调试。

使用了 SetUnhandledExceptionFilter，是烟雾弹，加不加调试器都跑不到，不是反调试。

小游戏部分

本题的主体是一个小游戏——经典游戏捡石子。笔者小时候特别喜欢和同学玩这个游戏，现在笔者把这个游戏的玩法做成了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.

这里，“可作为必胜操作的堆”的判断逻辑也可做为破解者掌握必胜序列的入手点。“右侧是否有其它可用于必胜操作的堆”的判断我写的很隐晦，程序内的大数组就是干这个的，不然破解者就没必要去分析AI了。我觉得直接分析AI更加容易。

破解这部分有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，我用编程技巧进行了处理。

破解这部分有2条路可走：Path 1，识别出模幂运算，利用32以内离散对数逆向。Path 2，不识别什么运算，直接构造逆运算数组。（推荐）

总结

破解本程序，有好多方法。一款好游戏，常常是开放式的。在此致敬塞尔达传说和勇者斗恶龙！

5、解题思路

本题解题思路由7HxzZ战队的梅零落提供：

XYLearn tqllllll ! 7feilee tqllllll !

应该是非预期了。

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，而后走过一个判断，通过GAME函数返回值来判断是否正确。

首先读入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);

简单判断name和serial合法后decode并存入全局变量数组。

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扣下来：

1	`def` `func1(x, m):<br> s` `=` `x<br> none_primitive_root` `=0<br>` `for` `iin` `range(1, m):<br> y` `=` `min(x, s)<br> z` `=` `max(x, s)<br> s` `=` `y` `*` `y` `%17` `^ triangle_at(xor_table, y, z)<br>......`

根据返回值发现是一个乘方运算(取模意义下)，计算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]<br>    key_len = len(key)<br>    ch = username[0] %16 +1<br>    username = map_username(username,bytes_417188)<br>    primitive_root = quadratic_residues(ch,16)<br>    kidx =0<br>    x =5<br>    while kidx < key_len:<br>        key_low = key[kidx] %16 +1<br>        key_high = (key[kidx]>>4) %16 +1<br>        flag =1<br>        if primitive_rootand key_low <=16 and key_high <=16:<br>            flag =0<br>            key_low = _pow(primitive_root, key_low)<br>            r2 = quadratic_residues(key_low,16)<br>            key_high = _pow(r2, key_high)<br>            if flag:<br>                break<br>        primitive_root = quadratic_residues(key_high,16)<br>        primitive_flag = (key_high * bytes_396088[username[key_low -1] - key_high])&0xff<br>        for iin range(key_low,128):<br>            v4 = int(username[i] ==0)<br>            v5 = (((v4 + bytes_396188[get_idx(username[key_low -1], username[i], key_high)])%256) * primitive_flag)&0xff<br>            primitive_flag = (((v5 +1) & int(v5 !=0)) + v5)&0xff<br>        username[key_low -1] = (username[key_low -1] + ((((2 * ((primitive_flag +1) &1) -1)&0xff) * key_high)&0xff))&0xff<br>        #print("test xor is {}".format(reduce(lambda x, y: x ^ y, username)))<br>        if not primitive_flag:<br>            break<br>        if not any(username):<br>            return kidx == key_len -1<br>        key_low_ = (key[kidx] >>4) %16 +1<br>        key_high_ = key[kidx +1] %16 +1<br>        bytes_396088[key_low_ //2] = (bytes_396088[key_low_ //2] + key_high_) %127 +1<br>        kidx +=1<br>        tmp = unknown(username[2], username[1], username[0])<br>        tmp = unknown(username[4], username[3], tmp)<br>        tmp = unknown(username[6], username[5], tmp)<br>        tmp = unknown(username[8], username[7], tmp)<br>        tmp = unknown(username[10], username[9], tmp)<br>        tmp = unknown(username[12], username[11], tmp)<br>        tmp = unknown(username[14], username[13], tmp)<br>        if tmp:<br>            for iin range(15):<br>                val = bytes_3A7288[tmp | (username[i] <<4)]<br>                if val &1:<br>                    username[i] = val >>1<br>                    break<br>        else:<br>            print(kidx)<br>            fflag =0<br>            while True:<br>                if username[x] ==1:<br>                    username[x] = (username[x] -1)%256<br>                    x = (x +4) %15<br>                    fflag =1<br>                    break<br>                if username[x] >1:<br>                    break<br>                x = (x +4) %15<br>            if fflag ==0:<br>                username[x] = username[x] - ((x * x +1) % username[x] +1)<br>                x = (x +4) %15<br>        if not reduce(lambda x, y: x | y, username):<br>            break<br>    return False

在循环过程中，每轮12bit key参与运算，首先根据第一步结果进行乘方，再进行一次求非平方剩余，再进行一次乘方(不出现单位元)，根据结果及一个数组操作更新一位username数组，而后进行一轮变换(unknown)，根据变换结果更新一位username。

通过观察数组及结果发现unknown操作是进行一组异或。

若异或后不为0则依赖第二个数组将其每位异或结果调整为0。

通过观察正确序列号发现：

1	`正确退出应该是循环过每一位序列号经由最后: 判断username数组变换为0时根据"循环次数==序列号长度-1"来return<br>在正确序列号变换下经由unknow变换的tmp值每轮都是0（即username数组每一位异或后为0）`

其实到这里也没猜到具体的数学背景是什么，最开始肖神通过unknown中变换的数组搜索到AES的add field，不过后来发现只是一组异或，遂失败。

不过从上面分析可以看到，每轮参与计算的只有12bit，而且通过正确序列号的程序流可以猜测到每一轮tmp=0即为控制条件，以此进行逐位爆破即可得到可能解。
最后肖神用unicorn成功解出(tqlll !!!)(python爆破我写得有点问题没搞定(飞神那边应该快改好了，已经出了几位))：

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

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@dBWnwvyppwIpswIygxJzz