BKP CTF 2017 Minesweeper Solution

solve_minesweeper.py

#!/usr/bin/env python2
import math

from pwn import *

"""
Read this: https://inst.eecs.berkeley.edu/~cs191/fa07/lectures/lecture22_fa07.pdf

I don't really know much about quantum computers.
Credit goes to [bobert](https://github.com/rstrand2357) for figuring out how to solve this.
I took a page of notes during a phone call with him.
I bit twiddle much better than he does.

I also put some fmt.Println debug statements in the provided go code

The challenge creates a list of possible bombs. You have to tell the program
which bombs will explode and which won't, but if you actively observe an 
active bomb, it'll explode. 

Apparently there is some quantum magic where if you have a chain of
Hadamard - phase shift - Hadamard - possible bomb[n]
blocks, you can figure out if they are active bombs or not if you
do enough of these with a small enough phase shift each time.

We do a total of 2000 (bignum) sets of those four blocks.
Each phase shift is pi/bignum radians

So, for each bomb n:
send (2000*4) for the number of gates
send a Hadamard gate
send a phase shift by pi/2000
send a Hadamard gate
send the index of the possible bomb n
get the return value (0:safe, 1:bomb)

Repeat for all 112 bombs

Send back the list of bombs / not-bombs
"""


context.endian = "big"
context.log_level = "INFO"

# How many Hadamard-phase-Hadamard-bomb blocks
bignum = 2000

# Gate types numbers are 0x70 + the gate index
hadamard = p8(0x70 + 4)
# Phase rotation is a 64-bit float
phase_rot = p8(0x70 + 6) + struct.pack("<d", math.pi/bignum)


# r = remote("54.202.194.91", 65535)
r = remote("127.0.0.1", 8001)

bombs = []
# for bomb in range(1):  # testing
for bomb in range(14*8):
    log.warning("bomb %d"%bomb)
    # num gates
    r.send(p16(bignum*4))

    for p_b in range(bignum):
        # log.info("block %d"%p_b)
        r.send(hadamard)
        r.send(phase_rot)
        r.send(hadamard)
        r.send(p8(bomb))
    measure_final = r.recv(1)
    # Add the bomb/not-bomb indicator to the list
    bombs += [0 if u8(measure_final) else 1]
    log.warning(hex(u8(measure_final)))

# 0 gates to stop getting gates
r.send(p16(0))

print bombs


def getbytes(bits):
    """Yield bytes from a list of bits

    This will sometimes? give more bytes than needed.

    I found this somewhere on stack overflow
    """
    bits = iter(bits)
    done = False
    while not done:
        byte = 0
        for _ in range(0, 8):
            try:
                bit = next(bits)
            except StopIteration:
                bit = 0
                done = True
            byte = (byte << 1) | bit
        yield byte


log.info("".join("o" if x else "X" for x in bombs))

# Up the log_level because I don't want to miss the flag
context.log_level = "DEBUG"

# Pack the bytes for the bombs and send
# Limit to 14 because the getbytes was doing something screwy
for b in list(getbytes(bombs))[:14]:
    log.info("sending %d"%b)
    r.send(p8(b))

log.info("Getting flag")
while True:
    print r.recv(1)



# FLAG{Maybe they exploded in parallel universes}\n