强网杯S8
mips #
Someone has found the mips binary, along with an emulator to execute it. What can you find in them?
USAGE：./emu ./mips_bin
32 位大端 mips 程序，拖到 IDA 里即可
程序会在 0x23000 处开辟一个可执行空间，写入解密的机器码，然后执行
这样得到的 flag 是 flag{dynamic_reverse}，是个假的 flag，交不上
一开始的想法是 emu 在加载时动态修改了程序，故修补程序使之在结束时打印字节码的内容，没有收获，但有个意外发现：在跳到 0x23000 前的 write 函数可以调用成功，之后的所有 patch 全都失效了
所以推测是 emu 在 0x23000 或那条 if 语句处下了钩子
IDA 打开 emu 直接搜索 0x23000 立即数
定位到 hook 的地方，这里有一个独立的检测，对 encrypt 的参数下交叉引用可以找到检测 flag 前缀的代码，推测出参数就是输入
encrypt 函数是一个稍微有点绕的魔改 RC4，KSA 部分使用乘以常数来优化了除法，实际上 KSA 和标准实现一致（见注释），PRGA 也一致，只是最后的加密多做了一些 XOR
在不同比特位置上异或不同常量依旧是双射，虽然可以写逆函数，但更快的方法是打表反向查找
唯一不能确定的是 dword_C32324，不过也不需要确定，直接根据明文是否可读来爆破，实践下来为 10，交叉引用显示这个变量和调试器检测有关
import numpy as np
inv1 = np.zeros(256, dtype=np.uint8)
inv2 = np.zeros(256, dtype=np.uint8)
def f(x):
x = np.uint8(x)
return ((((x << 7) | (x >> 1)) << 6) ^ 0xC0 | (((x << 7) | (x >> 1)) >> 2) ^ 0x3B) ^ 0xBE
def g(x):
v3 = np.uint8(x)
return (((((16 * (((32 * v3) | (v3 >> 3)) ^ 0xAD)) | ((((32 * v3) | (v3 >> 3)) ^ 0xAD) >> 4)) ^ 0xDE) >> 5) | (8 * (((16 * (((32 * v3) | (v3 >> 3)) ^ 0xAD)) | ((((32 * v3) | (v3 >> 3)) ^ 0xAD) >> 4)) ^ 0xDE)))
for i in range(256):
inv1[f(i)]=i
inv2[g(i)]=i
key1 = b'6105t3'
key2 = b'\xDE\xAD\xBE\xEF'
def rc4_ksa(key):
sbox = bytearray(range(256))
j = 0
for i in range(256):
j = (j + sbox[i] + key[i % len(key)]) % 256
sbox[i], sbox[j] = sbox[j], sbox[i]
return sbox
def rc4_prga(sbox, length=0x1000):
i = j = 0
for _ in range(length):
i = (i + 1) % 256
j = (j + sbox[i]) % 256
sbox[i], sbox[j] = sbox[j], sbox[i]
yield sbox[(sbox[i] + sbox[j]) % 256]
s = [0xC4, 0xEE, 0x3C, 0x0BB, 0x0E7, 0x0FD, 0x67, 0x1D, 0x0F8, 0x97,
0x68, 0x9D, 0x0B, 0x7F, 0x0C7, 0x80, 0x0DF, 0x0F9, 0x4B, 0x0A0,
0x46, 0x91]
s[12],s[16] = s[16], s[12]
s[7],s[11] = s[11], s[7]
sbox = rc4_ksa(key1)
prng = rc4_prga(sbox)
flag = []
for i in range(len(s)):
a = next(prng)
b = key2[i & 3]
c = s[i] ^ 10 ^ a ^ b
c = inv2[c]
c = inv1[c]
flag.append(c)
print(bytes(flag))
#QeMu_r3v3rs3in9_h@ck6}
remem #
静态链接，先找 ubuntu libc 借一下符号
main 函数里的 while + switch 可以看到明显的虚机取指逻辑
不过这题的派发函数很奇怪，是动态生成机器码来执行的
具体来说，是准备好了 x64 的指令模板，然后往里填寄存器，通过 Capstone 反汇编可以看出 rbp 是 5 号，rsp 4 号，rax 0 号，rbx 则是 3 号，还有一些指令是编码在字节码里的
观察几个比较复杂的派发函数可以知道，虚机由两个栈组成，一个用于计算，一个用于存储结果，还有一个输入队列，由用户输入扩展而成，调用号 0xf7 就是从队列取数压到计算栈上
简单反汇编字节码可以看出，所有的硬编码寄存器无外乎 rax 和 rbx，并且所有的 XOR 动作都在最后，只为了把结果栈上的所有值和一组预先定义的常数全部 XOR 在一起和 0 比较
这是个纯计算型虚机，因此可以重写解释器并在解释的过程中添加约束，实现上要注意调用号 0xf2 如果次字节为 0，则是乘方运算，否则就是从一个预先生成的队列里取数做乘法
import struct
code = b""
insn = []
temp = []
for i in range(0, len(code), 4):
a = struct.unpack("<I", code[i : i + 4])[0]
if a >= 0xF0 and len(temp) != 0:
insn.append(temp)
temp = []
temp.append(a)
else:
insn.append(temp)
packed = []
p=0x5E2F4391
_R = PolynomialRing(GF(p), 'x', 5)
x = _R.gens()
for i in range(5):
packed.append(x[i])
packed.extend(
[0x5E2F4391, 0x42DB9F06, 0x35368926, 0x509A3978, 0x1EBFA92F, 0x555CC98C])
xor_idx = 6
feed = [
packed[0], packed[0], packed[1],
packed[1], packed[0], packed[1],
packed[0], packed[0], packed[2],
packed[2], packed[3], packed[2],
packed[3], packed[3], packed[4],
packed[4], 0, 0
]
feed_idx = 1
table = [
3, packed[1], 6,
82, 6, 2,
13, 17, packed[2],
5, 5, 88,
packed[2], 4, 5,
232, 35, 8, 16
]
table_idx = 0
stackA = []
stackB = []
temp = packed[0]
mask = (1 << 64) - 1
f = []
for i in insn:
if i[0] == 240:
tos = stackA.pop()
tos1 = stackA.pop()
stackA.append(tos1 + tos)
elif i[0] == 241:
tos = stackA.pop()
tos1 = stackA.pop()
stackA.append(tos - tos1)
elif i[0] == 242:
if i[1] == 0:
temp *= temp
else:
temp *= table[table_idx]
table_idx += 1
elif i[0] == 243:
f.append(stackB.pop() - packed[xor_idx])
xor_idx += 1
elif i[0] == 245:
temp = temp & stackA.pop()
elif i[0] == 246:
#stackB.append(stackA.pop() % packed[5])
stackB.append(stackA.pop())
elif i[0] == 247:
stackA.append(temp)
temp = feed[feed_idx]
feed_idx += 1
elif i[0] == 248:
pass
# print("check temp")
else:
print("what??")
raise Exception()
print(f)
PS: z3 不是一个好的选择，因为乘方和变量乘法使得约束不再是线性的了
得到一组模 p 意义下的约束（这里出题人还是挺善良的，全部异或在一起其实常数和式子是可以不按照顺序给的）
$$ \begin{cases} \begin{aligned} -3x_0^2 + 6x_0x_1 + 88x_1 + 458466443 = 0 \newline 2x_0^2 + 17x_0 + 13x_1 + 687389291 = 0 \newline -5x_0x_2 + 5x_2^2 + 88x_2 + 227871257 = 0 \newline 5x_2^2 - 4x_2x_3 + 232x_3 - 515877167 = 0 \newline -35x_3^2 + 16x_4^2 + 8x_4 + 148011525 = 0 \end{aligned} \end{cases} $$
将前两个式子看作 $x_1$ 的表达式，令它们的 Sylvester 矩阵行列式为 0，即可消元得到 $x_0$，后面式子同理
要注意解也是模 p 的，验证解需要看情况加上 p 再看是否是可读字符组合
g=f[1].sylvester_matrix(f[0], x[1]).det().univariate_polynomial()
g.roots()
x0=862152290
bytes.fromhex(hex(x0)[2:])
g=f[1](x0,*x[1:]).univariate_polynomial()
g.roots()
x1=53932501+p
bytes.fromhex(hex(x1)[2:])
g=f[2](x0,*x[1:]).univariate_polynomial()
g.roots()
x2=962670904
bytes.fromhex(hex(x2)[2:])
g=f[3](x[0],x[1],x2,x[3],x[4]).univariate_polynomial()
g.roots()
x3=859320929
bytes.fromhex(hex(x3)[2:])
g=f[4](x[0],x[1],x[2],x3,x[4]).univariate_polynomial()
g.roots()
x4=50524140+p
bytes.fromhex(hex(x4)[2:])
#flag{3cfbaf5f9a18382aa23}
斯内克 #
我不希望我的蛇被人捡到能直接使用。
Hint: 赛题附件已更新，总体算法并未修改。对于解决此赛题，需关注以下内容：
1. 需要选手的操作序列最短
2. 赛题内设用于触发验证的轮次减少
3. 选手可忽略由蛇的身体长度引起的可能
蛇要最优走好每一步；蛇不应该直接调头 (如当蛇往右走时，不能直接转变方向为左)，否则会咬伤自己。
main 函数可以看到贪吃蛇主循环
一个快速推断结构体和全局变量的方式是看 draw 函数对它们的处理，容易知道，蛇的初始点为 (10, 10)，地图大小为 20x20，食物由假随机（种子 0xdeadbeef）生成，此外，游戏还填充一段可写可执行的内存 xbuf
在帧函数中可以看到游戏逻辑，吃到食物有特殊处理：如果 xbuf 通过了 md5 校验，则以 nickname 为参数执行之（md5 的常数很明显）
在 read_inputs 处可以看到转向的代码，根据不同的方向，转向时会对 xbuf 进行不同的修改，方向可从帧函数得出
根据题目要求，蛇总以最优路线前进且可以忽略身体碰撞，这意味着蛇的路线是基本确定的，找到路线就可以沿途寻找触发代码
伪随机可以预先确定，找到下一跳后根据蛇头方向分情况讨论，以东向为例子：
如果 diffX 为正或 0，则转向（与否）取决于 diffY；如果 diffX 为负且 diffY 不为 0，先朝 diffY 方向转，再朝西转；最麻烦的情况是 diffX 为负且 diffY 为 0 的情况，有两种可能性，即先向南或北方向转，再向西转，最后向北或南方向转回
考虑到最麻烦的情况有两种可能性，这里选用 dfs + 栈，将初始点和食物点算作节点，栈上存储蛇到节点时的方向、分数（用来确定下一跳）以及 xbuf
本质上这应该还是个迷宫问题
from hashlib import md5
from http.client import UPGRADE_REQUIRED
checkpoints = [[17, 0], [12, 10], [3, 11], [15, 9], [13, 18], [4, 10], [12, 10], [14, 16], [3, 7], [19, 14], [10, 11], [0, 15], [16, 11], [0, 16], [13, 3], [17, 12], [15, 3], [16, 14], [3, 19], [13, 17], [18, 9], [10, 17], [9, 8], [12, 4], [6, 3], [3, 11], [3, 6], [16, 5], [0, 1], [7, 4], [16, 10], [13, 7], [4, 19], [10, 8], [4, 13], [0, 12], [6, 15], [16, 7], [16, 6], [5, 16], [0, 9], [1, 12], [10, 12], [2, 9], [10, 8], [6, 15], [18, 13], [19, 10], [10, 0], [18, 11], [6, 4], [17, 12], [12, 19], [10, 9], [14, 4], [2, 16], [2, 3], [18, 15], [5, 14], [8, 4], [1, 15], [10, 13], [15, 4], [18, 1], [11, 9], [1, 19], [16, 16], [6, 14], [15, 1], [1, 13], [11, 13], [5, 4], [0, 13], [13, 18], [17, 7], [14, 4], [10, 12], [10, 6], [2, 18], [15, 9], [8, 7], [6, 4], [4, 7], [18, 3], [8, 18], [16, 1], [15, 14], [9, 16], [2, 4], [10, 3], [6, 13], [10, 3], [17, 11], [6, 2], [8, 19], [8, 16], [16, 9], [18, 6], [16, 10], [13, 17],]
start = [10, 10]
target = b'\x9c\x06\xc0\x8f\x88-y\x81\xe9\x1df3d\xce^.'
fp = open("dump.bin", "rb")
xbuf = fp.read()
xbuf = list(xbuf)
fp.close()
buflen = len(xbuf)
assert(buflen == 1152)
def incX(buf, rep=1):
return [(b + 30 * rep) & 0xff for b in buf]
def incY(buf, rep=1):
r = (5 * rep) % 8
return [((b >> r) & 0xff) | ((b << (8 - r)) & 0xff) for b in buf]
def decX(buf, rep=1):
newbuf = buf.copy()
for i in range(buflen):
newbuf[i] = buf[(i + 6 * rep) % buflen]
return newbuf
def decY(buf, rep=1):
return [(b - 102*rep) & 0xff for b in buf]
EAST=incX
WEST=decX
NORTH=decY
SOUTH=incY
def get_rel(diffX, diffY):
assert diffX != 0 or diffY != 0
result = []
if diffX > 0:
result.append(EAST)
elif diffX < 0:
result.append(WEST)
else:
result.append(None)
if diffY > 0:
result.append(SOUTH)
elif diffY < 0:
result.append(NORTH)
else:
result.append(None)
return result
def calc(max_depth=10):
stack = [[start, EAST, xbuf, 0], ]
while len(stack) > 0:
at, towards, buf, depth = stack.pop()
if depth > 0:
digest = md5(bytes(buf)).digest()
#print(digest)
if digest == target:
print(f"found at depth {depth}")
fq = open("code.bin", "wb")
fq.write(bytes(buf))
fq.close()
break
if depth >= max_depth:
continue
dest = checkpoints[depth]
diffX = dest[0] - at[0]
diffY = dest[1] - at[1]
relX, relY = get_rel(diffX, diffY)
if towards is EAST or towards is WEST:
if relX is None:
buf = relY(buf)
stack.append([dest, relY, buf, depth+1])
elif towards is relX:
if relY is None:
stack.append([dest, towards, buf, depth+1])
else:
buf = relY(buf)
stack.append([dest, relY, buf, depth+1])
else: # opposite
if relY is None: # most complicated case
buf1 = SOUTH(relX(NORTH(buf)))
stack.append([dest, SOUTH, buf1, depth+1])
buf2 = NORTH(relX(SOUTH(buf)))
stack.append([dest, NORTH, buf2, depth+1])
else:
buf = relY(buf)
buf = relX(buf)
stack.append([dest, relX, buf, depth+1])
else:
if relY is None:
buf = relX(buf)
stack.append([dest, relX, buf, depth+1])
elif towards is relY:
if relX is None:
stack.append([dest, towards, buf, depth+1])
else:
buf = relX(buf)
stack.append([dest, relX, buf, depth+1])
else: # opposite
if relX is None:
buf1 = EAST(relY(WEST(buf)))
stack.append([dest, EAST, buf1, depth+1])
buf2 = WEST(relY(EAST(buf)))
stack.append([dest, WEST, buf2, depth+1])
else:
buf = relX(buf)
buf = relY(buf)
stack.append([dest, relY, buf, depth+1])
calc(50)
最后得到触发代码，是一个魔改的 TEA，解密即可
flag{G0@d_Snake}