November 6, 2023 · 6 min read

Hacking Cryptographic Protocols with Advanced Variational Quantum Attacks

Here we introduce an improved approach to Variational Quantum Attack Algorithms (VQAA) on crytographic protocols. Our methods provide robust quantum attacks to well-known cryptographic algorithms, more efficiently and with remarkably fewer qubits than previous approaches. We implement simulations of our attacks for symmetric-key protocols such as S-DES, S-AES and Blowfish. For instance, we show how our attack allows a classical simulation of a small 8-qubit quantum computer to find the secret key of one 32-bit Blowfish instance with 24 times fewer number of iterations than a brute-force attack. Our work also shows improvements in attack success rates for lightweight ciphers such as S-DES and S-AES. Further applications beyond symmetric-key cryptography are also discussed, including asymmetric-key protocols and hash functions. In addition, we also comment on potential future improvements of our methods. Our results bring one step closer assessing the vulnerability of large-size classical cryptographic protocols with Noisy Intermediate-Scale Quantum (NISQ) devices, and set the stage for future research in quantum cybersecurity.

Multiverse Computing

Today’s world is all about information. Beyond the im- pact of other technologies, secure communications have become one of the cornerstones of modern society. In this era more than ever, information is both an asset and a vulnerability, and therefore cryptology’s relevance has escalated to unprecedented levels in history. Infor- mation control is critical, and it is therefore no surprise that quantum computing has emerged as one of the key disruptive technologies in this ambit, given the poten- tial of quantum computers to hack current cybersecurity standards. Whoever wins the quantum computing race, is also called to win the information race.

The field of cryptology serves as the cornerstone of secure digital communication, encompassing both cryp- tography and cryptanalysis. It provides tools for en- crypting sensitive data, thereby ensuring its confiden- tiality and integrity during transmission over insecure networks. Cryptanalysis, the counterpart to cryptogra- phy, aims to break these secure communication channels. It employs a variety of techniques, ranging from brute- force attacks (which involve an exhaustive search through all possible keys) to more structured approaches. These last may include ciphertext-only, known-plaintext, and chosen-plaintext attack, each one posing a specific set of challenges for the attacker. Over the years, cryptanalysis has become an art in itself.

Cryptographic functions are the backbone of these secure communication systems. Divided into Hash al- gorithms, symmetric algorithms and asymmetric algo- rithms, each scheme provides specific and valuable fea- tures. For instance, hash algorithms are crucial for data integrity and password verification [1], and are central to cryptocurrencies such as Bitcoin. Symmetric key al- gorithms, like DES [2], Blowfish [3], and AES [4], use a single secret key for both encryption and decryption providing speed advantages over its counterpart public-

key cryptography. This latter is exemplified by RSA [5], which uses a public key for encryption and a private key for decryption, being thus an example of asymmetric cryptography. Public-key cryptography can be employed for establishing the secret key that will be used in a sym- metric protocol, the combination of both cryptographic methods often results in establishing more secure com- munication channels.

In this context, quantum computing [6] has chal- lenged the very foundations of cryptology. By leveraging the principles of quantum mechanics, quantum comput- ers hold the promise of polynomial or even exponential speed-ups for certain computational tasks, including the ones often encountered in cryptography. Quantum com- puters therefore pose a significant threat to classical cryp- tographic systems. The factoring algorithm by Shor [7] showed that quantum computers could, in practice, hack RSA and related cybersecurity protocols efficiently. Re- cent estimations point out that one would require around 20 million noisy qubits to factor 2048-bit RSA integers in 8 hours [8], still beyond reach of current quantum proces- sors. More generically, brute-force attacks can also be en- hanced via quantum computing using Grover’s algorithm for searching unstructured databases [9], and which has been tested for symmetric DES protocols [10].

In the current era of Noisy Intermediate-Scale Quan- tum (NISQ) devices, progress has also been made along the lines of of variational quantum algorithms. For exam- ple, the so-called Variational Quantum Attack Algorithm (VQAA) [11] implements a variational quantum circuit aiming at decoding the key of AES-like symmetric proto- cols specifically designed for the Simplified-Data Encryp- tion Standard (S-DES) [12]. In practice, VQAA encodes a known ciphertext in the lowest-energy state of a clas- sical Hamiltonian, akin to a cost function, and aims to find such state by trying out different keys, effectively re- trieving the secret key by optimizing a set of variational parameters. As stated, however, the VQAA algorithmstill uses a very large number of qubits, making it thus impractical for real-life ciphers.

Full paper here