-
-
[原创]2021美团CTF-Re-100mazes
-
发表于: 2021-5-26 01:55 10021
-
0
开头就先总结一下这篇文章学到了什么吧
拿到之后打开发现就是100张地图，然后将走出来的总长度为1500的路线md5得到flag
查看发现基本上100个maze的大体流程基本都是相同的
我们先分析其中一个就可以
maze1：
主要的逻辑就是，前面先mov给table1进行赋值，然后赋我们的"方向盘"，然后赋我们的table2
之后用循环来走15次，说明每个迷宫走出来的字符串都是长度为15，最后加了个if条件将table1和table2异或之后来进行判断，说明将两个table异或之后才能得到真正的maze
逻辑不难，但是由于是100个迷宫，提取数据和解析等人工难以解决
下面我们先分析每个函数的汇编指令有些什么相似之处
思路：先分析函数的共同点，用capstone来解析指令并自动提取出我们的数据
首先我们发现，table1的赋值都是这种指令：
共625条
赋完table1之后，紧接着之后又发现了几条同样的指令，这几个指令就是赋我们的"方向盘"的
table2的解析：
发现 table2 有一条 lea 指令用来传址，并且是相对 eip 的寻址
map2 的地址为 0xa4e6c(当前地址)+7(指令长度)+ 0x3ed6d, 直接解析 625 个 int 即可
然后继续分析，发现两条mov dword ptr [rbp + xxx], xxx 赋值起点坐标
运行结果：
总结:一. 使用capstone对二进制文件进行指令解析"""先以rb形式打开文件,然后.read()读取赋值给变量然后binary = data[addr: addr+0x666]这种指令是取出要解析的那一段代码的机器码md = Cs(CS_ARCH_X86, CS_MODE_64) 设置解析模式为X86架构下的64位for i in md.disasm(binary, addr):# 第一个参数是机器码Byte数据，第二个参数是这段代码的"基地址".该函数为反汇编到一条错误的指令为止解析出指令:ins = "0x%x:\t%s\t%s" % (i.address, i.mnemonic, i.op_str) # 地址信息、助记符、操作数字符串然后接下来就是匹配指令,比如:(获取到自己想要的那些指令,操作数等)if 'mov byte ptr [rbp' in ins: pass
if 'mov dword ptr [rbp' in ins: pass
...二.数据结构-图;图的遍历算法BFS,DFS(仅此肯定是不够的,之后还得加深)三.使用DFS算法自动走迷宫的python脚本写法:(一般情况的思路)solve(map, startX, startY, direct, path):#传入的参数有map,开始位置的坐标,控制方向的字符,和走过的path字符串(path是为了返回的)if len(path) == 15: return True, path
#通过走过的路径长度来判断是否返回然后外面还必须有个checkValid来检测走到的位置是否合法def checkValid(map, x, y): # 检测某个坐标是否合法 if x < 0 or y < 0 or x > 24 or y > 24:
return False
return map[y * 25 + x] == ord('.')
使用checkValid的方法几个if条件进行判断(也就是查找每一个邻接结点)根据对应的移动来+-坐标,然后作为参数传入checkValid进行检测,如果这个点合法就将按照这种移动方法移动的下一个点的坐标和这种移动方法的操作字符都append下来例:all_dir.append((startX - 1, startY, direct[2]))之后for i in all_dir逐渐取出所有的可能走的方向,然后进行递归for dir in all_dir: # 这个循环存在的意义是为了避免可以有多条路线 result = solve(map, dir[0], dir[1], direct, path + dir[2])
# 递归到下一个点,并将上一个点的方向控制符加到路线中"""总结:一. 使用capstone对二进制文件进行指令解析"""先以rb形式打开文件,然后.read()读取赋值给变量然后binary = data[addr: addr+0x666]这种指令是取出要解析的那一段代码的机器码md = Cs(CS_ARCH_X86, CS_MODE_64) 设置解析模式为X86架构下的64位for i in md.disasm(binary, addr):# 第一个参数是机器码Byte数据，第二个参数是这段代码的"基地址".该函数为反汇编到一条错误的指令为止解析出指令:ins = "0x%x:\t%s\t%s" % (i.address, i.mnemonic, i.op_str) # 地址信息、助记符、操作数字符串然后接下来就是匹配指令,比如:(获取到自己想要的那些指令,操作数等)if 'mov byte ptr [rbp' in ins: pass
if 'mov dword ptr [rbp' in ins: pass
...二.数据结构-图;图的遍历算法BFS,DFS(仅此肯定是不够的,之后还得加深)三.使用DFS算法自动走迷宫的python脚本写法:(一般情况的思路)solve(map, startX, startY, direct, path):#传入的参数有map,开始位置的坐标,控制方向的字符,和走过的path字符串(path是为了返回的)if len(path) == 15: return True, path
#通过走过的路径长度来判断是否返回然后外面还必须有个checkValid来检测走到的位置是否合法def checkValid(map, x, y): # 检测某个坐标是否合法 if x < 0 or y < 0 or x > 24 or y > 24:
return False
return map[y * 25 + x] == ord('.')
使用checkValid的方法几个if条件进行判断(也就是查找每一个邻接结点)根据对应的移动来+-坐标,然后作为参数传入checkValid进行检测,如果这个点合法就将按照这种移动方法移动的下一个点的坐标和这种移动方法的操作字符都append下来例:all_dir.append((startX - 1, startY, direct[2]))之后for i in all_dir逐渐取出所有的可能走的方向,然后进行递归for dir in all_dir: # 这个循环存在的意义是为了避免可以有多条路线 result = solve(map, dir[0], dir[1], direct, path + dir[2])
# 递归到下一个点,并将上一个点的方向控制符加到路线中"""unsigned __int64 maze_1(void){ char v321[624]; // [rsp+6h] [rbp-C6Ah] BYREF
char direction[5]; // [rsp+276h] [rbp-9FAh] BYREF
char input_char; // [rsp+27Bh] [rbp-9F5h]
int col; // [rsp+27Ch] [rbp-9F4h]
int line; // [rsp+280h] [rbp-9F0h]
int v326; // [rsp+284h] [rbp-9ECh]
int v327; // [rsp+288h] [rbp-9E8h]
int i; // [rsp+28Ch] [rbp-9E4h]
int v329; // [rsp+290h] [rbp-9E0h]
int v330; // [rsp+294h] [rbp-9DCh]
char *table1; // [rsp+298h] [rbp-9D8h]
int table2[626]; // [rsp+2A0h] [rbp-9D0h] BYREF
unsigned __int64 v333; // [rsp+C68h] [rbp-8h]
v333 = __readfsqword(0x28u);
v321[0] = 0xB0;
v321[1] = 0x70;
v321[2] 0x8D;
.............此处省略一些赋值的代码
__asm { rdrand rax }
v321[605] = -127;
v321[606] = 126;
v321[607] = 96;
v321[608] = -110;
v321[609] = 12;
v321[610] = 32;
__asm { rdrand rax }
v321[611] = -65;
__asm { rdrand rax }
v321[612] = -95;
__asm { rdrand rax }
v321[613] = 62;
__asm { rdrand rax }
v321[614] = -19;
__asm { rdrand rax }
v321[615] = 6;
v321[616] = 13;
v321[617] = 95;
__asm { rdrand rax }
v321[618] = -13;
v321[619] = 44;
__asm { rdrand rax }
v321[620] = 58;
__asm { rdrand rax }
v321[621] = 93;
v321[622] = 53;
v321[623] = -9;
qmemcpy(direction, "kgMp9", sizeof(direction));
qmemcpy(table2, dword_A7420, 0x9C0uLL);
table2[624] = 65;
table1 = v321;
col = 4;
line = 24;
v326 = 4;
v327 = 24;
for ( i = 0; i <= 14; ++i ) // 循环15次
{
v329 = col;
v330 = line;
input_char = getchar(); // 读入单个字符
if ( input_char == direction[1] ) // g 上移
{
--line;
}
else if ( input_char == direction[2] ) // M 下移
{
++line;
}
else if ( input_char == direction[3] ) // p 左移
{
--col;
}
else
{
if ( input_char != direction[4] ) // 9 右移
exit(0);
++col;
}
if ( col < 0
|| line < 0
|| col > 24
|| line > 24 // 行列的下标最多24,说明这是一个25*25的maze
|| ((unsigned __int8)table1[25 * line + col] ^ table2[25 * line + col]) != '.'// 两个表异或得到真正的表,这里是在检测走的路不是'.'
|| col == v326 && line == v327 ) // 判断是否还在起点
{
exit(0);
}
v326 = v329;
v327 = v330;
}
return __readfsqword(0x28u) ^ v333;
}unsigned __int64 maze_1(void){ char v321[624]; // [rsp+6h] [rbp-C6Ah] BYREF
char direction[5]; // [rsp+276h] [rbp-9FAh] BYREF
char input_char; // [rsp+27Bh] [rbp-9F5h]
int col; // [rsp+27Ch] [rbp-9F4h]
int line; // [rsp+280h] [rbp-9F0h]
int v326; // [rsp+284h] [rbp-9ECh]
int v327; // [rsp+288h] [rbp-9E8h]
int i; // [rsp+28Ch] [rbp-9E4h]
int v329; // [rsp+290h] [rbp-9E0h]
int v330; // [rsp+294h] [rbp-9DCh]
char *table1; // [rsp+298h] [rbp-9D8h]
int table2[626]; // [rsp+2A0h] [rbp-9D0h] BYREF
unsigned __int64 v333; // [rsp+C68h] [rbp-8h]
v333 = __readfsqword(0x28u);
v321[0] = 0xB0;
v321[1] = 0x70;
v321[2] 0x8D;
.............此处省略一些赋值的代码
__asm { rdrand rax }
v321[605] = -127;
v321[606] = 126;
v321[607] = 96;
v321[608] = -110;
v321[609] = 12;
v321[610] = 32;
__asm { rdrand rax }
v321[611] = -65;
__asm { rdrand rax }
v321[612] = -95;
__asm { rdrand rax }
v321[613] = 62;
__asm { rdrand rax }
v321[614] = -19;
__asm { rdrand rax }
v321[615] = 6;
v321[616] = 13;
v321[617] = 95;
__asm { rdrand rax }
v321[618] = -13;
v321[619] = 44;
__asm { rdrand rax }
v321[620] = 58;
__asm { rdrand rax }
v321[621] = 93;
v321[622] = 53;
v321[623] = -9;
qmemcpy(direction, "kgMp9", sizeof(direction));
qmemcpy(table2, dword_A7420, 0x9C0uLL);
table2[624] = 65;
table1 = v321;
col = 4;
line = 24;
v326 = 4;
v327 = 24;
for ( i = 0; i <= 14; ++i ) // 循环15次
{
v329 = col;
v330 = line;
input_char = getchar(); // 读入单个字符
if ( input_char == direction[1] ) // g 上移
{
--line;
}
else if ( input_char == direction[2] ) // M 下移
{
++line;
}
else if ( input_char == direction[3] ) // p 左移
{
--col;
}
else
{
if ( input_char != direction[4] ) // 9 右移
exit(0);
++col;
}
if ( col < 0
|| line < 0
|| col > 24
|| line > 24 // 行列的下标最多24,说明这是一个25*25的maze
|| ((unsigned __int8)table1[25 * line + col] ^ table2[25 * line + col]) != '.'// 两个表异或得到真正的表,这里是在检测走的路不是'.'
|| col == v326 && line == v327 ) // 判断是否还在起点
{
exit(0);
}
v326 = v329;
v327 = v330;
}
return __readfsqword(0x28u) ^ v333;
}.text:0000000000001CFE mov [rbp+var_A54], 4Ah ; 'J'
.text:0000000000001D05 mov [rbp+var_A53], 0ACh
.text:0000000000001D0C mov [rbp+var_A52], 0DFh
.text:0000000000001D13 mov [rbp+var_A51], 0ABh
.text:0000000000001D1A mov [rbp+var_A50], 0ADh
.text:0000000000001D21 mov [rbp+var_A4F], 0A1h
.text:0000000000001D28 mov [rbp+var_A4E], 0ABh
.text:0000000000001D2F mov [rbp+var_A4D], 1Ah
.text:0000000000001CFE mov [rbp+var_A54], 4Ah ; 'J'
.text:0000000000001D05 mov [rbp+var_A53], 0ACh
.text:0000000000001D0C mov [rbp+var_A52], 0DFh
.text:0000000000001D13 mov [rbp+var_A51], 0ABh
.text:0000000000001D1A mov [rbp+var_A50], 0ADh
.text:0000000000001D21 mov [rbp+var_A4F], 0A1h
.text:0000000000001D28 mov [rbp+var_A4E], 0ABh
.text:0000000000001D2F mov [rbp+var_A4D], 1Ah
.text:0000000000002069 mov [rbp+var_9F9], 67h ; 'g'
.text:0000000000002070 mov [rbp+var_9F8], 4Dh ; 'M'
.text:0000000000002077 mov [rbp+var_9F7], 70h ; 'p'
.text:000000000000207E mov [rbp+var_9F6], 39h ; '9'
.text:0000000000002069 mov [rbp+var_9F9], 67h ; 'g'
.text:0000000000002070 mov [rbp+var_9F8], 4Dh ; 'M'
.text:0000000000002077 mov [rbp+var_9F7], 70h ; 'p'
.text:000000000000207E mov [rbp+var_9F6], 39h ; '9'
0xa4e6c: lea rax, [rip + 0x3ed6d]
0xa4e6c: lea rax, [rip + 0x3ed6d]
# _*_ coding:utf-8 _*_# @功能描述:# @程序作者:SYJ# @版权信息:Reversed By SYJ# @版本信息：0.0.0from capstone import *
import struct
def decode(offset):
data_bin = open('E:\\SYJ\\COMPETITIONS\\2021美团\\100mazes\\100mazes', 'rb').read()
data = data_bin[offset: offset + 0x2010] # 获取到要分析的那一段
md = Cs(CS_ARCH_X86, CS_MODE_64) # X86_64
inscnt = 0
inscnt2 = 0
map1 = []
map2 = []
start_position = []
for i in md.disasm(data, offset): # 第一个参数是机器码Byte数据，第二个参数是这段代码的"基地址".该函数为反汇编到一条错误的指令为止
ins = "0x%x:\t%s\t%s" % (i.address, i.mnemonic, i.op_str) # 地址信息、助记符、操作数字符串
if 'mov byte ptr [rbp' in ins: # 匹配向table1传数据的指令 和 向初始位置赋值的指令
if inscnt < 629:
map1.append(int(i.op_str.split(', ')[1], 16)) # 取操作数['byte ptr [rbp..', '0xC4']列表的第二个
inscnt += 1
if 'mov dword ptr [rbp' in ins: # 匹配start_position位置的赋值指令
if inscnt2 < 2:
start_position.append(int(i.op_str.split(', ')[1], 16))
inscnt2 += 1
if 'lea rax, [rip +' in ins:
off1 = i.op_str[11:-1] # 取到和rip的偏移
off1 = int(off1, 16) + i.address + 7 # 取到table2的地址,i.address是取到当前rip的地址,7是当前指令的长度
map2_data = data_bin[off1: off1 + 4 * 625] # 625个dword数据
for j in range(625):
# 将b'\x0f\x00\x00\x00'这种bytes类型数据解包成unsigned_int的数据
map2.append(struct.unpack("I", map2_data[j * 4: j * 4 + 4])[0]) # 解包成unsigned_int数据的元组后[0]取出元素
real_map = []
for i in range(625):
real_map.append(map1[i] ^ map2[i])
return real_map, bytearray(map1[-4:]), start_position
# 返回异或得到的真正的地图,table1的最后四个元素的bytes形式(就是控制方向的四个元素),和开始位置的坐标
# _*_ coding:utf-8 _*_# @功能描述:# @程序作者:SYJ# @版权信息:Reversed By SYJ# @版本信息：0.0.0from capstone import *
import struct
def decode(offset):
data_bin = open('E:\\SYJ\\COMPETITIONS\\2021美团\\100mazes\\100mazes', 'rb').read()
data = data_bin[offset: offset + 0x2010] # 获取到要分析的那一段
md = Cs(CS_ARCH_X86, CS_MODE_64) # X86_64
inscnt = 0
inscnt2 = 0
map1 = []
map2 = []
start_position = []
for i in md.disasm(data, offset): # 第一个参数是机器码Byte数据，第二个参数是这段代码的"基地址".该函数为反汇编到一条错误的指令为止
ins = "0x%x:\t%s\t%s" % (i.address, i.mnemonic, i.op_str) # 地址信息、助记符、操作数字符串
if 'mov byte ptr [rbp' in ins: # 匹配向table1传数据的指令 和 向初始位置赋值的指令
if inscnt < 629:
map1.append(int(i.op_str.split(', ')[1], 16)) # 取操作数['byte ptr [rbp..', '0xC4']列表的第二个
inscnt += 1
if 'mov dword ptr [rbp' in ins: # 匹配start_position位置的赋值指令
if inscnt2 < 2:
start_position.append(int(i.op_str.split(', ')[1], 16))
inscnt2 += 1
if 'lea rax, [rip +' in ins:
off1 = i.op_str[11:-1] # 取到和rip的偏移
off1 = int(off1, 16) + i.address + 7 # 取到table2的地址,i.address是取到当前rip的地址,7是当前指令的长度
map2_data = data_bin[off1: off1 + 4 * 625] # 625个dword数据
for j in range(625):
# 将b'\x0f\x00\x00\x00'这种bytes类型数据解包成unsigned_int的数据
map2.append(struct.unpack("I", map2_data[j * 4: j * 4 + 4])[0]) # 解包成unsigned_int数据的元组后[0]取出元素
real_map = []
for i in range(625):
real_map.append(map1[i] ^ map2[i])
return real_map, bytearray(map1[-4:]), start_position
# 返回异或得到的真正的地图,table1的最后四个元素的bytes形式(就是控制方向的四个元素),和开始位置的坐标
def checkValid(map, x, y): # 检测某个坐标是否合法
if x < 0 or y < 0 or x > 24 or y > 24:
return False
return map[y * 25 + x] == ord('.')
def solve(map, startX, startY, direct, path):
map[startY * 25 + startX] = ord('*') # 每次走一步就将其走过位置填为'*'(maze的墙的构成元素)
if len(path) == 15: # 每次递归调用之后判断是否已经走了15步,每个迷宫只走15步
return True, path
all_dir = []
i = 0
if checkValid(map, startX, startY - 1): # 查找每一个邻接结点
all_dir.append((startX, startY - 1, direct[0]))
if checkValid(map, startX, startY + 1):
all_dir.append((startX, startY + 1, direct[1]))
if checkValid(map, startX - 1, startY):
all_dir.append((startX - 1, startY, direct[2]))
if checkValid(map, startX + 1, startY):
all_dir.append((startX + 1, startY, direct[3])) # 将checkValid的坐标和行进的字符append到all_dir
for dir in all_dir: # 这个循环存在的意义是为了避免可以有多条路线
result = solve(map, dir[0], dir[1], direct, path + dir[2]) # 递归到下一个点,并将上一个点的方向控制符加到路线中
if result[0] == True:
return result
return False, ''
def checkValid(map, x, y): # 检测某个坐标是否合法
if x < 0 or y < 0 or x > 24 or y > 24:
赞赏记录
参与人
雪币
留言
时间
一笑人间万事
为你点赞~
2023-1-13 03:55
Youlor
为你点赞~
2022-7-17 11:42
sunfishi
为你点赞~
2021-5-27 12:59
赞赏
|
|
|---|---|
|
|
他的文章
赞赏
雪币:
留言:
