feyor.sh

Schrödinger's Cat

Schrödinger’s Cat was a quantum computing misc challenge repurposed written for UIUCTF 2023. The challenge had unrated difficulty and had 17 solves during the competition.

Description

Our boss got mad that our SSH keys were weak, so now we’re using a quantum computer to be extra secure!

Hints

Files

Solution

Code

import numpy as np
from base64 import b64encode
from qiskit import *
from qiskit.circuit.library import StatePreparation
from qiskit.compiler import transpile
import qiskit.quantum_info as qi

WIRES = 5

# helper functions from challenge
def normalization(msg):
    assert(len(msg) <= WIRES**2)
    state = np.array([ord(c) for c in msg.ljust(2**WIRES, ' ')])
    norm = np.linalg.norm(state)
    state = state / norm
    return (state, norm)

def transform(sv, n):
    legal = lambda c: ord(' ') <= c and c <= ord('~')
    renormalized = [float(i.real)*n for i in sv]
    rn_rounded = [round(i) for i in renormalized]
    if not np.allclose(renormalized, rn_rounded, rtol=0, atol=1e-2):
        print("Your rehydrated statevector isn't very precise. Try adding at least 6 decimal places of precision, or contact the challenge author if you think this is a mistake.")
        print(rn_rounded)
        exit(0)
    if np.any([not legal(c) for c in rn_rounded]):
        print("Invalid ASCII characters.")
        exit(0)
    return ''.join([chr(n) for n in rn_rounded])


def solve_qiskit():
    echo_sv, _ = normalization("echo 'Hello, world!'")
    cat_sv, cat_n = normalization("cat /flag.txt")

    circ = QuantumCircuit(WIRES)
    circ.append(StatePreparation(cat_sv, label="sp"), range(WIRES))
    circ.append(StatePreparation(echo_sv, label="inv_sp", inverse=True), range(WIRES))

    # append the original StatePreparation to confirm that this works; remove for payload
    #circ.append(StatePreparation(echo_sv), range(WIRES))
    circ = transpile(circ, backend=Aer.get_backend("aer_simulator"), optimization_level=3)
    sv = qi.Statevector.from_instruction(circ)

    return b64encode(circ.qasm().encode()), cat_n

if __name__ == "__main__":
    print(solve_qiskit())

Explanation

We connect to the challenge server and are greeted with the following:

print("Welcome to the Quantum Secure Shell. Instead of dealing with pesky encryption, just embed your commands into our quantum computer! I batched the next command in with yours, hope you're ok with that!")

given_sv, given_n = normalization("echo 'Hello, world!'")
print_given(given_sv, given_n)
print("\nPlease type your OpenQASM circuit as a base64 encoded string: ")
Welcome to the Quantum Secure Shell. Instead of dealing with pesky encryption, just embed your commands into our quantum computer! I batched the next command in with yours, hope you're ok with that!
     ┌─────────────────┐┌───────────────────────┐
q_0: ┤0                ├┤0                      ├
     │                 ││                       │
q_1: ┤1                ├┤1                      ├
     │                 ││                       │
q_2: ┤2 Your Circ Here ├┤2 echo 'Hello, world!' ├
     │                 ││                       │
q_3: ┤3                ├┤3                      ├
     │                 ││                       │
q_4: ┤4                ├┤4                      ├
     └─────────────────┘└───────────────────────┘
Normalization constant: 419.1873089681986

Executing...

Hello, world!

Please type your OpenQASM circuit as a base64 encoded string:

Taking a look at the source, we see that we input some quantum circuit which is inserted before a different circuit, and the resultant statevector is then “unnormalized”, interpreted as a string, and fed to os.system.

Our end goal should be to embed a string like ls or cat flag.txt; this is trivial with the normalization function provided.

cat_sv, cat_n = normalization("cat /flag.txt")
cat_circ = StatePreparation(cat_sv, label="state_prep")

What is the normalization constant?

The “measurement rule” in quantum mechanics dictates that the sum of all amplitudes squared must equal 1. In order to encode a vector of ASCII values in the circut, we first need to normalize it; to get back to the original vector, we “undo” the normalization by multiplying the scalar normalization constant.

Good news is, we didn’t receive any mod mail on the normalization constant so… hopefully no one had any issues?

Where’s the measurement?

You might be wondering how one might fit a 32 character string into 5 qubits, and more importantly; where are the measurement gates? The output of the circuit is the statevector, which means if you were to measure the qubits instead, the probability of measuring a specific outcome would correspond to amplitudes in the statevector. Using the statevector, we’re able to losslessly finangle lots of data into the rotation of a qubit that would otherwise be lost through measurement.

About StatePreparation

The existing circuit embeddeds the string echo 'Hello, world!' using Qiskit’s StatePreparation function. This is a form of amplitude encoding, a way to encode information in the probability amplitudes of discrete quantum states. A common point of confusion was that StatePreparation returns a statevector; it’s actually an algorithm for creating a circuit that will transform | 0 into a desired statevector.

circ = StatePreparation(given_sv)
print(qi.Statevector.from_instruction(circ) == qi.Statevector(given_sv))
True

Hope you didn’t sleep through linalg (I did)

The next part is to figure out how to “get rid of” the circuit applied after your input, which encodes the string echo 'Hello, world!'. Quantum circuits are all really just unitary matrices, which means they’re invertible.

So if we have input I , echo input E , and desired payload in I E = P , that means I = ( P E ) .

In order to calculate E , we need to grab E :

echo_sv, _ = normalization("echo 'Hello, world!'")
E = StatePreparation(echo_sv, label="echo")

And then take its inverse:

E_inv = E.inverse()

Finally, we compose the individual circuits together:

circ = QuantumCircuit(WIRES)
circ.append(cat_circ, range(WIRES))
circ.append(E_inv, range(WIRES))

circ.draw('mpl', filename="schroedingers_cat/circuit.png")

Gross (and also kinda wrong). Qiskit’s QASM converter will happily spit out black boxes like above, assuming whoever will consume the QASM will know what that means.

An aside on OpenQASM

If we try to convert our circuit as is to QASM, we run into some issues:

OPENQASM 2.0;
include "qelib1.inc";
gate multiplex1_reverse_dg q0 { ry(0.6960408807071358) q0; }
gate multiplex1_reverse_dg_5200741712 q0 { ry(1.5295115311526133) q0; }
gate multiplex1_reverse_reverse_dg q0 { ry(-0.04128479564228338) q0; }
gate multiplex2_reverse_dg q0,q1 { multiplex1_reverse_dg_5200741712 q0; cx q1,q0; multiplex1_reverse_reverse_dg q0; cx q1,q0; }
gate multiplex1_reverse_dg_5193281552 q0 { ry(1.4620958103644106) q0; }
gate multiplex1_reverse_reverse_dg_5201292752 q0 { ry(0.10867083226993679) q0; }
gate multiplex2_reverse_dg_5193285584 q0,q1 { multiplex1_reverse_dg_5193281552 q0; cx q1,q0; multiplex1_reverse_reverse_dg_5201292752 q0; }
gate multiplex1_reverse_reverse_reverse_dg q0 { ry(0.10867083226993673) q0; }

In order to emit QASM that Qiskit will actually understand, we need to transpile our circuit to a set of universal basis gates. This is also how quantum circuits are run on hardware, as each computer only understands a certain set of basis gates.

from qiskit import Aer
from qiskit.compiler import transpile
circ_transpiled = transpile(circ, backend=Aer.get_backend("aer_simulator"), optimization_level=3)
good_qasm = circ_transpiled.qasm()
print('\n'.join(good_qasm.split('\n')[:10]))
OPENQASM 2.0;
include "qelib1.inc";
qreg q[5];
u3(1.4344105714005226,0,0) q[0];
u3(1.5262619493655363,0,0) q[1];
u3(1.4620958103644108,0,0) q[2];
u3(1.5295115311526135,0,0) q[3];
u3(0.6960408807071358,0,0) q[4];
cx q[4],q[3];
u3(0.04128479564228338,-pi,-pi) q[3];

A little tangent on OpenQASM: the implementation is so scuffed and incomplete to the point it makes Yandere Simulator look like enterprise software. I had poked around trying to develop a challenge focused on OpenQASM, but found that literally every interesting part of the spec was unimplemented 😢

Here’s Qiskit’s implementation of OpenQASM3’s include statement:

def visit_Include(self, node: ast.Include, context: State) -> State:
		if node.filename != "stdgates.inc":
				raise_from_node(node, "non-stdgates imports not currently supported")
		for name, (builder, n_arguments, n_qubits) in _STDGATES.items():
				context = self._define_gate(name, builder, n_arguments, n_qubits, node, context)
		return context

I understand that this is alpha software for a rather small part of Qiskit, and I’m not trying to pile on the Qiskit devs for not lavishing more attention on this, but… bruh.

Finishing up

All that’s left is to b64encode this bad boy and ship it off to remote.

payload = b64encode(good_qasm.encode())
# server side
transform(qi.Statevector.from_instruction(make_circ(given_sv, QuantumCircuit.from_qasm_str(b64decode(payload).decode()))), cat_n)
cat /flag.txt

Retrospection

When the challenge was first released (on the second day of the CTF), I decided to not release the source. Although that was intended to prevent code reuse from server.py, it made the challenge waaaay too guessy. Not only that, but it was probably better to provide primitives so you could focus on solving the challenge instead of placating Qiskit’s fussiness.

This very much locks you into using Qiskit and — according to some modmail I received — a particular way of solving the challenge. Even though the server was built against the latest version of Qiskit (and thus the version people would get from pip install -r requirements.txt), in the future I would release the server Dockerfile to remove any source of impurity. (This is somewhat ironic, given that the challenge author uses NixOS.)