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.

  1. Classical reference: the cipher, the S-boxes and a brute-force search that counts guesses. Every quantum result is checked against it.
  2. 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.
  3. 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.
  4. Grover diffusion, repeated r times, then measurement. This runs on Qiskit Aer through the SamplerV2 primitive.
  5. 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.
  6. Testing: 65 pytest tests, 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

Built With

Share this project:

Updates

Submission history