Đây là report nho nhỏ về task của a mochi đã giao cho mình:

BFS and DFS

Để mình nói sơ về phần thuật toán trước:

Qua nhiều lần chơi nhiều bài rev khác nhau, mình thấy bfs và dfs chúng ta sẽ gặp tương đối nhiều, chủ yếu là các bài tìm đường đi, blind maze,…

Đặt điểm chung của các bài này giống như programing bình thường, tuy nhiên với mỗi bài sẽ có cách biểu diễn các node và các step khác nhau. Để tổng quan lại các bạn có thể hình dung như thế này:

BFS:
Bắt đầu từ root node, duyệt tất cả các node lân cận cùng mức rồi mới bắt đầu duyệt mức tiếp theo. Tương ứng với duyệt theo chiều rộng.

DFS:
Bắt đầu từ root node, duyệt theo 1 node theo 1 đường xa nhất có thể trước khi duyệt các node lân cận. Tương ứng với duyệt theo chiều sâu.

Do đó, điểm khác biệt lớn nhất giữa 2 cách duyệt này là cấu trúc dữ liệu mà nó sử dụng.

BFS: sử dụng queue(FIFO): mỗi lần duyêt một node, nó sẽ push node đó vào sau hàng đợi, và lấy node ở đầu hàng đợi ra để duyệt=> do đó nó sẽ duyệt tất cả các node lân cận trước khi tới mức tiếp theo.

DFS: sử dụng stack (LIFO): mỗi lận duyệt một node, nó cũng sẽ push node đó vào stack, tuy nhiên ở lần duyệt tiếp theo, nó sẽ lại lấy chính node đó ra => đồng nghĩa nó sẽ tăng lên một mức so với node cũ và duyệt trên chính node cũ, hay nói cách khác là đang duyệt theo chiều sâu.

Tuỳ theo từng bài mà áp dụng thuật toán tương ứng nhé.

Các bạn có thể tham khảo thêm tại:
https://www.geeksforgeeks.org/difference-between-bfs-and-dfs/

def bfs(graph, start_node):
    visited = set()
    queue = [start_node]
    while queue:
        node = queue.pop(0)
        if node not in visited:
            print(node, end=' ')
            visited.add(node)
            for neighbor in graph[node]:
                if neighbor not in visited:
                    queue.append(neighbor)

def dfs(graph, start_node):
    visited = set()
    stack = [start_node]
    while stack:
        node = stack.pop()
        if node not in visited:
            print(node, end=' ')
            visited.add(node)
            for neighbor in graph[node]:
                if neighbor not in visited:
                    stack.append(neighbor)

oops

Riêng đối với bài oops, array G_S sẽ tương ứng với 82 node trong graph

Đọc 12 byte input, nghĩa là số bước đi tối đa là 12 bước để tìm flag.

Ở root node, từng trường hợp của input sẽ tương ứng với từng function khác nhau (pfunc8,pfunc10,pfunc18…)

Ở mỗi node sẽ có 6 function, tương ứng với 6 node khác nhau có thể nhảy tới.
Một swicth case để nhảy và 1 hàm mod (modify, cái này mình sẽ nói sau).

Để tính được các node lân cận là gì, thì ở trong 6 hàm đó sẽ có các instruction, ví dụ như:

add rax, 78h
hoặc là
sub rax, 30h
…

Mỗi hàm sẽ có 1 cách nhảy khác nhau, dựa trên cái số mà nó cộng hoặc trừ, tuy nhiên thì nó cũng chỉ để phục vụ mục đích là nhảy tới các node lân cận.

Về phần này, mình dùng code có sẵn của a mochi và comment lại cho các bạn hiểu:

if code.find(b'\x48\x05') != -1 or code.find(b'\x48\x83\xc0') != -1 or code.find(
                    b'\x48\x83\xe8') != -1 or code.find(b'\x48\x2d') != -1:
                if code.find(b'\x48\x05') != -1: ## add rax, n
                    id = code.find(b'\x48\x05')
                    add = u32(get_bytes(func_addr + id + 2, 4)) // 8
                elif code.find(b'\x48\x2d') != -1: ## sub rax, n
                    id = code.find(b'\x48\x2d')
                    add = -(u32(get_bytes(func_addr + id + 2, 4)) // 8)
                elif code.find(b'\x48\x83\xc0') != -1: #add byte
                    id = code.find(b'\x48\x83\xc0') 
                    add = u8(get_bytes(func_addr + id + 3, 1)) // 8
                elif code.find(b'\x48\x83\xe8') != -1: #sub byte
                    id = code.find(b'\x48\x83\xe8')
                    add = -(u8(get_bytes(func_addr + id + 3, 1)) // 8)

Từ các số lấy được này có thể tính ra bước nhảy tiếp theo (vtable tiếp theo).

Sau khi biết được vtable tiếp theo là gì, nó sẽ set vtable tương ứng để duyệt node đó

Tiếp tục cho tới khi tìm được vtable có hàm cat flag (end):

Về phần lấy địa chỉ node tiếp theo và jump tới các node mình sẽ dùng lại script cũ của a mochi, đây là script của ảnh:

Cách của a mochi làm là dùng bfs, và bắt đầu loại trừ cho tới khi tìm được 1 đường đi đúng, tại sao lại là đường đi đúng?
Bởi vì trong quá trình duyệt, có nhiều trường hợp trả về đường đi đúng, tuy nhiên, ở mỗi node có 1 hàm mod, hàm này sẽ ảnh hưởng trực tiếp đến chuyện rằng node tiếp theo nó sẽ đi được những bước nào, không phải là tất cả 6 bước đều có thể đi.

Vì phù hợp với thời gian thi 8 tiếng nên cách trên hợp lí hơn, tuy nhiên vì mình có thời gian nhiều hơn nên mình sẽ nói kĩ hơn về cái này.

Mỗi lần nhảy tới 1 node khác, nó sẽ dùng hàm mod của node hiện tại, modify input[i] của mình và sau đó mới gọi switch case của node tiếp theo.

Ví dụ ở hàm mod1:

ta có switch (mod1(inp[1])) trong đó mod1 sẽ trả về kết quả của inp[1]^0x5b

Tuy nhiên, hàm mod 2 lại có thêm đặt điểm là or 1, ah:

Nghĩa là ở node thứ 3, nó sẽ là swith (mod2(inp[2])) trong đó mod 2 trả về kết quả có dạng: 0x1XX.

Nhưng các bạn có thể dễ dàng nhìn thấy rằng switch case lại có những case 0x2XX, đó sẽ là những node không thể nhảy tới.

Và một số hàm mod khác, nó sẽ or với 1 số có thể là 0x200 hoặc 0x100 để quyết định xem ở node tiếp theo nó có thể nhảy tới hàm nào.

Do đó điểm mấu chốt bài này là làm sao biết được hàm nào nó có thể nhảy hoặc không.

Mình đã viết 1 hàm Get_word, điều này giúp mình biết được node vừa đi qua có word là bao nhiêu (0x200 hoặc 0x100).

def Get_word(start):
    mod_addr = get_qword(start) 
    # print(hex(start))
    mod_byte = get_bytes(mod_addr,100)
    if start==0x29488 + base:# table 2 and table 1
        return True
    if start==base + 0x29430:
        return 0x100
    ins = mod_byte.index(b'\x0f\xb7\x05')
    word_idx = u32(mod_byte[ins+3:ins+7])
    word_idx = mod_addr + ins + 7 + word_idx
    word = u16(get_bytes(word_idx,2))
    return word

và trong mỗi node mình sẽ thêm last để biết rằng word của node vừa rồi là gì, làm dữ kiện để kiệm tra xem những node nào có thể nhảy tới.

direction, level, start, move, bs,last = queue.pop(0)
new_last = Get_word(start)
        queue.append((new_dir, level+1, new_start, new_pos,new_bs,new_last))

Và điểm mấu chốt của bài này là hàm can_step, cái mà chúng ta cần biết xem node tiếp theo có thể đi được hay không.

def can_step(start:int,step:int,last_step:int)->bool:
    # print(hex(word),hex(word_idx))
    if start==base + 0x29488 or start== 0x29430 + base:
        return True
    sw_addr = get_qword(start + 8*7)
    sw_byte = get_bytes(sw_addr,500)
    dic ={}
    for i in range(200-10):
        if sw_byte[i]==0x3d and (sw_byte[i+5:i+7]==b'\x0f\x84' or sw_byte[i+5]==0x74 or sw_byte[i+5:i+7]==b'\x0f\x85'):
            number =u32(sw_byte[i+1:i+5])
            if sw_byte[i+5:i+7]==b'\x0f\x84':
                j_addr = sw_addr+i + u32(get_bytes(sw_addr+i+7,4))+11
                j_byte = get_bytes(j_addr,14)
                dic[get_step(j_byte)] = number
            elif sw_byte[i+5]==0x74:
                j_addr = sw_addr+i + u8(get_bytes(sw_addr+i+6,1))+7
                j_byte = get_bytes(j_addr,14)
                dic[get_step(j_byte)] = number
            elif sw_byte[i+5:i+7]==b'\x0f\x85':
                j_byte = get_bytes(sw_addr+i+11,14)
                dic[get_step(j_byte)] = number
    if step not in dic.keys():
        # print(dic,start)
        return False
        # if start ==0x564BD51ECE88:
        #     print(dic,step,last_step)
        #     if step==6:
        #         exit(0)
    cur_step_word = dic[step]
    if (last_step>>8)==(cur_step_word>>8):
        return True
    return False

Ý tưởng của đoạn này là:

Trong mỗi switch case đều có chung một format như thế này:

6 Lệnh jz tương ứng với 6 bước nhảy tiếp theo, mình có thể extract number từ đây ra.

Tiếp theo, cần check xem từng number này tương ứng với function nào (bước từ (1->6)):

Tương ứng với mỗi lable, mình sẽ extract thêm được offset của các function thông qua lệnh add:

add rax, 30h -> 6
..
add rax, 10h -> 2
..
add rax, 28h -> 5

Rồi mình dựa vào các số này và kiểm tra được bước nhảy đó có hợp lệ hay không:

cur_step_word = dic[step]

if (last_step>>8)==(cur_step_word>>8):
        return True

Từ đây có thể dễ dàng chạy code và tìm được đường đi tương ứng, tuy nhiên vì mỗi lần nhảy, input mình xor với 1 số mà mình ko biết, nên là mình đã viết thêm 1 hàm để extract mấy cái số này ra:

def get_value(start):
    if start == 0x29488+base: #table 1
        return 0x5b
    if start == 0x29430 + base: #table 2
        return 0xA3
    mod_addr = get_qword(start)
    mod_byte = get_bytes(mod_addr,100)
    ins = mod_byte.index(b'\x8b\x05')
    dword_idx = u32(mod_byte[ins+2:ins+6])
    dword_idx = mod_addr + ins + 6 + dword_idx
    b = u32(get_bytes(dword_idx,4))
    return b

direction = '11211111453'
# inp = [ord('A')]
# inp.append(0x5B^stage[direction[1]])
# inp.append(0xA3^stage2[direction[2]])
# inp.append(0xC1^stage3[direction[3]])
# inp.append(0xB6^stage3[direction[3]])

x = [0,91, 163, 193, 24, 33, 207, 156, 169, 247, 202, 145]
inp = []
inp.append(ord('A')^x[0]) #1
inp.append(0x1A^x[1]) #1
inp.append(0x45^x[2]) #2
inp.append(0x9A^x[3]) #1
inp.append(0x91^x[4]) #1
inp.append(0xAC^x[5]) #1
inp.append(0x28^x[6]) #1
inp.append(0x7f^x[7]) #1
inp.append(0xd1^x[8]) #4
inp.append(0x38^x[9]) #5
inp.append(0x28^x[10]) #3
inp.append(0)
print(bytes(inp))

Với các số 0x1A, 0x45 tương ứng là các số trong sw_case, từ đó có được input hợp lí và lấy flag.

from pwn import *
io = process('./oops')
# io = process('35.187.245.7',32010)
io.sendline(b'AA\xe6[\x89\x8d\xe7\xe3x\xcf\xe2')
io.interactive()

Về phần DFS, mình chỉ cần đổi cấu trúc dữ liệu lại thành stack, và cho ra kết quả khác, nhưng vẫn đúng. Cách này thì dùng phương pháp loại trừ như của a mochi cũng khá là hiệu quả.

Full script:

Script a mochi:

# bfs

something = [0] * 82
something[0] = 0x55555556C449;
something[1] = 0x55555556C4FD;
something[2] = 0x55555556C5B1;
something[3] = 0x55555556C665;
something[4] = 0x55555556C719;
something[5] = 0x55555556C7CD;
something[6] = 0x55555556C881;
something[7] = 0x55555556C935;
something[8] = 0x55555556C9E9;
something[9] = 0x55555556CA9D;
something[10] = 0x55555556CB51;
something[11] = 0x55555556CC05;
something[12] = 0x55555556CCB9;
something[13] = 0x55555556CD6D;
something[14] = 0x55555556CE21;
something[15] = 0x55555556CED5;
something[16] = 0x55555556CF89;
something[17] = 0x55555556D03D;
something[18] = 0x55555556D0F1;
something[19] = 0x55555556D1A5;
something[20] = 0x55555556D259;
something[21] = 0x55555556D30D;
something[22] = 0x55555556D3C1;
something[23] = 0x55555556D475;
something[24] = 0x55555556D529;
something[25] = 0x55555556D5DD;
something[26] = 0x55555556D691;
something[27] = 0x55555556D745;
something[28] = 0x55555556D7F9;
something[29] = 0x55555556D8AD;
something[30] = 0x55555556D961;
something[31] = 0x55555556DA15;
something[32] = 0x55555556DAC9;
something[33] = 0x55555556DB7D;
something[34] = 0x55555556DC31;
something[35] = 0x55555556DCE5;
something[36] = 0x55555556DD99;
something[37] = 0x55555556DE4D;
something[38] = 0x55555556DF01;
something[39] = 0x55555556DFB5;
something[40] = 0x55555556E069;
something[41] = 0x55555556E11D;
something[42] = 0x55555556E1D1;
something[43] = 0x55555556E285;
something[44] = 0x55555556E339;
something[45] = 0x55555556E3ED;
something[46] = 0x55555556E4A1;
something[47] = 0x55555556E555;
something[48] = 0x55555556E609;
something[49] = 0x55555556E6BD;
something[50] = 0x55555556E771;
something[51] = 0x55555556E825;
something[52] = 0x55555556E8D9;
something[53] = 0x55555556E947;
something[54] = 0x55555556E9FB;
something[55] = 0x55555556EAAF;
something[56] = 0x55555556EB63;
something[57] = 0x55555556EC17;
something[58] = 0x55555556ECCB;
something[59] = 0x55555556ED7F;
something[60] = 0x55555556EE33;
something[61] = 0x55555556EEE7;
something[62] = 0x55555556EF9B;
something[63] = 0x55555556F04F;
something[64] = 0x55555556F103;
something[65] = 0x55555556F1B7;
something[66] = 0x55555556F26B;
something[67] = 0x55555556F31F;
something[68] = 0x55555556F3D3;
something[69] = 0x55555556F487;
something[70] = 0x55555556F53B;
something[71] = 0x55555556F5EF;
something[72] = 0x55555556F6A3;
something[73] = 0x55555556F757;
something[74] = 0x55555556F80B;
something[75] = 0x55555556F8BF;
something[76] = 0x55555556F973;
something[77] = 0x55555556FA27;
something[78] = 0x55555556FADB;
something[79] = 0x55555556FB8F;
something[80] = 0x55555556FC43;
something[81] = 0x55555556FCF7;

from pwn import *

start = 0x55555557D488
queue = [('', 0, start, 0)]
visited = []
cou = 0

while 1:
    cou += 1
    if len(queue) == 0: break

    direction, level, start, move = queue[0]
    if queue[0] == ('112', 3, 0x55555557cfb8, 80): break
    k = queue.pop(0)
    if (level, start) in visited: continue
    visited.append((level, start))
    print(f'({direction}, {level}, {hex(start)}, {move}) ', end='')


    if 0x55555557BAC0 == start:
        print(direction)
        print('found')
        exit(0)

    struct_start = start + 8  # directions function
    original_pos = level * 4
    for i in range(6):
        addr = idaapi.get_qword(struct_start + i * 8)
        code = get_bytes(addr, 50)
        new_pos = original_pos
        add = 0
        # print(new_pos, end = ' ')
        if code.find(b'\x48\x05') != -1 or code.find(b'\x48\x83\xc0') != -1 or code.find(
                b'\x48\x83\xe8') != -1 or code.find(b'\x48\x2d') != -1:
            if code.find(b'\x48\x05') != -1:
                id = code.find(b'\x48\x05')
                add = u32(get_bytes(addr + id + 2, 4)) // 8
            elif code.find(b'\x48\x2d') != -1:
                id = code.find(b'\x48\x2d')
                add = -(u32(get_bytes(addr + id + 2, 4)) // 8)
            elif code.find(b'\x48\x83\xc0') != -1:
                id = code.find(b'\x48\x83\xc0')
                add = u8(get_bytes(addr + id + 3, 1)) // 8
            elif code.find(b'\x48\x83\xe8') != -1:
                id = code.find(b'\x48\x83\xe8')
                add = -(u8(get_bytes(addr + id + 3, 1)) // 8)
        # finding new_start
        new_dir = direction + str(i + 1)
        if len(new_dir) == 3 and new_dir == '111': continue
        if len(new_dir) == 3 and new_dir == '114': continue
        if len(new_dir) == 3 and new_dir == '115': continue
        if len(new_dir) == len('112111112') and new_dir == '112111113': continue
        if len(new_dir) == len('112111111') and new_dir == '112111112': continue
        if len(new_dir) == len('112111111') and new_dir == '112111115': continue
        if len(new_dir) == len('1121111113') and new_dir == '1121111111': continue
        if len(new_dir) == len('1121111113') and new_dir == '1121111114': continue
        if len(new_dir) == len('1121111113') and new_dir == '1121111116': continue
        if len(new_dir) == len('1121111144') and new_dir == '1121111144': continue
        if len(new_dir) == len('1121111144') and new_dir == '1121111141': continue
        if len(new_dir) == len('1121111144') and new_dir == '1121111142': continue
        if len(new_dir) == len('11211111152') and new_dir == '11211111151': continue
        if len(new_dir) == len('11211111152') and new_dir == '11211111152': continue
        if len(new_dir) == len('11211111152') and new_dir == '11211111153': continue
        if len(new_dir) == len('11211111152') and new_dir == '11211111132': continue
        if len(new_dir) == len('11211111152') and new_dir == '11211111134': continue
        if len(new_dir) == len('11211111152') and new_dir == '11211111136': continue
        new_pos += add

        if level + 1 > 12: continue
        if new_pos > len(something) - 1 or new_pos < 0: continue
        id = something[new_pos] - 17
        new_start = u32(get_bytes(id + 3, 4)) + id + 7
        queue.append((new_dir, level + 1, new_start, new_pos))

Script BFS:

from pwn import *
base = idaapi.get_imagebase()
G_S = [99401, 99581, 99761, 99941, 100121, 100301, 100481, 100661, 100841, 101021, 101201, 101381, 101561, 101741, 101921, 102101, 102281, 102461, 102641, 102821, 103001, 103181, 103361, 103541, 103721, 103901, 104081, 104261, 104441, 104621, 104801, 104981, 105161, 105341, 105521, 105701, 105881, 106061, 106241, 106421, 106601, 106781, 106961, 107141, 107321, 107501, 107681, 107861, 108041, 108221, 108401, 108581, 108761, 108871, 109051, 109231, 109411, 109591, 109771, 109951, 110131, 110311, 110491, 110671, 110851, 111031, 111211, 111391, 111571, 111751, 111931, 112111, 112291, 112471, 112651, 112831, 113011, 113191, 113371, 113551, 113731, 113911]
G_S = [G_S[i]+ base for i in range(82)]
#things these function do:
#   - get next data
#   - call func_8_general
#   - allow something?
#   - set own vtable
# print(G_S)
def get_step(j_byte):
    if b'\x48\x83\xC0\x08\x48' in j_byte:
        return 1
    if b'\x48\x83\xC0\x10\x48' in j_byte:
        return 2
    if b'\x48\x83\xC0\x18\x48' in j_byte:
        return 3
    if b'\x48\x83\xC0\x20\x48' in j_byte:
        return 4
    if b'\x48\x83\xC0\x28\x48' in j_byte:
        return 5
    if b'\x48\x83\xC0\x30\x48' in j_byte:
        return 6

def Get_word(start):
    mod_addr = get_qword(start) 
    # print(hex(start))
    mod_byte = get_bytes(mod_addr,100)
    if start==0x29488 + base:# table 2 and table 1
        return True
    if start==base + 0x29430:
        return 0x100
    ins = mod_byte.index(b'\x0f\xb7\x05')
    word_idx = u32(mod_byte[ins+3:ins+7])
    word_idx = mod_addr + ins + 7 + word_idx
    word = u16(get_bytes(word_idx,2))
    return word
def can_step(start:int,step:int,last_step:int)->bool:
    # print(hex(word),hex(word_idx))
    if start==base + 0x29488 or start== 0x29430 + base:
        return True
    sw_addr = get_qword(start + 8*7)
    sw_byte = get_bytes(sw_addr,500)
    dic ={}
    for i in range(200-10):
        if sw_byte[i]==0x3d and (sw_byte[i+5:i+7]==b'\x0f\x84' or sw_byte[i+5]==0x74 or sw_byte[i+5:i+7]==b'\x0f\x85'):
            number =u32(sw_byte[i+1:i+5])
            if sw_byte[i+5:i+7]==b'\x0f\x84':
                j_addr = sw_addr+i + u32(get_bytes(sw_addr+i+7,4))+11
                j_byte = get_bytes(j_addr,14)
                dic[get_step(j_byte)] = number
            elif sw_byte[i+5]==0x74:
                j_addr = sw_addr+i + u8(get_bytes(sw_addr+i+6,1))+7
                j_byte = get_bytes(j_addr,14)
                dic[get_step(j_byte)] = number
            elif sw_byte[i+5:i+7]==b'\x0f\x85':
                j_byte = get_bytes(sw_addr+i+11,14)
                dic[get_step(j_byte)] = number
    if step not in dic.keys():
        # print(dic,start)
        return False
        # if start ==0x564BD51ECE88:
        #     print(dic,step,last_step)
        #     if step==6:
        #         exit(0)
    cur_step_word = dic[step]
    if (last_step>>8)==(cur_step_word>>8):
        return True
    return False

def get_value(start):
    if start == 0x29488+base: #table 1
        return 0x5b
    if start == 0x29430 + base: #table 2
        return 0xA3
    mod_addr = get_qword(start)
    mod_byte = get_bytes(mod_addr,100)
    ins = mod_byte.index(b'\x8b\x05')
    dword_idx = u32(mod_byte[ins+2:ins+6])
    dword_idx = mod_addr + ins + 6 + dword_idx
    b = u32(get_bytes(dword_idx,4))
    return b

start = 0x29488 + base
end = 0x27ac0 + base

queue = [('', 0, start, 0,[],0)]
visited = []
count = 0
while True:
    count+=1
    # print(count)
    if len(queue) == 0: break
    direction, level, start, move, bs,last = queue.pop(0)

    if start==end:
        print(direction,bs,'found')
        break
    if (level, start) in visited: continue
    visited.append((level, start))
    print(f'({direction}, {level}, cur {hex(start)}, {move}, {last})')
    struct_start = start + 8  # directions function
    original_pos = level * 4
    # print(hex(struct_start),hex(original_pos))

    for i in range(6):
        func_addr = get_qword(struct_start + i * 8)
        code = get_bytes(func_addr, 50)
        new_pos = original_pos
        add = 0
        # print(hex(func_addr))
        ### calculate step for next position
        
        try:
            if code.find(b'\x48\x05') != -1 or code.find(b'\x48\x83\xc0') != -1 or code.find(
                    b'\x48\x83\xe8') != -1 or code.find(b'\x48\x2d') != -1:
                if code.find(b'\x48\x05') != -1: ## add
                    id = code.find(b'\x48\x05')
                    add = u32(get_bytes(func_addr + id + 2, 4)) // 8
                elif code.find(b'\x48\x2d') != -1: ## sub
                    id = code.find(b'\x48\x2d')
                    add = -(u32(get_bytes(func_addr + id + 2, 4)) // 8)
                elif code.find(b'\x48\x83\xc0') != -1: #add byte
                    id = code.find(b'\x48\x83\xc0') 
                    add = u8(get_bytes(func_addr + id + 3, 1)) // 8
                elif code.find(b'\x48\x83\xe8') != -1: #sub byte
                    id = code.find(b'\x48\x83\xe8')
                    add = -(u8(get_bytes(func_addr + id + 3, 1)) // 8)
        except Exception as e:
            # black_list.append(direction)
            print(e,hex(start),direction)
            continue
        
        new_dir = direction + str(i + 1)
        new_bs = bs + [get_value(start)]
        ### optimizing and check here
        # print(can_step(start,i+1,last))
        
        if not can_step(start,i+1,last):
            continue
        ### next step (calc for next start, next pos, ...)
        new_pos += add
        if level + 1 > 12: continue # found

        if new_pos > len(G_S) - 1 or new_pos < 0: continue # can't step

        id = G_S[new_pos] - 17
        new_start = u32(get_bytes(id + 3, 4)) + id + 7
        # if new_start==0x5589e1728289:
        #     print(hex(start))
        new_last = Get_word(start)
        queue.append((new_dir, level+1, new_start, new_pos,new_bs,new_last))

Script DFS:

from pwn import *
base = idaapi.get_imagebase()
G_S = [99401, 99581, 99761, 99941, 100121, 100301, 100481, 100661, 100841, 101021, 101201, 101381, 101561, 101741, 101921, 102101, 102281, 102461, 102641, 102821, 103001, 103181, 103361, 103541, 103721, 103901, 104081, 104261, 104441, 104621, 104801, 104981, 105161, 105341, 105521, 105701, 105881, 106061, 106241, 106421, 106601, 106781, 106961, 107141, 107321, 107501, 107681, 107861, 108041, 108221, 108401, 108581, 108761, 108871, 109051, 109231, 109411, 109591, 109771, 109951, 110131, 110311, 110491, 110671, 110851, 111031, 111211, 111391, 111571, 111751, 111931, 112111, 112291, 112471, 112651, 112831, 113011, 113191, 113371, 113551, 113731, 113911]
G_S = [G_S[i]+ base for i in range(82)]
#things these function do:
#   - get next data
#   - call func_8_general
#   - allow something?
#   - set own vtable
# print(G_S)
def get_step(j_byte):
    if b'\x48\x83\xC0\x08\x48' in j_byte:
        return 1
    if b'\x48\x83\xC0\x10\x48' in j_byte:
        return 2
    if b'\x48\x83\xC0\x18\x48' in j_byte:
        return 3
    if b'\x48\x83\xC0\x20\x48' in j_byte:
        return 4
    if b'\x48\x83\xC0\x28\x48' in j_byte:
        return 5
    if b'\x48\x83\xC0\x30\x48' in j_byte:
        return 6

def Get_word(start):
    mod_addr = get_qword(start) 
    # print(hex(start))
    mod_byte = get_bytes(mod_addr,100)
    if start==0x29488 + base:# table 2 and table 1
        return True
    if start==base + 0x29430:
        return 0x100
    ins = mod_byte.index(b'\x0f\xb7\x05')
    word_idx = u32(mod_byte[ins+3:ins+7])
    word_idx = mod_addr + ins + 7 + word_idx
    word = u16(get_bytes(word_idx,2))
    return word
def can_step(start:int,step:int,last_step:int)->bool:
    # print(hex(word),hex(word_idx))
    if start==base + 0x29488 or start== 0x29430 + base:
        return True
    sw_addr = get_qword(start + 8*7)
    sw_byte = get_bytes(sw_addr,500)
    dic ={}
    for i in range(200-10):
        if sw_byte[i]==0x3d and (sw_byte[i+5:i+7]==b'\x0f\x84' or sw_byte[i+5]==0x74 or sw_byte[i+5:i+7]==b'\x0f\x85'):
            number =u32(sw_byte[i+1:i+5])
            if sw_byte[i+5:i+7]==b'\x0f\x84':
                j_addr = sw_addr+i + u32(get_bytes(sw_addr+i+7,4))+11
                j_byte = get_bytes(j_addr,14)
                dic[get_step(j_byte)] = number
            elif sw_byte[i+5]==0x74:
                j_addr = sw_addr+i + u8(get_bytes(sw_addr+i+6,1))+7
                j_byte = get_bytes(j_addr,14)
                dic[get_step(j_byte)] = number
            elif sw_byte[i+5:i+7]==b'\x0f\x85':
                j_byte = get_bytes(sw_addr+i+11,14)
                dic[get_step(j_byte)] = number
    if step not in dic.keys():
        # print(dic,start)
        return False
        # if start ==0x564BD51ECE88:
        #     print(dic,step,last_step)
        #     if step==6:
        #         exit(0)
    cur_step_word = dic[step]
    if (last_step>>8)==(cur_step_word>>8):
        return True
    return False

def get_value(start):
    if start == 0x29488+base: #table 1
        return 0x5b
    if start == 0x29430 + base: #table 2
        return 0xA3
    mod_addr = get_qword(start)
    mod_byte = get_bytes(mod_addr,100)
    ins = mod_byte.index(b'\x8b\x05')
    dword_idx = u32(mod_byte[ins+2:ins+6])
    dword_idx = mod_addr + ins + 6 + dword_idx
    b = u32(get_bytes(dword_idx,4))
    return b

start = 0x29488 + base
end = 0x27ac0 + base

stack = [('', 0, start, 0,[],0)]

visited = []
count = 0
while True:
    count+=1
    # print(count)
    if len(stack) == 0: break
    direction, level, start, move, bs,last = stack.pop()

    if start==end:
        print(direction,bs,'found')
        # print(stack)
        break
    if (level, start) in visited: continue
    visited.append((level, start))
    print(f'({direction}, {level}, cur {hex(start)}, {move}, {last})')
    struct_start = start + 8  # directions function
    original_pos = level * 4
    # print(hex(struct_start),hex(original_pos))

    for i in range(6):
        func_addr = get_qword(struct_start + i * 8)
        code = get_bytes(func_addr, 50)
        new_pos = original_pos
        add = 0
        # print(hex(func_addr))
        ### calculate step for next position
        
        try:
            if code.find(b'\x48\x05') != -1 or code.find(b'\x48\x83\xc0') != -1 or code.find(
                    b'\x48\x83\xe8') != -1 or code.find(b'\x48\x2d') != -1:
                if code.find(b'\x48\x05') != -1: ## add
                    id = code.find(b'\x48\x05')
                    add = u32(get_bytes(func_addr + id + 2, 4)) // 8
                elif code.find(b'\x48\x2d') != -1: ## sub
                    id = code.find(b'\x48\x2d')
                    add = -(u32(get_bytes(func_addr + id + 2, 4)) // 8)
                elif code.find(b'\x48\x83\xc0') != -1: #add byte
                    id = code.find(b'\x48\x83\xc0') 
                    add = u8(get_bytes(func_addr + id + 3, 1)) // 8
                elif code.find(b'\x48\x83\xe8') != -1: #sub byte
                    id = code.find(b'\x48\x83\xe8')
                    add = -(u8(get_bytes(func_addr + id + 3, 1)) // 8)
        except Exception as e:
            # black_list.append(direction)
            print(e,hex(start),direction)
            continue
        
        new_dir = direction + str(i + 1)
        new_bs = bs + [get_value(start)]
        ### optimizing and check here
        # print(can_step(start,i+1,last))
        
        if not can_step(start,i+1,last):
            continue
        ### next step (calc for next start, next pos, ...)
        new_pos += add
        if level + 1 > 12: continue # found

        if new_pos > len(G_S) - 1 or new_pos < 0: continue # can't step

        id = G_S[new_pos] - 17
        new_start = u32(get_bytes(id + 3, 4)) + id + 7
        # if new_start==0x5589e1728289:
        #     print(hex(start))
        new_last = Get_word(start)
        stack.append((new_dir, level+1, new_start, new_pos,new_bs,new_last))