writeups/fkehrer/ctfzone19/solve.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 # search recursively for solutions
  41 def recursive_search(currentBoard, moves, maxindex):
  42     for i in range(maxindex):
  43         board = xorboard(currentBoard, moves[i][0])
  44         if winningboard(board):
  45             return [i]
  46         result = recursive_search(board, moves, i)
  47         if result != None:
  48             return result + [i]
  49     return None
  50
  51
  52 fridge = pwnlib.tubes.remote.remote("ppc-fridge.ctfz.one", 31337)
  53
  54 # do all this once per stage
  55 for stage in range(len(dimensions)):
  56     dim = dimensions[stage]
  57     moves= []
  58     before = readboard(fridge, dim)
  59     # does all possible moves once, records the changes they make
  60     for x in range(dim):
  61         for y in range(dim):
  62             move_str = "{0},{1}".format(x,y)
  63             fridge.sendline(move_str)
  64             after = readboard(fridge, dim)
  65             moves.append((xorboard(before, after),move_str,))
  66             before = after
  67     # from the current board, find a solution
  68     moves_list = recursive_search(before, moves, len(moves))
  69     if moves_list == None:
  70         print("ERROR: No moves found")
  71         quit()
  72     print("BEFORE: ",before)
  73     # apply moves, skipping the last one because it doesn't print a board
  74     for i in moves_list[:-1]:
  75         print(moves[i][1])
  76         fridge.sendline(moves[i][1])
  77         print(readboard(fridge, dim))
  78     # handle last move
  79     print(moves[-1][1])
  80     fridge.sendline(moves[-1][1])
  81     print(fridge.recvline())    # this one is solved
  82
  83 fridge.interactive()