NewStar CTF MazE 题目逆向解题指南
NewStar CTF MazE 逆向分析-writeup
题目概述
这是一道来自NewStar CTF 2024的迷宫逆向题目。程序通过管道实现父子进程通信，玩家需要从迷宫的左上角移动到右下角。题目提示路径长度为936，flag格式为flag{md5(路径)}。
程序结构分析
该程序为64位无壳ELF文件，采用fork()创建子进程，通过管道进行进程间通信。父进程负责处理用户输入和显示，子进程负责迷宫生成和位置更新。
主函数逻辑
__int64 __fastcall main(int argc, char **argv, char **envp)
{
// 创建两个管道用于双向通信
if ( pipe(pipe_fd1) == -1 || pipe(pipe_fd2) == -1 ){
perror("pipe failed");
return 1;
}
pid = fork();
if (pid > 0) { // 父进程
// 关闭不需要的管道端
close(pipe_fd1[0]); // 关闭读端
close(pipe_fd2[1]); // 关闭写端
// 读取初始地图
read(pipe_fd2[0], buffer, 0x1000);
puts("这是一个迷宫游戏，你需要从左上角走到右下角");
puts("当前界面只显示以当前位置为中心的3*3区域");
puts("使用键盘的'w''a''s''d'移动");
puts("你的flag是flag{md5(路径)}，路径为最短路径");
// 游戏循环
while (1) {
scanf("%s", input);
write(pipe_fd1[1], input, strlen(input) + 1);
if (!strcmp(input, "exit")) break;
memset(buffer, 0, 0x64);
read(pipe_fd2[0], buffer, 0x64);
puts(buffer);
}
}
else { // 子进程
close(pipe_fd2[0]);
close(pipe_fd1[1]);
pos_x = 1;
pos_y = 1;
// 生成初始迷宫视图
generate_view(view_buffer, 1, 1);
write(pipe_fd2[1], view_buffer, strlen(view_buffer) + 1);
while (1) {
memset(buffer, 0, 0x1000);
read(pipe_fd1[0], buffer, 0x1000);
if (!strcmp(buffer, "exit")) break;
// 处理玩家移动
process_input(buffer, strlen(buffer), &pos_x, &pos_y);
// 生成新视图
memset(view_buffer, 0, 0x1000);
generate_view(view_buffer, pos_x, pos_y);
write(pipe_fd2[1], view_buffer, strlen(view_buffer) + 1);
}
}
}
关键函数分析
generate_view函数 (sub_1469)
该函数根据当前位置生成3x3的迷宫视图。参数为视图缓冲区、x坐标和y坐标。
process_input函数 (sub_168F)
处理玩家输入的移动指令，根据w/a/s/d更新玩家坐标。
迷宫数据提取
通过逆向分析，发现迷宫数据存储在一个大型数组中，通过特定的位移和XOR运算解密。迷宫大小为99x99，起始位置为(1,1)，终点为(97,97)。
迷宫重建脚本
根据逆向分析结果，编写Python脚本重建完整迷宫：
# 迷宫数据（从二进制中提取）
maze_data = [
0x8B, 0x98, 0x8D, 0x9B, 0x9B, 0x99, 0xCA, 0xCA, 0x8B, 0x98,
# ... (完整的迷宫数据)
]
# 方向偏移数组
x_offset = [-1, -1, -1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0]
y_offset = [-1, 0, 1, 0, -1, 0, 1, 0, -1, 0, 1, 0, 0, 0, 0, 0]
def decrypt_cell(data, x, y):
key = "tgrddf55"
index = (99 * x + y) // 8
bit_pos = 7 - (99 * x + y) % 8
value = data[index] ^ ord(key[index % 8])
return (value >> bit_pos) & 0x1
def get_cell_char(data, x, y):
cell = decrypt_cell(data, x, y)
if cell == 0:
return '0' # 可通行
elif cell == 1:
return '1' # 墙壁
else:
return 'e' # 错误状态
def build_maze(data, size=99):
maze = []
for i in range(1, size, 3):
row1, row2, row3 = [], [], []
for j in range(1, size, 3):
# 生成3x3块
block = [get_cell_char(data, x_offset[k]+i, y_offset[k]+j)
for k in range(11)]
row1.extend(block[0:3])
row2.extend(block[3:6])
row3.extend(block[6:9])
maze.extend([row1, row2, row3])
return maze
# 构建迷宫并输出
full_maze = build_maze(maze_data)
for row in full_maze:
print(''.join(row), end=',')
路径搜索算法
BFS广度优先搜索 (C++)
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int MAZE_SIZE = 99;
int maze_map[MAZE_SIZE][MAZE_SIZE];
int visited[MAZE_SIZE][MAZE_SIZE];
// 方向: 上右下左
int dir_x[] = {-1, 0, 1, 0};
int dir_y[] = {0, 1, 0, -1};
char dir_char[] = {'w', 'd', 's', 'a'};
struct Node {
int x, y;
string path;
};
string bfs_search() {
queue<Node> q;
q.push({1, 1, ""});
visited[1][1] = 1;
while (!q.empty()) {
Node cur = q.front();
q.pop();
// 到达终点
if (cur.x == 97 && cur.y == 97) {
return cur.path;
}
// 探索四个方向
for (int i = 0; i < 4; i++) {
int nx = cur.x + dir_x[i];
int ny = cur.y + dir_y[i];
if (nx >= 0 && nx < MAZE_SIZE &&
ny >= 0 && ny < MAZE_SIZE &&
maze_map[nx][ny] == 0 &&
visited[nx][ny] == 0) {
visited[nx][ny] = 1;
q.push({nx, ny, cur.path + dir_char[i]});
}
}
}
return "";
}
int main() {
// 将迷宫数据加载到二维数组
for (int i = 0; i < MAZE_SIZE; i++) {
for (int j = 0; j < MAZE_SIZE; j++) {
maze_map[i][j] = maze_binary[MAZE_SIZE * i + j];
}
}
string result = bfs_search();
cout << "最短路径: " << result << endl;
cout << "路径长度: " << result.length() << endl;
return 0;
}
DFS深度优先搜索 (C++)
#include <iostream>
using namespace std;
const int MAZE_SIZE = 99;
int maze_map[MAZE_SIZE][MAZE_SIZE];
char path_buffer[10000];
int path_len = 0;
// 方向: 上右下左
int dir_x[] = {-1, 0, 1, 0};
int dir_y[] = {0, 1, 0, -1};
char move_char[] = {'w', 'd', 's', 'a'};
bool is_valid(int x, int y) {
return (x >= 0 && x < MAZE_SIZE &&
y >= 0 && y < MAZE_SIZE &&
maze_map[x][y] == 0);
}
void dfs(int x, int y) {
// 到达终点
if (x == 97 && y == 97) {
for (int i = 0; i < path_len; i++) {
cout << path_buffer[i];
}
cout << endl;
return;
}
// 尝试四个方向
for (int i = 0; i < 4; i++) {
int nx = x + dir_x[i];
int ny = y + dir_y[i];
if (is_valid(nx, ny)) {
path_buffer[path_len++] = move_char[i];
maze_map[x][y] = 1; // 标记为已访问
dfs(nx, ny);
maze_map[x][y] = 0; // 回溯
path_len--;
}
}
}
int main() {
// 加载迷宫数据
for (int i = 0; i < MAZE_SIZE; i++) {
for (int j = 0; j < MAZE_SIZE; j++) {
maze_map[i][j] = maze_binary[MAZE_SIZE * i + j];
}
}
dfs(1, 1);
return 0;
}
获取Flag
运行搜索算法后得到最短路径，长度为936字符。对该路径计算MD5值：
import hashlib
path = "sssswwww..." # 搜索得到的路径
flag = "flag{" + hashlib.md5(path.encode()).hexdigest() + "}"
print(flag)
最终结果：
flag{4ed5a17ee7aeb95fcf12a3b96a9d4e6f}
总结
本题关键点在于：
- 理解父子进程通过管道通信的机制
- 逆向分析迷宫生成算法，重建完整迷宫数据
- 使用BFS或DFS找到最短路径
- 对路径计算MD5得到flag
由于路径长度为936，手动搜索是不可能的，必须通过程序算法求解。
