quant?

Platform: Umdctf | Category: Cryptography | Type: Challenge | Difficulty: Medium | OS: NA | Author: D3v0o0Nu11 | Date: 2026-04-26 | Status: Solved Techniques: grover_algorithm, quantum_oracle_search, amplitude_amplification, optimal_iteration_count

Summary

Task: quantum oracle search with 16 qubits, black-box oracle marks one state out of 65536. Solution: standard Grover's algorithm with ~200 iterations achieves near-perfect amplification of the marked state.

Recon

Port scan

 bash read-only • copy allowed Copy
nmap -p- -sV -sC <TARGET> --min-rate 1000 -Pn

Enumeration highlights

• Event: umdctf | ID: 20260426_umdctf_quant
• Tags: quantum, qiskit, grover, openqasm, black_box_oracle, phase_kickback
• Indicators: quantum circuit simulator with oracle gate, 16+ qubits with ancilla, limited oracle calls (250), diffuse operator provided, OpenQASM-like syntax
• Source: 20260426_umdctf_quant.md

Foothold

Vulnerability / Misconfiguration

1. grover_algorithm
2. quantum_oracle_search
3. amplitude_amplification
4. optimal_iteration_count

 bash read-only • copy allowed Copy
<command>

Exploitation

• See original writeup content for detailed exploitation.

Privilege Escalation

Enumeration

 bash read-only • copy allowed Copy
sudo -l
find / -perm -4000 2>/dev/null
getcap -r / 2>/dev/null
cat /etc/crontab
ps aux

Exploitation

1. N/A for challenge-type writeup; see exploitation above.
2. Flag obtained via challenge solve.

 bash read-only • copy allowed Copy
<command>

Flags

Key Takeaways / Lessons

• grover_algorithm
• quantum_oracle_search
• amplitude_amplification
• optimal_iteration_count
• Tags: quantum, qiskit, grover, openqasm, black_box_oracle, phase_kickback

Original Writeup

<details><summary>Click to expand original content</summary>

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:

 python read-only • copy allowed Copy
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

 python read-only • copy allowed Copy
#!/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 REDACTED:

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

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

</details>

---

signed by XESXOR