Nonsense
最近事情有点多，一些比赛的赛后 Writeup 都没有时间整理。工作日大部分时间都在复现分析链上的合约攻击事件，周末得闲才会看一看 CTF 相关的东西，比赛的参与程度也被迫降低了，不然年纪大了身体恢复不过来 ;)
话说回来，TCTF RisingStar 2022 Final 和 0CTF/TCTF 2023 接连举办，往返杭州上海连轴转，有那么一点“极限挑战”的味道了。
Solution
由于没有高强度做题，这次比赛只认真研究了一下 Parsing 这道题目。题目下载链接
简而言之，这是一道另类迷宫题目，出题人用 rust 的 nom 模块实现了一个 flag 检查器。题目中有很多形如 t_0ctf_parser::eats::eat* 的函数，作用为“吃掉”字符串中的一些字节。简单逆向后不难发现，除去最开始匹配 flag{ 与 3 字节 hex 以外，剩下的都通过 nom::bytes::complete::tag 进行逐字节匹配，将形如 body[0-9]* 的函数视作点，body[0-9]*_[0-9]* 视作边，则题目可抽象成一张有向图，在经过边时，t_0ctf_parser::eats::SCORE 会随之减少，减少的数值可视作该边权重。
需要注意的是，一些特殊的点权重为正，到达这些点时，如果匹配失败，则路径会进行回溯，回到上级 nom::branch::Alt::choice 继续匹配，因此对这些点要进行特殊处理，且由于存在匹配的先后顺序关系，在获取图的数据时，边与匹配的执行顺序之间应是保序的。
进一步地，假设从点 $x$ 出发有两条边匹配了相同字符，先后顺序为 $x \to y$ 与 $x \to z$，其中从点 $y$ 出发若匹配失败，则权重增加 $w$ 后回溯 ($w < 0$)，那么可以在局部更新 $x \to z$ 边的权重为 $\min(W_{x \to y} + w,W_{x \to z})$.
下为解题使用的 gdb script.
import re
import gdb
import ctypes
from collections import deque, defaultdict
int32 = lambda x: ctypes.c_int(x).value
def get_reg_info(name) -> str:
gdb.execute(f"set $_{name} = ${name}")
return gdb.convenience_variable(f"_{name}").format_string()
def bellman_ford(start, end, graph):
node_scores = defaultdict(lambda: int32(0x80000000))
node_scores[start] = 0
pred = {}
for _ in range(len(graph) - 1):
err = False
for u in graph.keys():
for v in sorted(list(graph[u])):
if (u, v) not in dists:
continue
if u not in node_scores:
continue
if v not in node_scores or node_scores[u] + dists[(str(u), str(v))] > node_scores[v]:
node_scores[v] = node_scores[u] + dists[(str(u), str(v))]
pred[v] = u
err = True
if err == False:
break
assert not err
path = [end]
cur = end
while cur != start:
path.append(pred[cur])
cur = pred[cur]
return node_scores[end], path[::-1]
# ======================= search in disassembly to find distances between node and scores =======================
gdb.execute("set confirm off")
gdb.execute("set pagination off")
gdb.execute("set disassembly-flavor intel")
infos = gdb.execute("info functions t_0ctf_parser::eats::eat_body[0-9]*_[0-9]*$", to_string=True).split('\n')
dists = defaultdict(lambda: int32(0x80000000))
for i in infos:
res = re.findall(r"t_0ctf_parser::eats::eat_body([0-9]*)_([0-9]*)$", i)
if len(res) == 1:
address = re.findall(r"(0x[0-9a-f]*)", i)[0]
disasm = gdb.execute("disas %s" % address, to_string=True).split('\n')
for i, line in enumerate(disasm):
if "mov eax,DWORD PTR [rip" in line and "SCORE" in line:
oper = disasm[i + 1]
if "eax,ecx" in oper:
continue
if "sub eax" in oper:
dists[res[0]] = -int32(int(re.findall(r"sub eax,(0x[0-9a-f]*)$", oper)[0], 16))
break
else:
raise ValueError()
gdb.execute("delete")
node_with_scores = {}
infos = gdb.execute("info functions t_0ctf_parser::eats::eat_body[0-9]*$", to_string=True).split('\n')
for i in infos:
res = re.findall(r"t_0ctf_parser::eats::eat_body([0-9]*)$", i)
if len(res) == 1:
address = re.findall(r"(0x[0-9a-f]*)", i)[0]
disasm = gdb.execute("disas %s" % address, to_string=True).split('\n')
for i, line in enumerate(disasm):
if "mov eax,DWORD PTR [rip" in line and "SCORE" in line:
oper = disasm[i + 1]
if "eax,ecx" in oper:
continue
if "sub eax" in oper:
node_with_scores[res[0]] = -int32(int(re.findall(r"sub eax,(0x[0-9a-f]*)$", oper)[0], 16))
break
else:
raise ValueError()
# ======================= bfs to get all one byte tags, this step should take a while ;) =======================
tags = {}
queue = deque()
queue.append(('s_0', 0, "flag{000000"))
graph = defaultdict(list)
gdb.execute("delete") # clear up
while queue:
cur, depth, flag = queue.popleft()
if '_' in cur:
_, y = cur.split('_')
gdb.execute("b t_0ctf_parser::eats::eat_body%s" % y)
else:
gdb.execute("rb t_0ctf_parser::eats::eat_body%s_[0-9]*$" % cur)
gdb.execute("set args %s" % flag)
gdb.execute("r")
# now should hit your targets
gdb.execute("b nom::bytes::complete::tag")
while True:
try:
rip = get_reg_info("rip")
except:
break
r = re.findall(r"<t_0ctf_parser::eats::eat_body([0-9_]*)>", rip)
if not r:
break
target, *_ = r
if target in tags:
break
if '_' in target: # an edge
x, y = target.split('_')
graph[x].append(y)
gdb.execute("c") # now should hit tag of current target
rdi = get_reg_info("rdi")
data = gdb.execute("x/1bx %s" % rdi, to_string=True)
ch = chr(int(data.strip('\n').split('\t')[1], 16))
tags[target] = ch
queue.append((target, depth + 1, flag + ch))
gdb.execute("c")
gdb.execute("delete")
# ======================= note that nodes with scores can rollback, update the distances and find path =======================
can_rollbacks = []
for gk, gv in graph.items():
choices = [tags[gk + '_' + i] for i in gv]
dups = [i for i, c in enumerate(choices) if c in choices[:i]]
if dups:
can_rollbacks.append(gk)
dup_ch = choices[dups[0]]
dups = [choices.index(dup_ch)] + dups
new_dist = 0
for d in dups:
print("%s -> %s" % (gk, gv[d]), end=' ')
if gv[d] in node_with_scores:
new_dist += node_with_scores[gv[d]]
new_dist += dists[(gk, gv[d])]
if gv[d] in node_with_scores:
print("(*)", end=' ')
print()
if new_dist > dists[(gk, gv[dups[-1]])]:
for d in dups[:-1]:
del dists[(gk, gv[d])] # update distances of node
dists[(gk, gv[dups[-1]])] = new_dist
result, path = bellman_ford('0', '599', graph)
assert result + 0x30B > 0
flag = 'flag{000000'
for i in range(len(path)):
flag += tags[path[i]]
if i == len(path) - 1:
flag += '}'
break
flag += tags[path[i] + '_' + path[i + 1]]
print(flag)