]> git.somenet.org - pub/jan/ctf-seminar.git/blob - writeups/fkehrer/ctfzone19/solve_bfs.py
Add writeup for hxp 36C3 CTF
[pub/jan/ctf-seminar.git] / writeups / fkehrer / ctfzone19 / solve_bfs.py
1 import pwnlib
2
3 dimensions = [4,4,10]
4
5 ZERO = False
6 ONE = True
7
8 # check if board is all 0s
9 def winningboard(board):
10     for elem in board:
11         if elem == ONE:
12             return False
13     return True
14
15 # xors two boards, result is a new board (originals unchanged)
16 def xorboard(boardA, boardB):
17     newBoard = []
18     for i in range(len(boardA)):
19         newBoard.append(boardA[i] != boardB[i])
20     return newBoard
21
22 # read a board from pipe, return representation with True/False
23 def readboard(pipe, dimension):
24     move = []
25     for _ in range(dimension):
26         line = pipe.recvline()
27         #print(line)
28         for field in line.split(b" "):
29             if field == b"0" or field == b"0\n":
30                 move.append(ZERO)
31             elif field == b"1" or field == b"1\n":
32                 move.append(ONE)
33             else:
34                 print("assumption fail: ")
35                 print(line)
36                 print(field)
37                 quit()
38     return move
39         
40 def bfs(currentBoard, moves, maxindex, depth):
41     for i in range(maxindex):
42         board = xorboard(currentBoard, moves[i][0])
43         if depth == 1:
44             if winningboard(board):
45                 return [i]
46         else:
47             result = bfs(xorboard(currentBoard, moves[i][0]), moves, i, depth - 1)
48             if result != None:
49                 return result + [i]
50     return None
51
52
53
54 fridge = pwnlib.tubes.remote.remote("ppc-fridge.ctfz.one", 31337)
55
56 # do all this once per stage
57 for stage in range(len(dimensions)):
58     dim = dimensions[stage]
59     moves= []
60     before = readboard(fridge, dim)
61     # does all possible moves once, records the changes they make
62     for x in range(dim):
63         for y in range(dim):
64             move_str = "{0},{1}".format(x,y)
65             fridge.sendline(move_str)
66             after = readboard(fridge, dim)
67             moves.append((xorboard(before, after),move_str,))
68             before = after
69     # from the current board, find a solution
70     for depth in range(1, len(moves)):
71         print("SEARCH DEPTH: ", depth)
72         moves_list = bfs(before, moves, len(moves), depth)
73         if moves_list != None:
74             break
75     if moves_list == None:
76         print("NO MOVES FOUND")
77     print("BEFORE: ",before)
78     # apply moves, skipping the last one because it doesn't print a board
79     for i in moves_list[:-1]:
80         print(moves[i][1])
81         fridge.sendline(moves[i][1])
82         print(readboard(fridge, dim))
83     # handle last move
84     print(moves[-1][1])
85     fridge.sendline(moves[-1][1])
86     print(fridge.recvline())    # this one is solved
87
88 fridge.interactive()