miniLCTF2023 maze_aot

Last updated on January 27, 2024 am

一道题学会angr和IDApython,甚至BFS（：

题目流程很简单，输入一个8个十六进制数，依次根据最低位选择一条路径走，走到会终点即可得到flag

这里是题目

IDApython

观察迷宫的流程图，会发现是很有规律的，每一个block都有两个successor，根据输入决定前往哪一个successor。还要注意一点，就是会有直接jmp块，需要做个小处理。通过IDApython 提取处迷宫的结构，再用BFS算法去走即可。

提取迷宫

大致分为三部分，第一部分是计算每个block的successor，存储为字典形式，这里不区分是普通跳转还是直接jmp跳转

第二部分是记录直接跳转块

第三部分是计算普通跳转是通过什么方式去跳，即是jz还是jnz，也是存储为字典形式

note：在提取迷宫的时候，最好将地址全部转为十进制的整型，否则后面比较会有各种问题（在这卡了好久）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
start_ea = 0x1500
end_ea = 0x23D9

func = idaapi.get_func(start_ea)
cfg = idaapi.FlowChart(func)

Maze = dict()
JmpMethod = dict()
DirJmp = list()
for block in cfg:
    BlockStart = block.start_ea
    BlockEnd = block.end_ea
    
    # 初始化一下
    Maze[BlockStart] = list()

    # 记录每一个块可以去哪
    for succ in block.succs():
        # 如果不是直接跳转块，那么直接获取successor的起始地址
        if not GetDisasm(succ.start_ea).startswith('jmp'):
            Maze[BlockStart].append(succ.start_ea)
        # 如果是直接跳转块 那么就获取该汇编语句jmp的地址，并将字符型地址转为整数型存储
        else:
            Maze[BlockStart].append(int(GetDisasm(succ.start_ea)[-4::],base=16))
    
    # 记录直接跳转块
    if GetDisasm(BlockStart).startswith('jmp'):
        DirJmp.append(BlockStart)
        
    # 记录普通跳转块
    elif BlockStart!=start_ea and BlockStart!=end_ea:#这两个不等号是用来掐头去尾，否则下面Dst转化就会有问题
        JmpMethod[BlockStart] = list()
        #  这里有一个细节 就是一个block的结束地址 并不是这个block最后一条语句的地址 而是它successor的起始地址
        #  所以这里就获取结束地址的前一条语句 来得到block的最后一条语句
        #  prev_head功能是获取前一条语句 print_insn_mnem是获取操作指令
        Dst = int(GetDisasm(prev_head(BlockEnd))[-4::],base=16)
        JmpMethod[BlockStart].append(print_insn_mnem(prev_head(BlockEnd)))
        JmpMethod[BlockStart].append(Dst)

print("Maze:")
print(Maze)
print("***************************************************************")
print("DirJmp:")
print(DirJmp)
print("***************************************************************")
print("JmpMethod:")
print(JmpMethod)

BFS

得到迷宫后，就可以用BFS走，DFS应该是走不出来的，因为可能有环的存在。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
# 接上文一起
import queue

start = 0x1500
end = 0x23d9
q = queue.Queue()
q.put(0x1500)


def maze_walk():
    visited = set()
    father = {0x1500: None} #用于回溯
    while not q.empty():
        curr = q.get() # 取的同时也会弹出
        nxs = Maze[curr]
        for dirc in nxs:
            if dirc not in visited:
                visited.add(dirc)
                father[dirc] = curr
                q.put(dirc)

            if dirc == end:
                p = [dirc]
                while father[dirc] is not None:
                    dirc = father[dirc]
                    p.append(dirc)

                return p[::-1] # 反转得到由起点->终点路径


path = maze_walk()
p = []

for i in path:
    if i not in DirJmp: #如果是jmp跳 那么不理他 下一个
        p.append(i)
p = p[1:] #除去第一个点即0x1500


ans = ''
for i in range(len(p) - 1): # 终点不算
    if JmpMethod[p[i]][0] == 'jnz' and JmpMethod[p[i]][1] == p[i + 1]:
        ans += '1'
    if JmpMethod[p[i]][0] == 'jz' and JmpMethod[p[i]][1] == p[i + 1]:
        ans += '0'
    if JmpMethod[p[i]][0] == 'jnz' and JmpMethod[p[i]][1] != p[i + 1]:
        ans += '0'
    if JmpMethod[p[i]][0] == 'jz' and JmpMethod[p[i]][1] != p[i + 1]:
        ans += '1'

# 再反转得到 因为迷宫从输入的最低位开始走的，所以最右边才是起始
ans = int(ans[::-1], 2)
print(hex(ans))
#  893bddd9aa12789e

Angr

主要思路就是模拟迷宫的走法，自定义一个ExplorationTechnique,避免路径爆炸的问题，毕竟 2^64次方还是很大的，里面的各种技术细节可以参考下之前的文章（就是因为这题，才写了这些文章 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
import angr
import claripy
from angr import SimState
# 继承ExplorationTechnique类，并重载一些方法
class Walk(angr.ExplorationTechnique):
    """大体思路就是BFS"""
    def __init__(self,MazeRange:tuple[int ,int],MazeFinal:int) -> None:
        '''
        MazeRange:整个迷宫范围，也就是起始地址到结束地址，注意是整个迷宫，不是起始到终点的范围
        MazeFinal:迷宫终点
        '''
        self._MazeRange = MazeRange
        self._MazeFinal = MazeFinal
        self._Vistited = set() #用于判断是否访问过
       

    def setup(self,simgr:angr.SimulationManager):
        """
        定义并初始化两个stash
        初始化_Vistited
        """
        simgr.stashes['visited'] =[]
        simgr.stashes['found'] =[]
        self._Vistited.add(simgr.active[0].addr)

    def isInMaze(self,state:angr.SimState) -> bool:
        return self._MazeRange[0] <= state.addr < self._MazeRange[1]
    
  
    def StateSplitter(self,states:list[angr.SimState]) -> tuple[list[angr.SimState],list[angr.SimState]]:
        """
        此函数用于分拣State，如果访问过就不要让这个State加入下一次的循环了
        类似于BFS那个核心要点
        """
            _keep =[]
            _split =[]
            for state in states:
                if self.isInMaze(state): #判断是否在迷宫范围内是因为走迷宫的时候会call 'step' 函数，那个我们不处理
                    if state.addr in self._Vistited:
                        _split.append(state)
                    else:
                        self._Vistited.add(state.addr)
                        _keep.append(state)
                else:
                    _keep.append(state) # 'step'或者其他非迷宫内部的state我们都要执行

            return _keep,_split# 这里的返回顺序不能改，前面的是保留的，后面的是舍弃的
    
    def isEnd(self,state:SimState) -> bool:
            return state.addr == self._MazeFinal # 判断是否到终点了
    
    def step(self,simgr:angr.SimulationManager,stash :str = 'active',**kwargs) -> angr.SimulationManager:
        # 模拟执行
        simgr.step(stash=stash,**kwargs)

        # 筛选用于下一次执行的state
        simgr.split(stash_splitter = self.StateSplitter,from_stash = 'active',to_stash = 'visited')

        # 将到终点的state存下来
        simgr.move(from_stash = 'active',to_stash = 'found',filter_func = self.isEnd)

        return simgr
        
    def complete(self,simgr:angr.SimulationManager):
        # 定义找到终点就结束
        return bool(simgr.found)
    

# 装载 设定基址为0
proj = angr.Project("./maze",auto_load_libs = False,main_opts={'base_addr': 0})

# 找到这几个对象
SymMazeWalk = proj.loader.find_symbol("maze_walk")
SymMazeFinal = proj.loader.find_symbol("maze_final")

SymKey = proj.loader.find_symbol("key")
SymSteps = proj.loader.find_symbol("steps")

KeyValue = claripy.BVS("SymKey",64)

# 从 maze_walk 开始
State = proj.factory.call_state(SymMazeWalk.rebased_addr,prototype = 'void f()')
State.options.add(angr.sim_options.ZERO_FILL_UNCONSTRAINED_REGISTERS)

# 因为我们跳过了main函数，没有执行输入 所以要自己把输入给存进内存
State.memory.store(SymKey.rebased_addr,KeyValue)
State.memory.store(SymSteps.rebased_addr,KeyValue)

# 实例化我们的Walk
tech = Walk(MazeRange=(SymMazeWalk.rebased_addr,SymMazeWalk.rebased_addr + SymMazeWalk.size),
            MazeFinal=SymMazeFinal.rebased_addr)

# 准备执行
Simgr = proj.factory.simgr(State)
# 使用我们的搜索方式
Simgr.use_technique(tech)

# 开始跑 直到找到可以达终点的state
Simgr.run()
# 移除我们的搜索方式 准备继续执行
Simgr.remove_technique(tech)

# 从我们找到那个state开始执行
SolveState = proj.factory.simgr(Simgr.found[0])
SolveState.run()
# 执行到最后得到输出 即为flag
print(SolveState.deadended[0].posix.dumps(1))

# miniLctf{YOU_AR3_$0_GOOD_4T_SOLV1NG_MAZE}
CTF > Reverse > wp
#reverse #angr #idapython
miniLCTF2023 maze_aot
http://example.com/2023/05/25/miniLCTF2023 maze_aot/
Author
yring
Posted on
May 25, 2023
Licensed under