Quantum brute force in cryptanalysis

Quantum Brute-Force Attack on Encryption

A brute-force key search attack is applied when the space of possible plaintexts is significantly smaller than the entire character space. Eve intercepts a ciphertext from Alice to Bob and implements two functions: DECRYPT(key, ciphertext) for decryption and ISPLAINTEXT(text) to check if the text belongs to the set of valid plaintexts. If the encryption is block-based, DECRYPT works on blocks, and ISPLAINTEXT accumulates the results.

The pseudocode for the attack is simple:

for each key
    text = DECRYPT(key, ciphertext)
    if ISPLAINTEXT(text) == 0 then return (key,text)
end for

ISPLAINTEXT criteria use character statistics, combinations, or heuristics without databases—checks for frequency, entropy, or language patterns.

Information Theory for Success Assessment

For a monoalphabetic cipher, we estimate the probability of a false positive:

• LENGTH(plaintext) — length in bits
• LENGTH(key) — key length in bits
• LENGTH(ciphertext) — ciphertext length in bits
• ENTROPY(plaintext) — Shannon entropy of the plaintext

Conditions:

• LENGTH(plaintext) ≤ LENGTH(ciphertext)
• Probability of false positive: 2^-(LENGTH(plaintext) - ENTROPY(plaintext))
• If LENGTH(plaintext) - ENTROPY(plaintext) > LENGTH(key), the key is uniquely determined

For length-preserving algorithms: when LENGTH(ciphertext) - ENTROPY(plaintext) ≥ LENGTH(key), the attack is guaranteed to find the key.

Quantum Approach to Brute-Force

Quantum computing relies on superposition and entanglement of qubits. A register of N entangled qubits is equivalent to 2^N classical states. Arithmetic (addition, multiplication, shifts) is implemented with quantum gates—transformations of unitary operators.

Any classical function over a key register can be transformed into a unitary U(K), where K is a superposition of all keys.

Grover's Algorithm for Key Search

Steps of the quantum attack:

• Initialize a register K of length LENGTH(key) in a uniform superposition of all keys: |K⟩ = (1/√2^{LENGTH(key)}) Σ |key⟩
• Apply the oracle U(K) = DECRYPT(K, ciphertext), then ISPLAINTEXT(U(K)): the phase is inverted for states with ISPLAINTEXT == 0
• Amplify the amplitude of the target state using Grover's algorithm: π/4 * √2^{LENGTH(key)} iterations with diffusion operators and the oracle
• Measure register K—it collapses to the correct key with probability ~1

The oracle requires implementing DECRYPT and ISPLAINTEXT as reversible quantum circuits. For block ciphers—process by blocks with ancillary qubits.

// Quantum circuit pseudocode (Q# style)
operation BruteForce(keyReg : Qubit[], ciphertext : String) : (Int, String) {
    // Apply H to all qubits for superposition
    ApplyToEach(H, keyReg);
    // Oracle: phase flip if ISPLAINTEXT(DECRYPT(keyReg, ciphertext)) == 0
    Oracle(keyReg, ciphertext);
    // Grover iterations
    for iter in 0 .. GroverIterations() - 1 {
        GroverDiffusion(keyReg);
        Oracle(keyReg, ciphertext);
    }
    // Measure
    let key = MeasureKey(keyReg);
    return (0, DECRYPT(key, ciphertext));
}

Quadratic speedup: O(√2^{LENGTH(key)}) instead of O(2^{LENGTH(key)}).

Key Takeaways

• Classical vs. Quantum: Brute-forcing a 128-bit key on a CPU—10^38 operations; on a quantum computer—10^19.
• Success Condition: Plaintext redundancy (LENGTH - ENTROPY) > LENGTH(key)/2 for a practical attack.
• Limitations: Noise in NISQ systems requires error correction; the DECRYPT oracle is complex for AES-like ciphers.
• Post-Quantum Cryptography: Transition to lattice-based, hash-based schemes is essential.
• Practice: Q# / Cirq simulators demonstrate on 20-bit keys.

— Editorial Team