# hxp

## BkP CTF 2017: crypto350 "minesweeper" writeup

This challenge required us to design a quantum circuit which detects on a two-qubit system whether a measurement is taking place or not, while making sure a certain state never gets measured. As per the challenge description, this can be used to detect an eavesdropper without them noticing.

The challenge server largely consists of implementing all the usual operations on a two-qubit system; those are:

• the identity,
• (controlled) Pauli’s X-, Y-, and Z-gate,
• (controlled) arbitrary phase rotation,
• and measurement.

In the beginning, the server sets up an array of 0x70 bools, which are supposed to describe bombs on a field. (Hence the name minesweeper.) Those only difference those “bombs” make is that we are given access to an operator that performs a measurement if there is a bomb, and does nothing if there isn’t. We are then allowed to execute a sequence of almost arbitrary circuits, with the only restriction that we must never measure a $1$ on any of the two qubits. After each circuit sent to the server, we are given a measurement of the final state (which may contain $1$s). In the end, it doesn’t even matter we have to send the exact indices with bombs to the server to get the flag.

The way we solved this is based on the observation that measurement performs a “projection” on the state matrix, in the sense that with high probability, a state with very low probability has probability zero afterwards, and its weight gets reallocated to the most probable state. For example, if a 1-qubit system is in the state $\sqrt{1-\varepsilon}\cdot\lvert0\rangle+\sqrt\varepsilon\cdot\lvert1\rangle$ with $\varepsilon$ very small, it will most likely be in the pure state $\lvert0\rangle$ afterwards.

Since the four basis states are assigned numbers in the source code, we fix the following mapping:

• state 0 is $\lvert00\rangle$;
• state 1 is $\lvert10\rangle$;
• state 2 is $\lvert01\rangle$;
• state 3 is $\lvert11\rangle$.

Let $\mathcal O$ be the operator that is either a measurement of the second qubit (if “there is a bomb”), or the identity (if there isn’t).

One of the core ingredients to our solution is the phase rotation gate $R_\varphi$: We use this to repeatedly introduce a small distortion into the state and apply the “oracle” operator $\mathcal O$ afterwards. Then either the small error is removed by the measurement (or, with very small probability, the whole thing blows up), or it accumulates to a large distortion over the rounds.

The basic primitive we use is the following operator: $\Gamma:=\mathcal O\cdot H\cdot R_\varphi\cdot H$ for a very small angle $\varphi$, such as $0.001$ radians.

Let’s trace the effect of this operator on a state ($\lvert10\rangle$ and $\lvert11\rangle$ are irrelevant for our purposes): \begin{align*} &\alpha\cdot\lvert00\rangle + \beta\cdot\lvert01\rangle \\ \overset H\longmapsto\qquad &\frac{\alpha+\beta}{\sqrt2}\cdot\lvert00\rangle + \frac{\alpha-\beta}{\sqrt2}\cdot\lvert01\rangle \\ \overset{R_\varphi}\longmapsto\qquad &\frac{\alpha+\beta}{\sqrt2}\cdot\lvert00\rangle + \frac{\alpha-\beta}{\sqrt2}e^{i\varphi}\cdot\lvert01\rangle \\ \overset H\longmapsto\qquad &\frac{(1+e^{i\varphi})\alpha+(1-e^{i\varphi})\beta}2\cdot\lvert00\rangle+\frac{(1-e^{i\varphi})\alpha+(1+e^{i\varphi})\beta}2\cdot\lvert01\rangle \\ \overset{\mathcal O}\longmapsto\qquad &\begin{cases} \gamma\cdot\lvert00\rangle & \text{if bomb, with overwhelming probability} \\\delta\cdot\lvert01\rangle & \text{if bomb, with negligible probability} \\\frac{(1+e^{i\varphi})\alpha+(1-e^{i\varphi})\beta}2\cdot\lvert00\rangle+\frac{(1-e^{i\varphi})\alpha+(1+e^{i\varphi})\beta}2\cdot\lvert01\rangle & \text{if no bomb} \text, \end{cases} \end{align*} where $\gamma$ and $\delta$ are complex numbers of norm $1$.

This means:

• If there is a bomb, and if we start in the pure state $\lvert00\rangle$, it is almost certain that we’re still in (a phase-shifted version of) that state after iterating $\Gamma$ a few times. (At some point, it becomes too likely that we hit the second case and we’re dead, but in practice one can balance the reliability and the danger of explosion well enough.)
• If there is no bomb, we see the system (slowly) converge to $\lvert01\rangle$ with repeated applications of $\Gamma$. Note we do not care about the probability of hitting $\lvert01\rangle$ here since $\mathcal O$ does not perform a measurement, and the final measurement does not blow up if it hits $\lvert01\rangle$.

This means we can distinguish the two possible cases by repeatedly applying $\Gamma$ to the initial state $\lvert00\rangle$ and checking (via the final measurement given to us by the server) whether we are definitely in the “no bomb” case (if we get $\lvert01\rangle$), or perhaps in the “bomb” case (if we get $\lvert00\rangle$). Since the latter case has some probability of error, we then iterate the same check a few more times. If we always get $\lvert00\rangle$, we’re most likely in the “bomb” case. Of course, if we happen to measure $\lvert01\rangle$ when applying $\mathcal O$, we are dead and have to start over, but by tweaking the angle $\varphi$ and the iteration counts, we could reduce that probability such that the solver works something like $60\%$ of the time in practice. (And yes, I did run it 100 times to get that number!)

Here is the solver script:

#!/usr/bin/env python3
import socket, struct

host, port = '54.202.194.91', 65535

G_H = 4 # Hadamard gate
G_P = 6 # Rotate phase by an angle specified in radians

def measure_or_not(num, wire):
assert num < 0x70
return bytes([num | wire * 0x80])

def gate(kind, wire, ctrl, param = None):
b = 0x70 | 0x80 * wire | 0x08 * ctrl | kind
return bytes([b]) if param is None else struct.pack('<Bd', b, param)

its, phi = 1000, .001
def detect(num, sock):
gates = []
for _ in range(its):
gates.append(gate(G_H, 1, 0))
gates.append(gate(G_P, 1, 0, phi))
gates.append(gate(G_H, 1, 0))
gates.append(measure_or_not(num, 1))
sock.sendall(struct.pack('!H', len(gates)) + b''.join(gates))
return sock.recv(1)[0] # measure_final

sock = socket.socket()
sock.connect((host, port))

reps = 50
is_bomb = [False] * 0x70
for field in range(112):
for cur_rep in range(reps):
if detect(field, sock):
print('{:3d} is clear'.format(field))
break
else:
print('{:3d} is bomb'.format(field))
is_bomb[field] = True

sock.send(b'\0\0') # no more queries

packed = sum(b << i for i, b in enumerate(reversed(is_bomb)))
packed = int.to_bytes(packed, 14, 'big')
print('bombs @ {}'.format(packed))
sock.sendall(packed)
sock.shutdown(socket.SHUT_WR)

print('--> {}'.format(sock.recv(0x100).decode().strip()))


Note the constants phi, its and reps were initially chosen pretty arbitrarily and tweaked whenever the probability of error or explosion turned out too large. I’m confident one could obtain much better results using controlled quantum gates (NB: we only used one of the qubits!) and by computing/minimizing the failure probabilities, but the above is simple and worked well enough to get the flag:

\$ ./pwn.py
0 is clear
1 is clear
2 is bomb
3 is clear
4 is clear
5 is clear
6 is clear
7 is bomb
8 is clear
9 is bomb
10 is bomb
11 is bomb
12 is bomb
13 is clear
14 is bomb
15 is clear
16 is clear
17 is bomb
18 is bomb
19 is clear
20 is clear
21 is clear
22 is bomb
23 is bomb
24 is bomb
25 is clear
26 is clear
27 is clear
28 is bomb
29 is bomb
30 is clear
31 is bomb
32 is clear
33 is bomb
34 is bomb
35 is bomb
36 is bomb
37 is bomb
38 is clear
39 is clear
40 is bomb
41 is bomb
42 is bomb
43 is clear
44 is bomb
45 is clear
46 is clear
47 is bomb
48 is bomb
49 is bomb
50 is clear
51 is bomb
52 is bomb
53 is clear
54 is bomb
55 is clear
56 is bomb
57 is bomb
58 is clear
59 is bomb
60 is bomb
61 is bomb
62 is bomb
63 is bomb
64 is bomb
65 is bomb
66 is bomb
67 is bomb
68 is clear
69 is bomb
70 is clear
71 is bomb
72 is bomb
73 is bomb
74 is clear
75 is clear
76 is bomb
77 is clear
78 is clear
79 is clear
80 is bomb
81 is clear
82 is clear
83 is bomb
84 is clear
85 is bomb
86 is bomb
87 is clear
88 is bomb
89 is clear
90 is clear
91 is bomb
92 is bomb
93 is clear
94 is bomb
95 is bomb
96 is clear
97 is bomb
98 is bomb
99 is clear
100 is bomb
101 is bomb
102 is clear
103 is bomb
104 is bomb
105 is clear
106 is clear
107 is clear
108 is clear
109 is clear
110 is bomb
111 is bomb
bombs @ b'!zc\x8d|\xe9\xda\xdf\xf5\xc8\x96\x9bm\x83'
--> FLAG{Maybe they exploded in parallel universes}