A Quantum Circuit to Execute a Key-Recovery Attack Against the DES and 3DES Block Ciphers

Quantum computing enabled cryptanalytic techniques are able to concretely reduce the security margin of existing cryptographic primitives. While this reduction is only polynomial for symmetric cryptosystems, it still provides a reduction in their security margin. In this work, we propose a detailed quantum circuit designed to cryptanalyze both the Data Encryption Standard (DES) cryptosystem, and its successor Triple-DES (3DES), currently standardized in ISO/IEC 18033–3, and still widely employed in satellite data and bank card encryption. To do so, we introduce the first quantum circuit implementation of the 8 substitution tables (a.k.a. S-boxes), applying a bitslicing strategy, which is currently the most efficient classical combinatorial circuit design in terms of number of two inputs Boolean gates. Secondly, we present the complete quantum circuits required to attack both DES and 3DES leveraging Grover's algorithm. We provide finite regime, closed form equations, delineating the circuits complexities in terms of the number of qubits, gates, depth and number of qubits multiplied by depth. The complexity analysis is based on two distinct gate sets: a NOT-CNOT-Toffoli (NCT) extended with the Hadamard gate; and the fault-tolerant Clifford+T. Finally, akin to the classical attack to the 3DES, we introduce a meet-in-the-middle strategy relying on an exponential amount of Quantum Random Access Memory. Our findings show that the 3DES with keying option 2, the most widely employed variant of 3DES, can be attacked with a circuit depth of approximately <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$2^{67}$</tex> and less than a thousand qubits. This is close to the <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$2^{64}$</tex> value suggested by NIST for the depth achievable sequentially by a single quantum computer in a decade. Our technique can be further sped up parallelizing the approach onto multiple devices, pointing to the practicality of cryptanalyzing 3DES in such a scenario.