Aleer
Aleer
发布于 2026-11-21 / 0 阅读
0
0

RE - Maze

题目概览

项目

内容

文件

Maze.exe

类型

PE64 / x86-64,MinGW (GCC 4.9.2) 编译,无符号、未加壳

考点

多层迷宫还原、运行时迷宫生成、FNV-1a + splitmix64 + RC4 派生、路径约束求解

程序读入一行 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 逐层密钥派生

反汇编中可见以下常量:

用途

常量

位置

FNV-1a offset basis

0xcbf29ce484222325

0x40191a, 0x403595

FNV-1a prime

0x100000001b3

0x401924

splitmix64 gamma

0x9e3779b97f4a7c15

0x40360e 等

splitmix64 mix1/mix2

0xbf58476d1ce4e5b9, 0x94d049bb133111eb

0x403627 等

层2 异或掩码

0xc2b2ae3d27d4eb4f

0x40380c

每解密完一层,0x401690 会用该层迷宫更新 FNV-1a 哈希;随后 splitmix64 以该哈希为种子产出伪随机字节流:

  • layer1:16 字节密钥喂给标准 RC4(KSA 在 0x4036b0,PRGA 异或在 0x403710)解密 0x405280;

  • layer2:8 字节密钥异或 0x405260 的密文,再按 bit 展开成 13×13 位图(0x40388d 处的位提取循环,共 0xa9 = 169 位);

  • layer3:0x401ba0 用同一 PRNG 现场生成迷宫,因此文件里找不到它的明文 —— 与提示吻合。

四层位图最终落在:

层

位图地址

来源

0

0x415900

明文 XOR 0x6B

1

0x416981

XOR 0x6B + RC4

2

0x417a02

异或掩码 + 位展开

3

0x418a83

运行时生成

实践上无需完整复刻这套密钥派生:动态调试让程序自己生成四层迷宫,然后直接 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, +1
  • U/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 验证:每层满足长度要求的路径唯一):

层

起点 (row,col)

楼梯 (row,col)

路径

步数

0

(1,1)

(6,7)

DDRRRRDDRRD

11

1

(1,1)

(7,6)

RRDDRRRRDDDDL

13

2

(1,1)

(7,6)

DDRRRRDDDDR

11

3

(1,1)

(3,7)

DDDDRRRRUURR

12

层间插入 P 拼接:

DDRRRRDDRRD P RRDDRRRRDDDDL P DDRRRRDDDDR P DDDDRRRRUURR

总长 11+13+11+12+3 = 50,与长度校验一致。


五、Flag

PCTF{DDRRRRDDRRDPRRDDRRRRDDDDLPDDRRRRDDDDRPDDDDRRRRUURR}


评论