UTCTF 2021 - Wiesner's Quantum Bank

We’re Wiesner’s Quantum Bank, the biggest name in quantum money storage. Check out our new remote service:

1nc crypto.utctf.live 1234

First Steps

No source provided :( Let’s connect through netcat then:

 1<== Welcome to Wiesner's Quantum Bank! ==>
 2
 3Due to totally legitimate reasons, we only have one Schroedinger Buck (SB) in the whole bank. Good thing nobody can copy it!
 4
 5Each member of Wiesner's Quantum Bank also gets a free qubit with which they can do whatever they want. Surely this will not come back to bite us!
 6
 7What would you like to do today?
 8
 9    a) Work with a qubit from the Schroedinger Buck
10    b) Submit a valid Schroedinger Buck in exchange for a flag (why do we sell flags???)
11    c) Quit
12
13Choice [a|b|c]:

Alright, they’re talking about quantum money, and we can work with qubits. Let’s find out what we can do:

 1Which qubit of the Schroedinger Buck would you like to work with? Enter a number between 0-29 (inclusive):
 20
 3What operation would you like to perform?
 4
 5    a) Apply X gate to my qubit
 6    b) Apply Y gate to my qubit
 7    c) Apply Z gate to my qubit
 8    d) Apply H (Hadamard) gate to my qubit
 9    e) Apply Rotation gate to my qubit
10    f) Apply CNOT gate to my qubit and the SB qubit
11    g) Apply CNOT-X gate to my qubit and the SB qubit
12    h) Have the SB qubit verified (bank measures)
13    i) Measure the SB qubit in the [0,1] basis
14    j) Measure the SB qubit in the [+,-] basis
15    k) Measure the control qubit (takes you to main menu after)
16    l) Go back to the main menu (resets your qubit)
17
18Choice [a|b|c|d|e|f|g|h|i|j|k|l]:

Okay, that’s a lot of operations. At this point I realized that I could not get through the challenge with zero knowledge of quantum mechanics, so I had to brush up on some reading.

The Basics

As mentioned before, this challenge is about a quantum money scheme, where each (well, the only) bill is a quantum state made up for 30 qubits. You might be wondering: what are qubits?

Disclaimer: this is not a complete or detailed explanation, it’s just enough to understand the challenge.

Qubits are quantum bits. A normal bit contains the value 0 or 1, simple as that. But a qubit is a superposition of both states, which are designated $|0 \rangle$ and $|1 \rangle$. However, this does not mean that a qubit contains a value between 0 and 1. It simply means that, when measured, the qubit will show 0 or 1 with some probability dependent on its quantum state.

$|0 \rangle$ and $|1 \rangle$ also have vector representations $\begin{bmatrix}1 \ 0\end{bmatrix}$and $\begin{bmatrix}0 \ 1\end{bmatrix}$ respectively. Linear algebra enthusiasts might note that this means they form an orthogonal basis - indeed, $[0, 1]$ is called the computational basis of qubits.

A general qubit could then be expressed as $\alpha|0\rangle + \beta |1\rangle$, where $\alpha$ and $\beta$ are real numbers. When measured in the computational basis, this qubit has probability $|\alpha|^2$ to show $|0 \rangle$ and $|\beta|^2$ to show $|1 \rangle$. (Just take my word for this one.) (Quick check: the qubits $|0 \rangle$ and $|1 \rangle$ indeed have 100% chance to measure as $|0 \rangle$ and $|1 \rangle$ respectively.)

But you could also measure the qubit in any other orthogonal basis, which would not show $|0 \rangle$ and $|1 \rangle$ but the vectors in that basis instead. For example, if we define $|+ \rangle = \frac{1}{\sqrt{2}}|0 \rangle + \frac{1}{\sqrt{2}}|1 \rangle$ and $|- \rangle = \frac{1}{\sqrt{2}}|0 \rangle - \frac{1}{\sqrt{2}}|1 \rangle$, $[+, -]$ form another orthogonal basis, and if we measure any qubit $\alpha|0\rangle + \beta |1\rangle$ in this basis we would have different probabilities to show either $|+ \rangle$ or $|- \rangle$ (which I can’t be bothered to write out).

The Problem

On to the challenge: we wish to forge our own valid Schrodinger Buck by measuring each qubit using the operations given to us. As shown by the title, the challenge is using Wiesner’s quantum money scheme. This means that each qubit has 4 possible values: $|0 \rangle$, $|1 \rangle$, and also two other states denoted as $|+ \rangle$ and $|- \rangle$. $|+ \rangle = \frac{1}{\sqrt{2}}|0 \rangle + \frac{1}{\sqrt{2}}|1 \rangle$ and $|- \rangle = \frac{1}{\sqrt{2}}|0 \rangle - \frac{1}{\sqrt{2}}|1 \rangle$. We already know that the $|0 \rangle$ and $|1 \rangle$ states always measure as 0 and 1, but these new states, $|+ \rangle$ and $|- \rangle$, both have a $\frac{1}{2}$ chance of measuring as either $|0 \rangle$ or $|1 \rangle$, since $|\alpha|^2 = |\beta|^2 =\frac{1}{2}$.

You may be wondering at this point: why don’t we just measure each qubit? After all, the bank gives you the option to measure in both bases!* Well, there are two problems with this.

1. When you measure a qubit, it takes on the value it shows. So if you measure $|+ \rangle$ in the $[0, 1]$ basis, it will become either $|0 \rangle$ or $|1 \rangle$, and you won’t be able to tell what it originally was.
2. Even if you were able to measure each qubit multiple times, there is an even $\frac{1}{2}$ chance that it would measure as either $|0 \rangle$ or $|1 \rangle$, so you still wouldn’t be able to tell what it was.

*Okay, it turns this was possible in the challenge, but it was an unintended bug. And way less cool than the actual solution.

The Solution

Doing a bit of research, I came across a paper that described a few ways to attack this specific quantum money scheme. One of them was named the “bomb-testing” attack, and it caught my notice especially because it used a “probe” qubit, which seemed to line up exactly with the “free qubit” the bank gave us for no apparent reason. I won’t go into the full details of the attack, but you can read the paper if you wish to know more. Essentially, the attack works like this:

1. We apply controlled not gates (CNOT, CNOT-X) to the free qubit and the SB qubit, which produce different results depending on the state of the SB qubit. A useful fact that enables this to work well is the fact that $|+ \rangle$ and $|- \rangle$ both stay invariant (don’t change) under a CNOT gate.
2. One pass will allow us to determine if the SB qubit is $|+ \rangle$ or not. A second pass will allow us to determine if the SB qubit is $|- \rangle$ or not. If it is neither, then we have eliminated the probabilistic possibilities of the qubit, and we can just straight up measure it in the computational basis $[0, 1]$ to get the 100% correct value.

We can repeat this attack 30 times, once for each qubit, to get all 30 qubits and successfully forge our bill.

Here is the script I wrote for this:

  1from pwn import *
  2import math
  3
  4sh = remote('crypto.utctf.live', 1234)
  5
  6rounds = 100
  7sigma = math.pi / (2 * rounds)
  8
  9sb = ''
 10
 11for i in range(30):
 12	print(i)
 13	sh.recvuntil('Choice [a|b|c]:')
 14	sh.recvline()
 15	sh.sendline('a'.encode())
 16	sh.recvline()
 17	sh.recvline()
 18	sh.sendline(str(i).encode())
 19	#test for +
 20	print('+ pass')
 21	for a in range(16):
 22		sh.recvline()
 23	for _ in range(rounds):
 24		sh.sendline('e'.encode())
 25		#print('end e')
 26		#print(sh.recvline())
 27		#print(sh.recvline())
 28		sh.sendline(str(sigma).encode())
 29		#print('send sigma')
 30		for b in range(4):
 31			sh.recvline()
 32		sh.sendline('f'.encode())
 33		for b in range(4):
 34			sh.recvline()
 35		sh.sendline('h'.encode())
 36		for b in range(4):
 37			sh.recvline()
 38	sh.sendline('k'.encode())
 39	sh.recvuntil('\nYour qubit measured as a ')
 40	mq = int(sh.recvline().decode()[0])
 41	print('my qubit', mq)
 42	if mq == 1:
 43		sb += '+'
 44		continue
 45
 46	#test for -
 47	print('- pass')
 48	sh.recvuntil('Choice [a|b|c]:')
 49	sh.recvline()
 50	sh.sendline('a'.encode())
 51	sh.recvuntil('(inclusive):')
 52	sh.recvline()
 53	sh.sendline(str(i).encode())
 54	sh.recvuntil('[a|b|c|d|e|f|g|h|i|j|k|l]:')
 55	sh.recvline()
 56	for _ in range(rounds):
 57		sh.sendline('e'.encode())
 58		#print('end e')
 59		#print(sh.recvline())
 60		#print(sh.recvline())
 61		sh.sendline(str(sigma).encode())
 62		#print('send sigma')
 63		for b in range(4):
 64			sh.recvline()
 65		sh.sendline('g'.encode())
 66		for b in range(4):
 67			sh.recvline()
 68		sh.sendline('h'.encode())
 69		for b in range(4):
 70			sh.recvline()
 71	sh.recvuntil('[a|b|c|d|e|f|g|h|i|j|k|l]:')
 72	sh.recvline()
 73	sh.sendline('k'.encode())
 74	sh.recvuntil('Your qubit measured as a ')
 75	mq = int(sh.recvline().decode()[0])
 76	if mq == 1:
 77		sb += '-'
 78		continue
 79
 80	#0, 1 pass
 81	print('01 pass')
 82	sh.recvuntil('Choice [a|b|c]:')
 83	sh.recvline()
 84	sh.sendline('a'.encode())
 85	sh.recvuntil('(inclusive):')
 86	sh.recvline()
 87	sh.sendline(str(i).encode())
 88	sh.recvuntil('[a|b|c|d|e|f|g|h|i|j|k|l]:')
 89	sh.recvline()
 90	#measure in [0, 1]
 91	sh.sendline('i'.encode())
 92	sh.recvuntil('The SB qubit measured as a ')
 93	cq = sh.recvline().decode()[0]
 94	sb += cq
 95
 96sh.recvuntil('Choice [a|b|c]:')
 97sh.recvline()
 98sh.sendline('b'.encode())
 99sh.recvuntil('long:')
100sh.recvline()
101sh.sendline(sb.encode())
102sh.interactive()

~Quintec