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()