题目概览
程序读入一行 path,用 U/D/L/R 在迷宫中行走、P 上楼,目标是走到第 3 层(layer 3)的另一端。程序不会自己寻路,只校验玩家给出的路径是否合法。
一、字符串与诱饵
strings 直接暴露了大量信息:
Sorry~~~~
world: failed to load.
================================================
PCTF 2026
moves : U D L R to walk, P to take the stairs
goal : reach the far side of layer 3
------------------------------------------------
path:
You get it!!!!!!!
PCTF{UDLRUDLRUDLRUDLRUDLRUDLRUDLRUDLRUDLRUDLRUDLR} <-- 诱饵 flag
// this program never builds the path; it only walks the one you give it
// re3: four layers are in this file, but layer 3 is written nowhere
TRV*W <-- 0x405260 处的 8 字节密文(可见字符部分)
CQ4J <-- 0x405280 处的密文内容(可见字符部分)
HHHHHHHHHHHHaHEEEEE...HHHHUDLR <-- 0x405340 处的 13x13 迷宫(密文)两条注释给出了关键提示:
"never builds the path; it only walks the one you give it"—— 程序只校验路径,不生成路径。"four layers are in this file, but layer 3 is written nowhere"—— 第 4 层(下标 3)迷宫是运行时生成的,文件里没有明文。
直接提交诱饵 PCTF{UDLR...} 会被判定失败。
实测运行:
$ echo U | ./Maze.exe
...
path: Sorry~~~~二、主函数逆向
main 位于 0x403570(由 CRT 启动代码传入)。整体流程:
0x40357d 解密 layer0 明文迷宫 (0x405340) -> 0x408140,逐字节 XOR 0x6B
0x4035e3 0x401b20: ASCII 迷宫 -> 0/1 位图,写入 0x415900
0x403601 0x401690(0, &hash): 校验 layer0,计算起点/楼梯/路径长度,更新 FNV 哈希
0x40360e splitmix64 由哈希派生 16 字节 RC4 密钥
0x403677 取 0x405280 密文 -> XOR 0x6B -> RC4 解密 -> 0x401b20 转位图 -> 0x416981 (layer1)
0x403782 splitmix64 再派生 8 字节密钥
0x403819 取 0x405260 密文 -> XOR 密钥 -> 按位展开 169 bit -> 0x417a02 (layer2)
0x40396c 0x401ba0: 运行时生成 layer3 -> 0x418a83
0x403990 四层全部就绪,打印菜单
0x403a14 fgets 读入 path,剥掉 PCTF{ } 外壳
0x403ab2 检查总长度必须为 50
0x403b00 逐字符走迷宫并校验
0x403c0e 通过 -> "You get it!!!!!!!"2.1 迷宫的低强度加密:XOR 0x6B
0x4035d0 处的循环对拷贝出的迷宫逐字节 xor 0x6b:
48 ^ 6B = 0x23 = '#' (墙)
45 ^ 6B = 0x2E = '.' (路)
61 ^ 6B = 0x0A = '\n' (行分隔)直接对 0x405340 的 181 字节做同样运算即可还原 layer0:
#############
#...........#
#.#########.#
#.....#...#.#
#####.###.#.#
#...#.....#.#
#.#.###.###.#
#.#...#.#...#
#.###.#.#####
#...#.#...#.#
###.#.###.#.#
#...#.......#
#############函数 0x401b20(src, dst) 把 13 行 × 13 列的 ASCII 迷宫转换成 169 字节位图:'#' -> 1(墙),其余 -> 0(通路),并校验每行宽度与换行位置。
2.2 逐层密钥派生
反汇编中可见以下常量:
每解密完一层,0x401690 会用该层迷宫更新 FNV-1a 哈希;随后 splitmix64 以该哈希为种子产出伪随机字节流:
layer1:16 字节密钥喂给标准 RC4(KSA 在
0x4036b0,PRGA 异或在0x403710)解密0x405280;layer2:8 字节密钥异或
0x405260的密文,再按 bit 展开成 13×13 位图(0x40388d处的位提取循环,共0xa9 = 169位);layer3:
0x401ba0用同一 PRNG 现场生成迷宫,因此文件里找不到它的明文 —— 与提示吻合。
四层位图最终落在:
实践上无需完整复刻这套密钥派生:动态调试让程序自己生成四层迷宫,然后直接 dump 位图即可。
2.3 全局参数(路径约束)
0x401690 在校验每层迷宫时写入以下全局变量(gdb dump 的实际值):
0x415890: 11 13 11 12 <- 每层必须走的步数
0x4158a0: 7 6 6 7 \
0x4158b0: 6 7 7 3 / 每层楼梯出口 (col,row)
0x4158c0: 1 1 1 1 \
0x4158d0: 1 1 1 1 / 每层起点 (col,row)长度校验(0x403ab2):
ecx = [0x415890] + [0x415894] + 3 + [0x415898] + [0x41589c]
= 11 + 13 + 3 + 11 + 12 = 50
cmp ecx, input_len即:输入总长必须恰好 50(47 个方向 + 3 个 P)。
2.4 行走校验(0x403b00)
方向表(gdb 实测):
0x405400 (row 增量, index=U/D/L/R): -1, +1, 0, 0
0x405410 (col 增量, index=U/D/L/R): 0, 0, -1, +1U/D/L/R:更新当前(row, col),检查越界(0..12),并检查目标格位图为0(通路);P:若当前层
<= 2:必须正好站在该层楼梯上(0x4158a0),然后layer++;若当前层
== 3:必须站在该层起点上(可下楼),否则失败;
循环结束要求
layer == 3且当前位置为(row=3, col=7)(0x4158b8/0x4158bc),才输出成功。
三、动态调试 dump 四层迷宫
在迷宫生成完成、但尚未读取输入的位置 0x403990 下断,dump 四段 169 字节位图:
break *0x403990
run
x/169bx 0x415900
x/169bx 0x416981
x/169bx 0x417a02
x/169bx 0x418a83把 1 画成 #、0 画成 .,得到四层迷宫(下图中 S=起点,E=楼梯/终点,数字为步序,16 进制 1..B):
Layer 0 — DDRRRRDDRRD(11 步)
#############
#S..........#
#1#########.#
#23456#...#.#
#####7###.#.#
#...#89A..#.#
#.#.###E###.#
#.#...#.#...#
#.###.#.#####
#...#.#...#.#
###.#.###.#.#
#...#.......#
#############Layer 1 — RRDDRRRRDDDDL(13 步)
#############
#S12....#.#.#
#.#3#####.#.#
#.#45678#.#.#
#.#####9#.#.#
#.....#A#...#
#######B###.#
#.....EC#...#
#.#####.#.###
#.#.....#.#.#
#.#######.#.#
#...........#
#############Layer 2 — DDRRRRDDDDR(11 步)
#############
#S........#.#
#1#######.#.#
#23456#...#.#
#####7#.###.#
#...#8#...#.#
#.#.#9#####.#
#.#.#AE.#...#
#.#####.#.###
#.#.....#...#
#.#.#######.#
#...........#
#############Layer 3 — DDDDRRRRUURR(12 步)
#############
#S..........#
#1#.#######.#
#2#.#ABE..#.#
#3###9###.###
#45678..#...#
#.#####.###.#
#.#...#...#.#
###.#.###.#.#
#...#...#.#.#
#######.###.#
#...........#
#############四、路径求解
每层迷宫都是单连通的,且起点到楼梯的最短路径长度恰好等于全局变量规定的步数,因此用 BFS 求最短路即可:
from collections import deque
def bfs(maze, start, goal):
q = deque([(start[0], start[1], "")])
seen = {start}
while q:
r, c, p = q.popleft()
if (r, c) == goal:
return p
for ch, dr, dc in [('U',-1,0),('D',1,0),('L',0,-1),('R',0,1)]:
nr, nc = r+dr, c+dc
if 0 <= nr < 13 and 0 <= nc < 13 and maze[nr*13+nc] == 0 \
and (nr, nc) not in seen:
seen.add((nr, nc))
q.append((nr, nc, p+ch))求解结果(已用带长度约束的 DFS 验证:每层满足长度要求的路径唯一):
层间插入 P 拼接:
DDRRRRDDRRD P RRDDRRRRDDDDL P DDRRRRDDDDR P DDDDRRRRUURR总长 11+13+11+12+3 = 50,与长度校验一致。
五、Flag
PCTF{DDRRRRDDRRDPRRDDRRRRDDDDLPDDRRRRDDDDRPDDDDRRRRUURR}