quant? — UMDCTF

Description

quant? it's all math anyways. I heard predicting the future has been in vogue recently, so I hid the flag in a black-box oracle.

Connect to a "qisket" (misspelled qiskit) oracle service at nc challs.umdctf.io 30309. The service accepts OpenQASM-like circuit descriptions with:

• 16 input qubits q[0] through q[15]
• 1 ancilla qubit q[16]
• 16-bit classical register c[0] through c[15]

Supported gates: h, x, z, mcx, oracle, diffuse, measure

Limits: 250 oracle calls, 200000 bytes input, 512 shots.

Analysis

This is a classic Grover's Algorithm challenge. The service has a black-box oracle that marks exactly one 16-bit state. The goal is to find this marked state using quantum amplitude amplification.

Key Parameters

• Search space: N = 2^16 = 65536 states
• Marked states: M = 1
• Optimal iterations: k = floor(π/4 × √(N/M)) ≈ 201

The optimal number of Grover iterations can be computed precisely:

import math

def grover_iterations(n_qubits: int) -> int:
    theta = math.asin(1 / math.sqrt(1 << n_qubits))
    return max(range(250), key=lambda k: math.sin((2 * k + 1) * theta) ** 2)

# For 16 qubits: returns 200

Circuit Structure

Standard Grover's algorithm requires:

1. Initialization: Put all input qubits in superposition with Hadamard gates
2. Ancilla preparation: Prepare ancilla in |-> state for phase kickback
3. Grover iterations: Repeat (oracle + diffusion) ~200 times
4. Measurement: Measure all input qubits

Solution

#!/usr/bin/python3
import math
import os
import re
import socket
import subprocess

HOST = "challs.umdctf.io"
PORT = 30309
N = 16
CACHE = "/tmp/umdctf_pow"
TOKEN_RE = re.compile(rb"sh -s ([^\n]+)\nsolution: ")
BANNER_END = b"measure every input qubit as q[i] -> c[i]\n\n"
FLAG_RE = re.compile(r"UMDCTF\{[^\n}]*\}")

ORACLE_ARGS = ",".join(f"q[{i}]" for i in range(17))
DIFFUSE_ARGS = ",".join(f"q[{i}]" for i in range(16))


def solve_pow(token: str) -> str:
    cmd = f"curl -sSfL https://pwn.red/pow | sh -s {token}"
    out = subprocess.check_output(cmd, shell=True, env={**os.environ, "XDG_CACHE_HOME": CACHE})
    return out.decode().strip()


def grover_iterations(n_qubits: int) -> int:
    theta = math.asin(1 / math.sqrt(1 << n_qubits))
    return max(range(250), key=lambda k: math.sin((2 * k + 1) * theta) ** 2)


def build_circuit(k: int) -> str:
    lines = [
        "OPENQASM 2.0;",
        'include "qelib1.inc";',
        "qreg q[17];",
        "creg c[16];",
    ]
    # Initialize input qubits in superposition
    lines.extend(f"h q[{i}];" for i in range(16))
    # Prepare ancilla in |-> state for phase kickback
    lines.append("x q[16];")
    lines.append("h q[16];")
    # Grover iterations
    for _ in range(k):
        lines.append(f"oracle {ORACLE_ARGS};")
        lines.append(f"diffuse {DIFFUSE_ARGS};")
    # Measure
    lines.extend(f"measure q[{i}] -> c[{i}];" for i in range(16))
    lines.append("END")
    return "\n".join(lines) + "\n"


def run(circuit: str) -> str:
    with socket.create_connection((HOST, PORT), timeout=10) as s:
        s.settimeout(60)
        # Wait for PoW prompt
        text = b""
        while b"solution: " not in text:
            chunk = s.recv(4096)
            if not chunk:
                break
            text += chunk
        # Solve PoW
        token = TOKEN_RE.search(text).group(1).decode()
        print(f"[*] Solving PoW for token: {token}")
        solution = solve_pow(token)
        s.sendall((solution + "\n").encode())
        # Wait for banner
        banner = b""
        while BANNER_END not in banner:
            chunk = s.recv(4096)
            if not chunk:
                break
            banner += chunk
        print("[*] Got banner, sending circuit...")
        # Send circuit
        s.sendall(circuit.encode())
        s.shutdown(socket.SHUT_WR)
        # Get response
        out = b""
        s.settimeout(60)
        try:
            while True:
                chunk = s.recv(4096)
                if not chunk:
                    break
                out += chunk
        except Exception:
            pass
    return out.decode("utf-8", "replace")


def main() -> int:
    k = grover_iterations(N)  # Returns 200
    circuit = build_circuit(k)
    print(f"[*] Using {k} Grover iterations")
    print(f"[*] Circuit size: {len(circuit)} bytes")
    
    response = run(circuit)
    print(f"[*] Response ({len(response)} bytes):")
    print(response)
    
    m = FLAG_RE.search(response)
    if m:
        print(f"\n[+] FLAG: {m.group(0)}")
        return 0
    return 1


if __name__ == "__main__":
    raise SystemExit(main())

Working Circuit

OPENQASM 2.0;
include "qelib1.inc";
qreg q[17];
creg c[16];
h q[0]; h q[1]; ... h q[15];  # Superposition on all input qubits
x q[16]; h q[16];              # Ancilla in |-> state for phase kickback
# 200 iterations of:
oracle q[0],q[1],...,q[16];    # Mark the target state
diffuse q[0],q[1],...,q[15];   # Amplitude amplification
# Measure all input qubits
measure q[0] -> c[0]; ... measure q[15] -> c[15];
END

Flag Meaning

The binary value in the flag 0110010101111010:

• Decimal: 25978
• Hex: 0x657a
• ASCII (little-endian): "ez" (e=0x65, z=0x7a)

This is typical CTF humor — the marked state spells "ez" (easy).