IACR Transactions on Symmetric Cryptology

Quantum Security Analysis of AES

Xavier Bonnetain, María Naya‐Plasencia, André Schrottenloher

Published Jun 11, 2019• 175 citations

Abstract

In this paper we analyze for the first time the post-quantum security of AES. AES is the most popular and widely used block cipher, established as the encryption standard by the NIST in 2001. We consider the secret key setting and, in particular, AES-256, the recommended primitive and one of the few existing ones that aims at providing a post-quantum security of 128 bits. In order to determine the new security margin, i.e., the lowest number of non-attacked rounds in time less than 2128 encryptions, we first provide generalized and quantized versions of the best known cryptanalysis on reduced-round AES, as well as a discussion on attacks that don’t seem to benefit from a significant quantum speed-up. We propose a new framework for structured search that encompasses both the classical and quantum attacks we present, and allows to efficiently compute their complexity. We believe this framework will be useful for future analysis.Our best attack is a quantum Demirci-Selçuk meet-in-the-middle attack. Unexpectedly, using the ideas underlying its design principle also enables us to obtain new, counter-intuitive classical TMD trade-offs. In particular, we can reduce the memory in some attacks against AES-256 and AES-128.One of the building blocks of our attacks is solving efficiently the AES S-Box differential equation, with respect to the quantum cost of a reversible S-Box. We believe that this generic quantum tool will be useful for future quantum differential attacks. Judging by the results obtained so far, AES seems a resistant primitive in the post-quantum world as well as in the classical one, with a bigger security margin with respect to quantum generic attacks.

DOI: 10.46586/tosc.v2019.i2.55-93

Related papers

Quantum Grover Attack on the Simplified-AES

Mishal Almazrooie, Rosni Abdullah, Azman Samsudin +1 more

In this work, a quantum design for the Simplified-Advanced Encryption Standard (S-AES) algorithm is presented. Also, a quantum Grover attack is modeled on the proposed quantum S-AES. First, quantum circuits for the main components of S-AES in the finite field F2[x]/(x4 + x + 1), are constructed. Then, the constructed circuits are put together to form a quantum version of S-AES. A C-NOT synthesis is used to decompose some of the functions to reduce the number of the needed qubits. The quantum S-AES is integrated into a black-box queried by Grover's algorithm. A new approach is proposed to uniquely recover the secret key when Grover attack is applied. The entire work is simulated and tested on a quantum mechanics simulator. The complexity analysis shows that a block cipher can be designed as a quantum circuit with a polynomial cost. In addition, the secret key is recovered in quadratic speedup as promised by Grover's algorithm.

International Conference on Software and Computer Applications (ICSCA)Feb 8, 201815 citations

A Study of Post Quantum Cryptographic Security Model Using Symmetric Key Algorithm

Sonali Sharma, Shilpi Sharma, Tanupriya Choudhury

The advancement in the field of technology and science has rendered the classical algorithms used for securing data vulnerable to attacks by quantum computers. Post quantum cryptography aims at establishing quantum safe algorithms so that data can be secured. Advanced Encryption Standard (AES) is a symmetric key block cipher which provides security against known quantum attacks. The Shor’s and Grover’s algorithms are the quantum algorithms which have proved to break encryption provided by security mechanisms like RSA and even have the potential to break AES-128 in future. However, if key size of symmetric key security mechanisms is increased then security provided by them cannot be broken by both classical and quantum computers in near future. Quantum computers are becoming more and more prevalent, but there is still some concern about their security. In this paper, we will show that the current quantum computers in use cannot break AES-256 encryption with Grover’s algorithm. We have implemented AES-256 for encryption of files in our system and proposed a proof that the qubits used by quantum computers are not enough to break AES-256 with Grover’s algorithm. We believe that this provides strong evidence that current quantum computers are not a threat to encrypted data using AES-256. We hope this will ease concerns about using quantum computing for secure applications and encourage further development of these powerful machines.

International Journal of Intelligent Systems and Applications in EngineeringApr 16, 20230 citations

Quantum impossible differential attack. Applications to CLEFIA, AES and SKINNY

Nicolas David

The general context Cryptography is a computer discipline that aims to protect messages through encryption systems. In symmetric cryptography, a secret parameter, called a key, is used both to encrypt and to decrypt messages. The security provided by a symmetric encryption system is evaluated using cryptanalysis techniques which aim, for example, to find the secret key. Quantum computer arrival could impact the cryptographic field. Indeed, in 1994, Shor exhibited that quantum computers could be used to improve assymetric cryptanalysis [17]. With the recent breakthrough in quantum computer, the security of cryptographic primitives against quantum adversary can not be taken as guaranteed. The NIST launched a competition for new primitives that are safe even against adversaries that has access to a quantum computer. To estimate the quantum security of a cryptographic scheme, it is necessary to perform its quantum cryptanalysis. Quantum cryptanalysis techniques sometimes are quantum adaptation of classical cryptanalysis techniques. This transformation is called quantizing. Let's note that an attack is valid if and only if it is more efficient than the naive attack. In the classical setting, the naive attack is the generic exhaustive search, in the quantum setting, it is the Grover search algorithm [14].

Sep 2, 20190 citations

Classical and Quantum based Differential Cryptanalysis Methods

Priyanka Jojan, Kapil Kumar Soni, Akhtar Rasool

The security of a significant proportion of cryptography in use today depends directly or indirectly on the presumed difficulty of either factoring or extracting discrete logarithms in polynomial time on quantum computers. This paper discusses a quantum version of differential cryptanalysis which propounds quadratic speedup over the existing classical one. Linear cryptanalysis and differential cryptanalysis are general form cryptanalysis which is primarily applicable to block cipher, but also to stream ciphers and cryptographic hash functions. Linear cryptanalysis is a known-plaintext attack, in which attacker studies probabilistic linear relations known as linear approximations between some bits of plaintext, some bits of cipher text and some bits of cipher key. And in differential cryptanalysis the role of attacker is to analyze how differences in input information can affect the resulting difference at the output. Differential Cryptanalysis is a chosen-plaintext attack. However, differential cryptanalysis is more compelling so in this paper we are proposing a quantum version of the same. The computational complexity of classical differential cryptanalysis reaches O(NK). But by applying variations of Grover's search that is either full or partial Quantum Search the number of queries required to find the cipher key will be reduced.

International Conference on Computing, Communication and Networking Technologies (ICCCNT)Jul 6, 20215 citations

Quantum Cryptanalysis: Evaluating the Impact of Shor’s and Grover’s Algorithms on Modern Encryption Standards

Mithal Hadi Jebur, Sumar Mohamed Khaleel

Motivated by Shor’s algorithm and its attractive features, the milestone results in quantum cryptanalysis were the discovery of quantum differential and linear cryptanalysis. In quantum cryptanalysis, quantum distinguishers imitate the classical setting. Details differ; however, as the distinguisher in the quantum setting can take maximum coset superposition of all possible subsets of plaintext pairs. Using quantum measurements, the winning gap of the game is exploited so that a distinguisher can still guess the secret key perfectly with a constant probability. Symmetric primitives also suffer reduced ideal security in the quantum world, but this security reduction is less drastic than for most asymmetric primitives. Stream ciphers, block ciphers, and cryptographic hash functions are primitives that are believed to resist quantum attacks. Analogs to Shor’s algorithm may say how hard it is to build a quantum computer, but devising quantum algorithms to outperform the best classical attacks for widely-used cryptographic primitives is probably outside the reach of current even if exponentially growing noisy intermediate-scale quantum (NISQ) computers.

CyberSystem journal.Dec 31, 20253 citations

Quantum-enhanced symmetric cryptanalysis for S-AES

Alexey Moiseevskiy

Advanced Encryption Standard is one of the most widely used and important symmetric ciphers for today. It well known, that it can be subjected to the quantum Grover's attack that twice reduces its key strength. But full AES attack requires hundreds of qubits and circuit depth of thousands, that makes impossible not only experimental research but also numerical simulations of this algorithm. Here we present an algorithm for optimized Grover's attack on downscaled Simplifed-AES cipher. Besides full attack we present several approaches that allows to reduce number of required qubits if some nibbles of the key are known as a result of side-channel attack. For 16-bit S-AES the proposed attack requires 23 qubits in general case and 19, 15 or 11 if 4, 8 or 12 bits were leaked in specifc confguration. Comparing to previously known 32-qubits algorithm this approach potentially allows to run the attack on today's NISQ-devices and perform numerical simulations with GPU, that may be useful for further research of problem-specifc error mitigation and error correction techniques.

arXiv:2304.05380Apr 11, 20231 citation