Đâ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/
```python
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:
```python
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).
```python
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.
```python
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.
```python
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:
```python
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:
```python
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
```
```python
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.
```python!
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:
```python
# 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:
```python
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:
```python
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))
```
Sign in with Wallet
Connect another wallet