IEEE Access

A Quantum Differential Attack on ChaCha and Related Resources Estimation

Mintu Mandal, Hirendra Kumar Garai, Sabyasachi Dey

Published Jan 1, 2025• 1 citation

Abstract

Existing classical cryptanalytic techniques against ChaCha primarily rely on differential cryptanalysis, leveraging probabilistic neutral bits (PNBs) introduced by Aumassonet al. Separately, Batheet al. proposed a quantum brute force search attack using Grover’s algorithm with complexity 2128. However, since the setups for brute force attacks and differential attacks with probabilistic neutral bits differ significantly, the feasibility of applying Grover’s algorithm to the existing differential attacks on ChaCha remained unclear. In this paper, we demonstrate for the first time that a quantum setup for a PNB-based differential attack is indeed possible on ChaCha, where we can utilize the power of Grover’s algorithm to improve further. By combining Grover’s algorithm with PNB-based differential attack, we propose a quantum algorithm for PNB based differential attack and present a quantum attack on 6-round ChaCha that provides more than a quadratic speedup. Specifically, our attack achieves a complexity of 270, surpassing the quadratic speedup of the brute-force attack applying Grover’s algorithm, proposed by Batheet al. We achieve a circuit depth of 283with our algorithm, marking a substantial advancement in efficiency.

DOI: 10.1109/access.2025.3593658

Related papers

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 Truncated Differential Attacks Using Convolutions

Aurel Pichollet-Mugnier, André Schrottenloher

This paper focuses on quantum key-recovery attacks on block ciphers. Previous works on quantum differential and truncated differential attacks like [Kaplan et al., ToSC 2016] have shown that classical algorithms for key-recovery, typically based on generating differential pairs and sieving them, can be accelerated by up to a quadratic speedup using variants of quantum search, quantum amplitude amplification, and quantum collision-finding.>br/> In this paper, we introduce a new quantum truncated differential key-recovery attack, which leverages the quantum convolution algorithm introduced in [Schrottenloher, CRYPTO 2022] and previously used in linear cryptanalysis. We adapt this algorithm to the case of differential cryptanalysis, by rewriting the probability of a differential of an n-bit cipher as a convolution of functions with 2n-bit input. We then construct a quantum state whose amplitudes encode the probability of the differential for different key guesses, and use this as the starting point of a quantum search. In some cases (although not on practical ciphers so far), the speedup is better than quadratic compared to classical attacks. We also extend the framework to related-key differential attacks.We give applications to a 9-round attack on QARMAv2-64 adapted from [Ahmadian et al., DCC 2024] and a 12-round related-key attack on AES-256 from [Boura et al., CRYPTO 2023], which show improvement over classical attacks and over Kaplan et al.’s strategy when taking into account the amount of memory and the type of quantum memory used (as our attack requires only quantum-accessible classical memory).

IACR Transactions on Symmetric CryptologyMar 16, 20261 citation

Optimized Implementation and Analysis of CHAM in Quantum Computing

Yujin Yang, Kyungbae Jang, Anubhab Baksi +1 more

A quantum computer capable of running the Grover search algorithm, which reduces the complexity of brute-force attacks by a square root, has the potential to undermine the security strength of symmetric-key cryptography and hash functions. Recently, studies on quantum approaches have proposed analyzing potential quantum attacks using the Grover search algorithm in conjunction with optimized quantum circuit implementations for symmetric-key cryptography and hash functions. Analyzing quantum attacks on a cipher (i.e., quantum cryptanalysis) and estimating the necessary quantum resources are related to evaluating post-quantum security for the target cryptography algorithms. In this paper, we revisit quantum implementations of CHAM block cipher, an ultra lightweight cipher, with a focus on optimizing the linear operations in its key schedule. We optimized the linear equations of CHAM as matrices by applying novel optimized decomposition techniques. Using the improved CHAM quantum circuits, we estimate the cost of Grover’s key search and evaluate the post-quantum security strength with further reduced costs.

Applied SciencesApr 20, 20238 citations

A practical-quantum differential attack on block ciphers

Tarun Yadav, Manoj Kumar, Amit Kumar +1 more

Abstract Differential attack is a basic cryptanalysis method for block ciphers that exploits the high probability relations between the input and output differences. The existing work in quantum differential cryptanalysis of block ciphers is focused on resource estimation to recover the last round subkeys on the basis of relations constructed using classical methods. To find such relations using quantum computing, we propose a method to search the high probability differential and impossible differential characteristics. The method explores all possible input and output difference pairs using superposition of qubits. The proposed method is used to design the quantum circuit to search the differential characteristics for a toy cipher smallGIFT. We execute the quantum circuit on a quantum simulator to get differential and impossible characteristics. These characteristics are validated with the characteristics obtained using branch-and-bound based method. The differential characteristic is used to mount quantum key recovery attack using Grover's search. We provide the estimation of quantum resources to search the differential characteristics of lightweight block cipher GIFT-64 on a quantum computer.

Cryptography and CommunicationsJul 1, 202311 citations

Grover on PIPO

Kyungbae Jang, Gyeongju Song, Hyeokdong Kwon +4 more

The emergence of quantum computers is threatening the security of cryptography through various quantum algorithms. Among them, the Grover search algorithm is known to be efficient in accelerating brute force attacks on block cipher algorithms. To utilize the Grover’s algorithm for brute force attacks, block ciphers must be implemented in quantum circuits. In this paper, we present optimized quantum circuits of the SPN (Substitution Permutation Network) structured lightweight block cipher, namely the PIPO block cipher. In particular, the compact design of quantum circuits for the 8-bit Sbox is investigated. These optimization techniques are used to implement other cryptographic operations as quantum circuits. Finally, we evaluate quantum resources of Grover search algorithm for the PIPO block cipher in ProejctQ, a quantum simulator provided by IBM.

ElectronicsMay 17, 202121 citations

Quantum Differential Meet‐In‐The‐Middle Attack and Some Applications to Lightweight Ciphers

Yinsong Xu, Bin‐Bin Cai, Zheng Yuan +3 more

Abstract At CRYPTO 2023, Boura et al. proposed a new cryptanalysis technique, differential meet‐in‐the‐middle (MITM) attack. They used MITM technique to make the key recovery step of a differential attack more efficient. In this study, a quantum differential meet‐in‐the‐middle attack is proposed by using nested quantum search algorithm, which can achieve up to a quadratic speed‐up compared to the classical version. Besides, the time complexity of the attack can be reduced by at least a factor of ( is the guessed key length and is the block size) compared to the first quantum differential attack proposed by Kaplan et al. at ToSC 2016. Finally, to demonstrate the efficiency of our attack, it is applied to two reduced‐round lightweight block ciphers, PIPO and SIMON , to evaluate their post‐quantum security. When attacking the same number of rounds, the time complexity of our attack is significantly lower than that of classical attacks. For the 8‐round PIPO‐128 , the attack significantly improves efficiency, reducing the time complexity from to , cutting down the required qRAM size by a factor of and obtaining the data complexity instead of compared to the best quantum attack proposed by Schrottenloher at CRYPTO 2023. For the 19‐round SIMON‐32‐64 , the time complexity here will be instead of compared to the other quantum attack, and the attack can target more rounds than using Grover‐meets‐Simon technique.

Advanced Quantum TechnologiesAug 7, 20246 citations