利用 networkx 解决CTF_RE 图最短路径问题
# 利用 networkx 解决CTF_RE 图最短路径问题## 前言
最近复现了了下今年L3HCTF的IDAAAAA题，然后通过此题又联想到了之前做的一道特殊的迷宫题invisible_maze-fix,发现通过python的networkx解决此类问题相当的方便，因此记录下解题过程，方便以后查询。
>2道题目附件👇
>
>链接：https://pan.baidu.com/s/1reVYGScanSCs5H4ykl60vw
>提取码：kvhl
## invisible_maze
### 常规的迷宫题目
在CTF逆向题目中，常规的迷宫题目一般是程序给你一个非常长的字符串，然后自己整理可以得到整个迷宫的全貌，比如下图这种
这种能很容易的得到整个迷宫的路径，可是这个invisible_maze这个题才可以说是是真正的迷宫题，因为它没有从上帝视角给你路径的全貌，而是把你放到了个迷宫中，每走一步，它告诉你，上下左右分别去哪
### 本题题解
#### 分析
IDA打开程序分析
进入`sub_401050`函数， 程序告诉你上下左右走的话是什么东西，很明显，只有进入另一个函数路才是通的
直接查找字符串，交叉引用来到成功的地方
可以发现只有进入到`sub_41F1E0`,然后再按s才会成功，而整个迷宫的路径是非常复杂的
观察函数窗口，发现从`sub_401050` 到 `sub_41F270` 全是这样的结构，我们手动的去画出整个迷宫显然是不现实的，每个函数其实就是一个节点，然后两个节点就构成了一条边，比如：`sub_401050`就是一个节点，而`sub_401050 ---> sub_4010E0`就是一条边。
每个函数的结构基本差不多，考虑打算用IDAPython打印出每个节点，以及它对应的adsw对应的四个值，如果是进入另外一个函数的话，那么本函数和进入的那个函数就构造成了一条边，最后将节点和边传入python的networkx库就能构造出整个迷宫图，直接调用函数就能求最短路径了。
发现函数只有下面2种情况
当经过case表跳转后，如果第一条汇编指令是`push xxx`，那么肯定是不通的（除了成功的那个位置），如果是`call sub_xxx`的话，那么本条汇编指令就可以找到下一个函数（节点），如果是`pop esi`的话，下一条`jmp xxx`就是进入的下一个函数（节点）
#### 编写IDAPython脚本
写IDAPython脚本
```python
def get_edges_from_func(func_addr):
func_end_addr = idc.find_func_end(func_addr) # 找到此函数末尾地址
addr = func_addr
while addr < func_end_addr:
addr = idc.next_head(addr) # 得到下一条汇编指令的地址
if idc.print_insn_mnem(addr) == 'movzx': # 得到本条汇编指令的操作指令
index_table_addr = get_operand_value(addr ,1) # 得到adsw对应的索引表，对应上2图的0x4010C0 和 0x41E384
addr = idc.next_head(addr) # 来到Jmp ds:xxxx的位置
switch_table_addr = get_operand_value(addr ,0)# 得到case表的地址
break
value = get_bytes(index_table_addr, 23)
index_adws = , value, value, value] # 获取adsw对应的4个数
# print(index_adws)
edges = []
for i in index_adws: # 遍历
tmp = get_wide_dword(switch_table_addr + i * 4)
if idc.print_insn_mnem(tmp) == 'push':
edges.append(None)
elif idc.print_insn_mnem(tmp) == 'call':
edges.append(get_operand_value(tmp ,0)) # 得到call的那个函数的地址
elif idc.print_insn_mnem(tmp) == 'pop':
tmp = idc.next_head(tmp) # 来到jmp sub_xxx的地址
edges.append(get_operand_value(tmp ,0))
# print(edges)
return edges
func_list = list(Functions(0x401050, 0x41F271)) # 列出此范围所有的函数
all_edges = []
for i in func_list:
edges = get_edges_from_func(i)
all_edges.append(edges)
print(all_edges)
print("len(func_list): %d" % len(func_list))
print("len(all_edges): %d" % len(all_edges))
print(func_list)
```
输入结果
```
[, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ]
len(func_list): 788
len(all_edges): 788
```
>对于IDAPython简单函数的学习，可以参考 https://zzzzsky.com/2021/12/08/LearnIDAPython/
至此，我们找到了所有的节点，以及每个节点对应的adsw对应的4个值，如果为None说明不通，如果不为None，说明是进入的另外一个函数，就可以构造一条边
#### networkx求最短路径
写python脚本
```python
import networkx as nx
import hashlib
all_edges = [, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ]
func_list =
src_node = 0x401050 # 起点
target_node = 0x41F1E0# 终点
G = nx.MultiDiGraph() # 生成一张空图，Mul允许2个节点之间存在多个边，Di代表边是有方向的
for i in func_list:
G.add_node(i) # 添加节点
for i, value inenumerate(all_edges):
src = func_list
for j in value:
if j != None: # 不为None,就可以构造一条边
dst = j
G.add_edge(src, dst)
path = nx.shortest_path(G, source = src_node, target = target_node) # 直接调用此函数就可以求出最短路径经过的那几个节点
print(len(path))
print()
s = ""
for i in range(1, len(path)): # 根据得到的结果来求出每一步走的方向
func_index = func_list.index(path)
index = all_edges.index(path)
if index == 0:
s += 'a'
elif index == 1:
s += 'd'
elif index == 2:
s += 's'
else:
s += 'w'
# 成功的地方在41F1E0处
# case 's':
# result = printf("Great!!!you got it!flag is DASCTF{md5{your input}\n");
# break;
input_ = s + 's'
print(input_)
# DASCTF{md5{your input}\n")
print("DASCTF{%s}" % hashlib.md5(input_.encode()).hexdigest())、
```
输出
```
496
['0x401050', '0x4010e0', '0x401180', '0x403460', '0x403500', '0x4035a0', '0x403640', '0x4036e0', '0x403770', '0x403810', '0x4038b0', '0x403940', '0x4039e0', '0x403a80', '0x403b20', '0x403bc0', '0x403c60', '0x403cf0', '0x403d90', '0x403e30', '0x403ec0', '0x403f60', '0x404630', '0x405e20', '0x406450', '0x406eb0', '0x408060', '0x4087c0', '0x4097c0', '0x40a520', '0x40b490', '0x40b970', '0x40ba10', '0x40bab0', '0x40bb50', '0x40bbf0', '0x40bc90', '0x40bd30', '0x40bdd0', '0x40be60', '0x40bf00', '0x40bfa0', '0x40c030', '0x40c0d0', '0x40c170', '0x40c210', '0x40c2b0', '0x40c340', '0x40c3e0', '0x40c480', '0x40c520', '0x40c5c0', '0x40c650', '0x40c6f0', '0x40c790', '0x40c820', '0x40c8c0', '0x40c950', '0x40c9f0', '0x40ca90', '0x40cb30', '0x40cbd0', '0x40cc70', '0x40b530', '0x40ae60', '0x409990', '0x408f10', '0x408240', '0x407990', '0x4078f0', '0x407860', '0x4077d0', '0x407730', '0x407690', '0x4075f0', '0x407550', '0x4074b0', '0x407410', '0x4081a0', '0x408ad0', '0x408b60', '0x408c00', '0x408c90', '0x408d30', '0x408dd0', '0x408e70', '0x409900', '0x40adc0', '0x40ad20', '0x40ac80', '0x40abe0', '0x40ab40', '0x40aaa0', '0x40aa00', '0x40a960', '0x40a8d0', '0x40a840', '0x40a7a0', '0x40a700', '0x40a660', '0x40a5c0', '0x409860', '0x408860', '0x408900', '0x408990', '0x408a30', '0x408100', '0x407370', '0x406590', '0x405f60', '0x404770', '0x404810', '0x4048b0', '0x404950', '0x4049f0', '0x404a90', '0x404b30', '0x404bc0', '0x404c60', '0x404d00', '0x404da0', '0x404e30', '0x404ed0', '0x404f70', '0x405010', '0x4050b0', '0x405150', '0x4051f0', '0x405290', '0x405320', '0x4053c0', '0x405460', '0x405500', '0x405590', '0x405620', '0x4056c0', '0x405760', '0x406000', '0x406630', '0x407a30', '0x4082e0', '0x408fb0', '0x409a30', '0x40af00', '0x40b5d0', '0x40cd10', '0x40d200', '0x40f620', '0x40faf0', '0x410ff0', '0x412270', '0x4126c0', '0x412760', '0x412800', '0x4128a0', '0x412940', '0x4129e0', '0x412a80', '0x412b20', '0x412bc0', '0x412c50', '0x412ce0', '0x412d80', '0x412e20', '0x412ec0', '0x412f60', '0x413000', '0x4130a0', '0x412310', '0x411580', '0x40fcd0', '0x40f880', '0x40d480', '0x40cf90', '0x40b830', '0x40b180', '0x409ca0', '0x409410', '0x408410', '0x407b60', '0x406bb0', '0x406b10', '0x406a70', '0x4069d0', '0x406930', '0x4068a0', '0x406800', '0x406760', '0x406140', '0x4058a0', '0x404450', '0x402c70', '0x402d00', '0x402da0', '0x402e40', '0x402ee0', '0x402f70', '0x403010', '0x4030b0', '0x403150', '0x4031f0', '0x403280', '0x403320', '0x4033c0', '0x4044f0', '0x405930', '0x4061e0', '0x406c50', '0x407c00', '0x4084b0', '0x408540', '0x4094b0', '0x409550', '0x409d40', '0x409de0', '0x40b220', '0x40b8d0', '0x40d160', '0x40d0c0', '0x40d660', '0x40d5c0', '0x40d520', '0x40f920', '0x40fd70', '0x411620', '0x4123b0', '0x413140', '0x413930', '0x4161e0', '0x416140', '0x4160a0', '0x416000', '0x415f60', '0x415ec0', '0x415e20', '0x415d80', '0x415ce0', '0x415c40', '0x415ba0', '0x415b00', '0x415a60', '0x4159c0', '0x415920', '0x415890', '0x4157f0', '0x415760', '0x4156c0', '0x415620', '0x415580', '0x4154e0', '0x415440', '0x4153a0', '0x415300', '0x415270', '0x4151d0', '0x415130', '0x415090', '0x414ff0', '0x414f60', '0x414ec0', '0x414e20', '0x414d90', '0x414cf0', '0x414c50', '0x414bb0', '0x414b20', '0x414a90', '0x4149f0', '0x414950', '0x4148b0', '0x414810', '0x414770', '0x4146d0', '0x413890', '0x4137f0', '0x413750', '0x4136b0', '0x414630', '0x414590', '0x4144f0', '0x414450', '0x4143b0', '0x414310', '0x414270', '0x4141d0', '0x414130', '0x414090', '0x413ff0', '0x413f60', '0x413ec0', '0x413e20', '0x413d80', '0x413cf0', '0x413c50', '0x413bb0', '0x413b10', '0x413a70', '0x413620', '0x412630', '0x411880', '0x4101c0', '0x410260', '0x4102f0', '0x410390', '0x410430', '0x4104d0', '0x410570', '0x410610', '0x4106b0', '0x410750', '0x4107f0', '0x410890', '0x410920', '0x4109b0', '0x410a50', '0x410af0', '0x410b90', '0x410c30', '0x410cd0', '0x410d70', '0x410e10', '0x410eb0', '0x411920', '0x4119c0', '0x411a60', '0x411b00', '0x411ba0', '0x411c40', '0x411ce0', '0x411d80', '0x411e20', '0x411ec0', '0x411f60', '0x412000', '0x4120a0', '0x412140', '0x4121d0', '0x410f50', '0x40fa60', '0x40f580', '0x40f4f0', '0x40f450', '0x40f3c0', '0x40f330', '0x40f290', '0x40f1f0', '0x40f150', '0x40f0c0', '0x40f020', '0x40ef80', '0x40eef0', '0x40ee50', '0x40edb0', '0x40ed20', '0x40ec80', '0x40ebf0', '0x40eb50', '0x40eac0', '0x40ea20', '0x40e990', '0x40e8f0', '0x40e850', '0x40e7b0', '0x40e710', '0x40e670', '0x40e5d0', '0x40e530', '0x40e490', '0x40e3f0', '0x40e350', '0x40e2b0', '0x40e220', '0x40e180', '0x40e0e0', '0x40e040', '0x40dfb0', '0x40df10', '0x40de70', '0x40ddd0', '0x40dd40', '0x40dca0', '0x40dc00', '0x40db60', '0x40dac0', '0x40da20', '0x40d980', '0x40d8e0', '0x40d840', '0x40d7a0', '0x40d700', '0x40f9c0', '0x40fe10', '0x4116b0', '0x412450', '0x4131e0', '0x413280', '0x413320', '0x4133c0', '0x413460', '0x4134f0', '0x4124f0', '0x411740', '0x40fea0', '0x40ff40', '0x40ffe0', '0x410080', '0x410120', '0x4117e0', '0x412590', '0x413590', '0x4139d0', '0x416820', '0x416780', '0x4166e0', '0x416640', '0x4165a0', '0x416500', '0x416460', '0x4163c0', '0x416320', '0x416280', '0x4168c0', '0x419110', '0x419370', '0x419fb0', '0x41a040', '0x41a0e0', '0x41a180', '0x41a220', '0x41a2c0', '0x41a350', '0x41a3f0', '0x41a490', '0x41a530', '0x41a5d0', '0x419410', '0x4191b0', '0x416960', '0x416a00', '0x416a90', '0x416b20', '0x416bc0', '0x416c60', '0x416d00', '0x416da0', '0x416e40', '0x416ee0', '0x416f80', '0x417010', '0x4170b0', '0x417150', '0x4171e0', '0x417280', '0x417320', '0x4173c0', '0x417460', '0x417500', '0x4175a0', '0x417640', '0x4176e0', '0x417780', '0x417820', '0x4178c0', '0x417960', '0x417a00', '0x417aa0', '0x417b30', '0x417bd0', '0x417c70', '0x417d10', '0x417da0', '0x417e30', '0x417ec0', '0x417f60', '0x418000', '0x4180a0', '0x418140', '0x4181e0', '0x418280', '0x418310', '0x4183b0', '0x418440', '0x4184e0', '0x418580', '0x418610', '0x4186b0', '0x419250', '0x4194b0', '0x41be60', '0x41bf90', '0x41c8e0', '0x41e1e0', '0x41e140', '0x41ea10', '0x41ebf0', '0x41f1e0']
dssddddddddddddddddddssssssssssdddddddddddddddddddddddddddddddwwwwwwaaaaaaaaassddddddssaaaaaaaaaaaaawwdddwwwwwddddddddddddddddddddddddddsssssssssssssssddddddddddddddddwwwwwwwwwwwwwaaaaaaawwwwddddddddddddssssssdsdsdsssasaasssssssaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaawaaasaaaaaaaaaaaaaaaaaaawwwwdddddddddddddddddddddsddddddddddddddwwwaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaasssssdddddwwwddddsssssaaaaaaaaassssddddddddddwwwddddddddddddddddddddddddddddddddddddddddddddddddssssssassss
DASCTF{0a80fbe4b623aa3c09173ecf9147601e}
```
>对于networkx的学习，可以参考此文档 https://www.osgeo.cn/networkx/tutorial.html
>
>对于求最短路径来说，基本就是
>
>1. 创建合适的图
>2. 添加节点，添加边
>3. 调用shortest_path，求出最短路径，这里求出的是经过的节点
>3. 然后再根据具体题目要求，根据经过的节点，把操作的步骤打印出来即可
## IDAAAAAA
### 分析
此题为今年L3HCTF的一道re题，题目仅给了一个i64文件，没有给可执行文件，IDA打开分析
`sub_401E97`函数返回1，则正确, 进入此函数发现有5个方程，用z3解
发现无解
再次观察，发现这里有个断点，来到断点窗口
发现是个条件断点，将conditon的数据复制出来
```python
global jIS40A
jIS40A = # 很长的密文 是个列表，长度是1000
N4QKUt = 0
EpUdLx = 4728923 # 0x048285B
idaapi.add_bpt(EpUdLx)# 0x048285B
uwGgnM = idaapi.bpt_t()
idaapi.get_bpt(EpUdLx, uwGgnM)
uwGgnM.elang = "Python"
uwGgnM.condition = "N4QKUt = {}\n".format(N4QKUt) + 'VLzxDy = idaapi.get_byte(5127584 + N4QKUt)\nVLzxDy -= ord(\'a\')\nif VLzxDy == 0:\n bYsMTa = 287\n LjzrdT = b\'lqAT7pNI3BX\'\nelif VLzxDy == 1:\n bYsMTa = 96\n LjzrdT = b\'z3Uhis74aPq\'\nelif VLzxDy == 2:\n bYsMTa = 8\n LjzrdT = b\'9tjseMGBHR5\'\nelif VLzxDy == 3:\n bYsMTa = 777\n LjzrdT = b\'FhnvgMQjexH\'\nelif VLzxDy == 4:\n bYsMTa = 496\n LjzrdT = b\'SKnZ51f9WsE\'\nelif VLzxDy == 5:\n bYsMTa = 822\n LjzrdT = b\'gDJy104BSHW\'\nelif VLzxDy == 6:\n bYsMTa = 914\n LjzrdT = b\'PbRV4rSM7fd\'\nelif VLzxDy == 7:\n bYsMTa = 550\n LjzrdT = b\'WHPnoMTsbx3\'\nelif VLzxDy == 8:\n bYsMTa = 273\n LjzrdT = b\'mLx5hvlqufG\'\nelif VLzxDy == 9:\n bYsMTa = 259\n LjzrdT = b\'QvKgNmUFTnW\'\nelif VLzxDy == 10:\n bYsMTa = 334\n LjzrdT = b\'TCrHaitRfY1\'\nelif VLzxDy == 11:\n bYsMTa = 966\n LjzrdT = b\'m26IAvjq1zC\'\nelif VLzxDy == 12:\n bYsMTa = 331\n LjzrdT = b\'dQb2ufTZwLX\'\nelif VLzxDy == 13:\n bYsMTa = 680\n LjzrdT = b\'Y6Sr7znOeHL\'\nelif VLzxDy == 14:\n bYsMTa = 374\n LjzrdT = b\'hLFj1wl5A0U\'\nelif VLzxDy == 15:\n bYsMTa = 717\n LjzrdT = b\'H6W03R7TLFe\'\nelif VLzxDy == 16:\n bYsMTa = 965\n LjzrdT = b\'fphoJwDKsTv\'\nelif VLzxDy == 17:\n bYsMTa = 952\n LjzrdT = b\'CMF1Vk7NH4O\'\nelif VLzxDy == 18:\n bYsMTa = 222\n LjzrdT = b\'43PSbAlgLqj\'\nelse:\n bYsMTa = -1\nif bYsMTa < 0:\n cpu.rsp -= 8\n cpu.rdi = 4927649\n cpu.rax = 0\n idaapi.patch_qword(cpu.rsp, 4202616)\n idaapi.del_bpt(cpu.rip)\n cpu.rip = 4263680\nelse:\n zaqhdD = 0x486195\n bYsMTa = jIS40A\n\n idaapi.patch_bytes(5117568, bYsMTa)\n idaapi.patch_bytes(5117488, LjzrdT)\n\n cpu.rsp -= 8\n idaapi.patch_qword(cpu.rsp, zaqhdD)\n cpu.rdi = 5117568\n cpu.rsi = len(bYsMTa)\n cpu.rdx = 5117488\n cpu.rcx = 11\n cpu.r8 = 5117568\n cpu.rax = 5117568\n\n idaapi.add_bpt(zaqhdD)\n jQfwUA = idaapi.bpt_t()\n idaapi.get_bpt(zaqhdD, jQfwUA)\n jQfwUA.elang = "Python"\n jQfwUA.condition = "N4QKUt = {}\\nSdjOr3 = {}\\n".format(N4QKUt, len(bYsMTa)) + \'bYsMTa = idaapi.get_bytes(cpu.rax, SdjOr3).decode()\\nzaqhdD = 4767838\\nidaapi.add_bpt(zaqhdD)\\njQfwUA = idaapi.bpt_t()\\nidaapi.get_bpt(zaqhdD, jQfwUA)\\njQfwUA.elang = "Python"\\njQfwUA.condition = "N4QKUt = {}\\\\n".format(N4QKUt+1) + bYsMTa\\nidaapi.del_bpt(zaqhdD)\\nidaapi.add_bpt(jQfwUA)\\nidaapi.del_bpt(cpu.rip)\\ncpu.rsp -= 8\\nidaapi.patch_qword(cpu.rsp, zaqhdD)\\ncpu.rip = 4447160\\n\'\n idaapi.del_bpt(zaqhdD)\n idaapi.add_bpt(jQfwUA)\n idaapi.del_bpt(cpu.rip)\n cpu.rip = 4201909\n'
idaapi.del_bpt(EpUdLx)
idaapi.add_bpt(uwGgnM) # 改为条件断点
cpu.rsp -= 8
idaapi.patch_qword(cpu.rsp, EpUdLx) # 0x48285B
cpu.rip = 4202096 #retn-->来到刚才条件断点的位置
```
可以发现，大致流程为，触发`0x40201F`处的断点的时候，设置一个新的条件断点，跳转过去，触发新的条件断点的condition，由此可见验证flag的算法全部在这些condition中
将`uwGgnM.condition` 稍作整理，然后分析
```python
N4QKUt = 0
VLzxDy = idaapi.get_byte(5127584 + N4QKUt)# 5127584(0x4e3da0) 为程序中输入的flag的地址flag
VLzxDy -= ord('a')
if VLzxDy == 0: # 根据VLzxDy初始化2个值
bYsMTa = 287 # jIS40A的索引
LjzrdT = b'lqAT7pNI3BX' # 解密 jIS40A 的key
elif VLzxDy == 1:
bYsMTa = 96
LjzrdT = b'z3Uhis74aPq'
elif VLzxDy == 2:
bYsMTa = 8
LjzrdT = b'9tjseMGBHR5'
elif VLzxDy == 3:
bYsMTa = 777
LjzrdT = b'FhnvgMQjexH'
elif VLzxDy == 4:
bYsMTa = 496
LjzrdT = b'SKnZ51f9WsE'
elif VLzxDy == 5:
bYsMTa = 822
LjzrdT = b'gDJy104BSHW'
elif VLzxDy == 6:
bYsMTa = 914
LjzrdT = b'PbRV4rSM7fd'
elif VLzxDy == 7:
bYsMTa = 550
LjzrdT = b'WHPnoMTsbx3'
elif VLzxDy == 8:
bYsMTa = 273
LjzrdT = b'mLx5hvlqufG'
elif VLzxDy == 9:
bYsMTa = 259
LjzrdT = b'QvKgNmUFTnW'
elif VLzxDy == 10:
bYsMTa = 334
LjzrdT = b'TCrHaitRfY1'
elif VLzxDy == 11:
bYsMTa = 966
LjzrdT = b'm26IAvjq1zC'
elif VLzxDy == 12:
bYsMTa = 331
LjzrdT = b'dQb2ufTZwLX'
elif VLzxDy == 13:
bYsMTa = 680
LjzrdT = b'Y6Sr7znOeHL'
elif VLzxDy == 14:
bYsMTa = 374
LjzrdT = b'hLFj1wl5A0U'
elif VLzxDy == 15:
bYsMTa = 717
LjzrdT = b'H6W03R7TLFe'
elif VLzxDy == 16:
bYsMTa = 965
LjzrdT = b'fphoJwDKsTv'
elif VLzxDy == 17:
bYsMTa = 952
LjzrdT = b'CMF1Vk7NH4O'
elif VLzxDy == 18:
bYsMTa = 222
LjzrdT = b'43PSbAlgLqj'
else:
bYsMTa = -1
if bYsMTa < 0: # Wrong的位置
cpu.rsp -= 8
cpu.rdi = 4927649 # 0x4b30a1: "O, no" # 传递参数
cpu.rax = 0
idaapi.patch_qword(cpu.rsp, 4202616) # leave retn
idaapi.del_bpt(cpu.rip)
cpu.rip = 4263680 # 0410F00 printf("O, no")
else:
zaqhdD = 0x486195
bYsMTa = jIS40A # 从一长串密文中取出数据
idaapi.patch_bytes(5117568, bYsMTa) # 0x4e1680# 取出的密文
idaapi.patch_bytes(5117488, LjzrdT) # 0x4e1630# 取出的key
# rdi, rsi, rdx, rcx, r8, r9
cpu.rsp -= 8
idaapi.patch_qword(cpu.rsp, zaqhdD) # 0x486195
# 设置参数
cpu.rdi = 5117568 # 0x4e1680 # 密文地址
cpu.rsi = len(bYsMTa) # 密文长度
cpu.rdx = 5117488 # 0x4e1630 # key地址
cpu.rcx = 11 # key长度
cpu.r8 = 5117568 # 0x4e1680 # 密文地址
cpu.rax = 5117568 # 0x4e1680 # 返回值
idaapi.add_bpt(zaqhdD)
jQfwUA = idaapi.bpt_t()
idaapi.get_bpt(zaqhdD, jQfwUA)
jQfwUA.elang = "Python"
jQfwUA.condition = "N4QKUt = {}\nSdjOr3 = {}\n".format(N4QKUt, len(bYsMTa)) + 'bYsMTa = idaapi.get_bytes(cpu.rax, SdjOr3).decode()\nzaqhdD = 4767838\nidaapi.add_bpt(zaqhdD)\njQfwUA = idaapi.bpt_t()\nidaapi.get_bpt(zaqhdD, jQfwUA)\njQfwUA.elang = "Python"\njQfwUA.condition = "N4QKUt = {}\\n".format(N4QKUt+1) + bYsMTa\nidaapi.del_bpt(zaqhdD)\nidaapi.add_bpt(jQfwUA)\nidaapi.del_bpt(cpu.rip)\ncpu.rsp -= 8\nidaapi.patch_qword(cpu.rsp, zaqhdD)\ncpu.rip = 4447160\n'
idaapi.del_bpt(zaqhdD)
idaapi.add_bpt(jQfwUA)
idaapi.del_bpt(cpu.rip)
cpu.rip = 4201909#0x401db5 # 5个参数 先执行解密，然后再->0x486195(因为上面已经把cpu.esp-8的位置改为了0x486195), 触发条件断点
```
可以发现流程就是，根据输入的flag的每个字符，来判断进入下一个节点
解密函数是一个简单的异或, 先随便找几个解密看看，key的长度都是11
```python
def dec(_x, _key):
m = []
for i in range(len(encs)):
m.append(encs ^ ord(_key))
print(bytes(m).decode())
dec(287,'lqAT7pNI3BX')
print('===============================================================')
dec(96, 'z3Uhis74aPq')
```
```python
NyPGpw = idaapi.get_byte(5127584 + N4QKUt)
NyPGpw -= ord('a')
if NyPGpw == 0:
afvkwL = 667
hsYnNw = b'vjHiPd4bBuf'
elif NyPGpw == 1:
afvkwL = 667
hsYnNw = b'vjHiPd4bBuf'
elif NyPGpw == 2:
afvkwL = 667
hsYnNw = b'vjHiPd4bBuf'
else:
afvkwL = -1
if afvkwL < 0:
cpu.rsp -= 8
cpu.rdi = 4927649
cpu.rax = 0
idaapi.patch_qword(cpu.rsp, 4202616)
idaapi.del_bpt(cpu.rip)
cpu.rip = 4263680
else:
RrNlIm = 0x4438d8
afvkwL = jIS40A
idaapi.patch_bytes(5117568, afvkwL)
idaapi.patch_bytes(5117488, hsYnNw)
cpu.rsp -= 8
idaapi.patch_qword(cpu.rsp, RrNlIm)
cpu.rdi = 5117568
cpu.rsi = len(afvkwL)
cpu.rdx = 5117488
cpu.rcx = 11
cpu.r8 = 5117568
cpu.rax = 5117568
idaapi.add_bpt(RrNlIm)
XKDdOn = idaapi.bpt_t()
idaapi.get_bpt(RrNlIm, XKDdOn)
XKDdOn.elang = "Python"
XKDdOn.condition = "N4QKUt = {}\nSdjOr3 = {}\n".format(N4QKUt, len(afvkwL)) + 'afvkwL = idaapi.get_bytes(cpu.rax, SdjOr3).decode()\nRrNlIm = 4370382\nidaapi.add_bpt(RrNlIm)\nXKDdOn = idaapi.bpt_t()\nidaapi.get_bpt(RrNlIm, XKDdOn)\nXKDdOn.elang = "Python"\nXKDdOn.condition = "N4QKUt = {}\\n".format(N4QKUt+1) + afvkwL\nidaapi.del_bpt(RrNlIm)\nidaapi.add_bpt(XKDdOn)\nidaapi.del_bpt(cpu.rip)\ncpu.rsp -= 8\nidaapi.patch_qword(cpu.rsp, RrNlIm)\ncpu.rip = 4220940\n'
idaapi.del_bpt(RrNlIm)
idaapi.add_bpt(XKDdOn)
idaapi.del_bpt(cpu.rip)
cpu.rip = 4201909
===============================================================
XxrupR = idaapi.get_byte(5127584 + N4QKUt)
XxrupR -= ord('a')
if XxrupR == 0:
SAoBHX = 667
EOlVWv = b'vjHiPd4bBuf'
elif XxrupR == 1:
SAoBHX = 667
EOlVWv = b'vjHiPd4bBuf'
elif XxrupR == 2:
SAoBHX = 667
EOlVWv = b'vjHiPd4bBuf'
else:
SAoBHX = -1
if SAoBHX < 0:
cpu.rsp -= 8
cpu.rdi = 4927649
cpu.rax = 0
idaapi.patch_qword(cpu.rsp, 4202616)
idaapi.del_bpt(cpu.rip)
cpu.rip = 4263680
else:
uBEeMD = 0x45e68a
SAoBHX = jIS40A
idaapi.patch_bytes(5117568, SAoBHX)
idaapi.patch_bytes(5117488, EOlVWv)
cpu.rsp -= 8
idaapi.patch_qword(cpu.rsp, uBEeMD)
cpu.rdi = 5117568
cpu.rsi = len(SAoBHX)
cpu.rdx = 5117488
cpu.rcx = 11
cpu.r8 = 5117568
cpu.rax = 5117568
idaapi.add_bpt(uBEeMD)
piHsvj = idaapi.bpt_t()
idaapi.get_bpt(uBEeMD, piHsvj)
piHsvj.elang = "Python"
piHsvj.condition = "N4QKUt = {}\nSdjOr3 = {}\n".format(N4QKUt, len(SAoBHX)) + 'SAoBHX = idaapi.get_bytes(cpu.rax, SdjOr3).decode()\nuBEeMD = 4808702\nidaapi.add_bpt(uBEeMD)\npiHsvj = idaapi.bpt_t()\nidaapi.get_bpt(uBEeMD, piHsvj)\npiHsvj.elang = "Python"\npiHsvj.condition = "N4QKUt = {}\\n".format(N4QKUt+1) + SAoBHX\nidaapi.del_bpt(uBEeMD)\nidaapi.add_bpt(piHsvj)\nidaapi.del_bpt(cpu.rip)\ncpu.rsp -= 8\nidaapi.patch_qword(cpu.rsp, uBEeMD)\ncpu.rip = 4405922\n'
idaapi.del_bpt(uBEeMD)
idaapi.add_bpt(piHsvj)
idaapi.del_bpt(cpu.rip)
cpu.rip = 4201909
```
可以发现都符合一个框架
```
xxxx = idaapi.get_byte(5127584 + N4QKUt)
xxxx -= ord('a')
if xxxx == 0:
afvkwL = 667
hsYnNw = b'vjHiPd4bBuf'
elif xxxx == 1:
afvkwL = 667
hsYnNw = b'vjHiPd4bBuf'
.......
else:
afvkwL = -1
if afvkwL < 0:
........
```
因为解密出来都含有`idaapi.get_byte(5127584 + N4QKUt)`，而key的长度都是11，因此可以对key全部爆破出来
```python
encs = [....]
def get_keys():
sign = ]
keys = *1000 # encs的长度是1000， 对应1000个key
for i in range(len(encs)):
tmp = encs
tmp_key = ^ sign for j in range(11)] # 获得key
sign_1 = ^ encs for j in range(11)]
if b'= id' in bytes(sign_1):
keys = bytes(tmp_key)
else:
keys = None # i = 426
return keys
keys = get_keys()
print(keys.count(None)) # 1
```
只有1个节点没有解密成功，即没有指向，应该就是终点，结合题目，是个最短路径问题
终点的索引是426，写脚本找到索引426的key
```python
def dec(_src, _key):
m = []
for i in range(len(_src)):
m.append(_src ^ _key)
return bytes(m).decode("utf-8")
def get_keys():
sign = ]
keys = *1000 # encs的长度是1000， 对应1000个key
for i in range(len(encs)):
tmp = encs
tmp_key = ^ sign for j in range(11)] # 获得key
sign_1 = ^ encs for j in range(11)]
if b'= id' in bytes(sign_1):
keys = bytes(tmp_key)
else:
keys = None
return keys
def get_node_edges(_dec_src): # 获取每条边，2个点即构成一条边
# 传入解密后的脚本
i = _dec_src.index('<')
_dec_src = _dec_src[:i]
m = re.findall(r' = (\d+)', _dec_src)
nodes =
return nodes
keys = get_keys()
for i, value in enumerate(encs):
if keys == None:
target_node = i
else:
dec_src = dec(value, keys)
nodes = get_node_edges(dec_src)
# 添加边
for j in range(len(nodes)):
if nodes==426:
print(i)
print(dec_src)
exit()
# 705
# GKjYbv = idaapi.get_byte(5127584 + N4QKUt)
# GKjYbv -= ord('a')
# if GKjYbv == 0:
# NizaZl = 426
# BCTfiu = b'akUx3IWl29V'
# else:
# ......
```
key为`akUx3IWl29V`, 解密得到
```python
idaapi.del_bpt(cpu.rip)
cpu.rax = 0
cpu.rip = 4202594 # 0x402062
```
是终点无疑了，现在需要找出所有的节点，以及边（2个节点就是1个边，有方向）,然后用networkx求解
### networkx求最短路径
直接贴脚本了，就是通过正则表达式匹配出node,然后构造边，添加边，用networkx求出路径，再写出控制方向的的flag字符即可
```python
import re
import networkx
import hashlib
encs = [....]
def dec(_src, _key):
m = []
for i in range(len(_src)):
m.append(_src ^ _key)
return bytes(m).decode("utf-8")
def get_keys():
sign = ]
keys = *1000 # encs的长度是1000， 对应1000个key
for i in range(len(encs)):
tmp = encs
tmp_key = ^ sign for j in range(11)] # 获得key
sign_1 = ^ encs for j in range(11)]
if b'= id' in bytes(sign_1):
keys = bytes(tmp_key)
else:
keys = None
return keys
def get_node_edges(_dec_src): # 获取每个节点指向的其他的节点，然后通过此来获取边
# 传入解密后的脚本
i = _dec_src.index('<')
_dec_src = _dec_src[:i]
m = re.findall(r' = (\d+)', _dec_src)
nodes =
return nodes
keys = get_keys()
edges = []
node2node = []
for i, value in enumerate(encs):
if keys == None:
target_node = i # 终点
nodes = []
else:
dec_src = dec(value, keys)
nodes = get_node_edges(dec_src)
# 添加边
for j in range(len(nodes)): # 根据获取的指向的节点来添加边
edges.append(])
node2node.append(nodes)
src_node = -1 # 最开始还有1个节点
src_edge =
# 将最初的边添加进去
for i in src_edge:
edges.append()
G = networkx.DiGraph()
G.add_node(-1)
for i in range(len(encs)):
G.add_node(i)
for i in edges:
G.add_edge(i, i)
path = networkx.shortest_path(G, source=src_node, target=target_node)
print(path) # 打印出路径来
s = []
s.append(src_edge.index(path))
for i in range(2, len(path)):
s.append(node2node].index(path))
print(s)
s = "".join()
print(s)
print("L3HCTF{" + hashlib.md5(s.encode()).hexdigest() + "}")
# [-1, 331, 578, 255, 875, 765, 687, 209, 119, 963, 939, 443, 250, 366, 65, 504, 920, 849, 720, 893, 728, 580, 114, 665, 72, 51, 241, 519, 473, 970, 984, 557, 90, 793, 487, 67, 428, 236, 263, 24, 39, 104, 505, 491, 95, 223, 486, 798, 873, 872, 64, 229, 37, 274, 329, 601, 372, 750, 446, 3, 332, 698, 277, 740, 816, 845, 570, 828, 21, 36, 839, 770, 343, 451, 151, 994, 937, 760, 644, 9, 614, 302, 454, 153, 840, 76, 424, 352, 950, 238, 613, 497, 898, 858, 415, 205, 393, 927, 522, 705, 426]
# [12, 2, 0, 4, 1, 0, 2, 4, 3, 0, 0, 1, 5, 0, 2, 0, 2, 0, 1, 6, 0, 6, 1, 1, 0, 0, 4, 0, 2, 0, 1, 2, 1, 0, 2, 4, 1, 0, 6, 0, 0, 0, 1, 2, 3, 1, 6, 1, 3, 1, 2, 1, 3, 0, 2, 6, 0, 1,
# 5, 1, 1, 4, 1, 0, 1, 0, 1, 1, 1, 1, 1, 2, 0, 0, 1, 3, 0, 1, 0, 1, 0, 5, 0, 2, 2, 0, 2, 3, 0, 6, 3, 0, 0, 1, 0, 1, 0, 0, 0, 0]
# mcaebacedaabfacacabgagbbaaeacabcbacebagaaabcdbgbdbcbdacgabfbbebababbbbbcaabdababafaccacdagdaababaaaa
# L3HCTF{6584ed9fd9497981117f22a6c572caee}
```
flag为 `L3HCTF{6584ed9fd9497981117f22a6c572caee}`
>参考： https://www.anquanke.com/post/id/259494#h3-2 奈何文化有限，只能一句“卧槽，牛皮”表示对大佬的敬仰。{:301_993:} 不错学习了 经典文章
经典文章 mark学习下 牛，学习中！！！！ 大佬牛牛牛{:1_918:} 很厉害，学习了 额，看着好深奥复杂的感觉啊