Inspiration
Everyone has heard that "quantum computers will break encryption", but few people can explain how, or how close we really are. I wanted to build the attack myself, end to end, and see what the famous quantum speed-up looks like once realistic IBM device noise gets involved, instead of on a whiteboard.
What it does
Root Access runs a known-plaintext attack on a toy block cipher:
$$C = S(P \oplus K)$$
where P is the plaintext, K the secret key, C the ciphertext, and S an S-box. The main version uses the 4-bit S-box from the real PRESENT lightweight cipher. Given one (P, C) pair, the program finds K with Grover's algorithm.
A classical attacker tries keys one by one: about N/2 guesses on average for N = 2ⁿ keys. Grover needs only about
$$r = \left\lfloor \frac{\pi}{4}\sqrt{N} \right\rfloor$$
oracle calls, and after r iterations it measures the right key with probability
$$P_{\text{success}} = \sin^2\big((2r+1)\theta\big), \qquad \theta = \arcsin\frac{1}{\sqrt{N}}.$$
| Key bits | Keys | Classical guesses (avg) | Grover iterations | Ideal success |
|---|---|---|---|---|
| 2 | 4 | 2.5 | 1 | 100% |
| 3 | 8 | 4.5 | 2 | 94.5% |
| 4 | 16 | 8.5 | 3 | 96.1% |
An interactive Streamlit demo lets you pick a plaintext and a key, then:
- watch the key's probability grow iteration by iteration (animated),
- compare noise-free simulation with runs under realistic IBM device noise, side by side,
- see what the circuit costs once it's compiled for a real IBM device,
- see how the same math scales up to AES-128.
How I built it
Everything is in Python with Qiskit 2.x.
- Classical reference: the cipher, the S-boxes and a brute-force search that counts guesses. Every quantum result is checked against it.
- Reversible S-box: a quantum circuit can only do reversible operations, and an S-box is a permutation, so I build it directly as |x⟩ → |S(x)⟩ on n qubits using transformation-based synthesis.
- The oracle flips the sign of the correct key and nothing else: $$O\,|K\rangle = \begin{cases} -|K\rangle & \text{if } S(P \oplus K) = C \ \phantom{-}|K\rangle & \text{otherwise}\end{cases}$$ It XORs in P, applies the S-box, maps the target ciphertext to |11…1⟩, applies a multi-controlled Z, then undoes everything (uncomputation) so only the phase remains.
- Grover diffusion, repeated r times, then measurement. This runs on Qiskit Aer through the
SamplerV2primitive. - Realistic noise: I ran the attack on Qiskit's fake backends, offline noise models of real IBM devices (IBM Torino), compiled with
generate_preset_pass_manager. A sweep mode runs 0, 1, 2 and 3 iterations as one job, showing the probability rise and fall under noise. The same runner targets real IBM hardware through Qiskit IBM Runtime (least busy device,SamplerV2, dynamical decoupling); it's built and ready, but all results shown here are simulated. - Testing: 65
pytesttests, including an exhaustive check that the oracle is exactly right for every plaintext–key pair.
Challenges I ran into
- Noise wins fast. Compiled for an IBM device, my first 4-bit attack needed more than 1,100 two-qubit gates, which is far too deep to survive today's noise. So the noisy runs use 2- and 3-bit S-boxes.
- My first S-box circuit lost to a generic method. For PRESENT it needed more two-qubit gates (170) than Qiskit's generic unitary synthesis (139). Large multi-controlled gates are very expensive once compiled to real hardware gates.
- Bit ordering. Qiskit puts qubit 0 on the right of a bitstring. Getting keys, plaintexts and histograms to agree took careful conventions and tests.
- Fair comparisons. I wanted every number in the demo to be honest, so simulated noise is always labelled as simulated, never presented as hardware.
- Limited hardware access. With little free hardware time, I tested everything against IBM's device noise models instead, so every noisy result is reproducible by anyone, offline.
Accomplishments that I'm proud of
A circuit optimization with a short proof behind it. Inside the oracle the S-box always appears as S†MS, where the marking step M only multiplies basis states by ±1, so it is diagonal. If my circuit implements DS for any diagonal phase matrix D, the extra phases cancel, because diagonal matrices commute:
$$ (DS)^\dagger\, M\, (DS) = S^\dagger D^\dagger M D\, S = S^\dagger M\, S. $$
That let me replace Toffoli gates with cheaper relative-phase Toffolis:
| Full Grover circuit, compiled for IBM Torino | Before | After |
|---|---|---|
| 3-bit: two-qubit gates | 104 | 72 (−31%) |
| 4-bit: two-qubit gates | 1,127 | 642 (−43%) |
| 3-bit: success under simulated device noise | 65% | 71% |
What I learned
- How Grover works: an oracle that only flips a sign, plus a reflection about the mean, steadily moves probability onto the answer.
- Uncomputation matters: leftover garbage on the qubits would quietly break the interference that Grover depends on.
- On hardware, logical gate count means little. Two-qubit gate count and depth after compilation decide the result.
- Under noise, the textbook "optimal" iteration count isn't always best. With retries, 1 iteration at 65% success costs about 1.5 oracle calls per found key, versus about 2.8 for 2 iterations at 71%.
- The big picture: Grover takes AES-128 from about 2¹²⁷ guesses down to about 2⁶⁴ sequential iterations. That is still far out of reach, and it's why doubling the key length (AES-256) is the standard defence.
Honest caveat: with a single S-box layer, one (P, C) pair already gives K = S⁻¹(C) ⊕ P classically. This cipher is a teaching example of the mechanism and its hardware cost, not a real break.
What's next for Root Access
- Run the sweep on real IBM quantum hardware and compare it against the noise-model predictions
- A two-round cipher, C = S(S(P ⊕ K₁) ⊕ K₂), where classical inversion no longer works and the search becomes genuinely hard
- Readout error mitigation to get more out of real hardware
- A noise-aware speed-up metric built into the demo: the expected number of oracle calls to find the key once failed runs are retried
- Trying IBM's AI-powered transpiler to compress the circuits further