At EUROCRYPT 2006, the Nostradamus attack was originally proposed by Kelsey and Kohno, a cryptographic vulnerability in which a hash value y can be pre-determined by an adversary and a suffix S can later be fabricated such that H(P‖S) = y for a priori unknown prefix P. Their attack framework was shown to achieve a time complexity of \(O(\sqrt {n}\cdot 2^{2n/3})\), with n denoting the hash function’s output bit-length. At ASIACRYPT 2022, a quantum variant of the Nostradamus attack was introduced by Benedikt et al., and the time complexity was reduced from \(O(\sqrt {n}\cdot 2^{2n/3})\) to \(O(\sqrt [3]{n}\cdot 2^{3n/7})\). In ToSC 2023, the first dedicated Nostradamus attack targeting AES-like hash functions was proposed by Zhang et al., and subsequently at ToSC 2024 the meet-in-the-middle attack framework was improved by Dong et al., resulting in enhanced attack results. In this paper, a more efficient algorithm for constructing diamond structures is proposed. By designing an unbalanced diamond structure shaped as an unbalanced binary tree, the time complexity of the offline phase is reduced from \(O(\sqrt [3]{k}\cdot 2^{(n+2k)/3})\) to O(2(n + 2k)/3) in the qRAM setting, where k represents the height of the diamond structure. In detail, the time complexity of the quantum Nostradamus attack is improved from \(O(\sqrt [3]{n}\cdot 2^{3n/7})\) to O(23n/7). Furthermore, this new offline structure is applied to the MITM Nostradamus attack targeting AES-MMO, yielding lower time complexity results in the qRAM setting.
At EUROCRYPT 2006, the Nostradamus attack was originally proposed by Kelsey and Kohno, a cryptographic vulnerability in which a hash value y can be pre-determined by an adversary and a suffix S can later be fabricated such that H(P‖S) = y for a priori unknown prefix P. Their attack framework was shown to achieve a time complexity of (O(\sqrt {n}\cdot 2^{2n/3})), with n denoting the hash function’s output bit-length. At ASIACRYPT 2022, a quantum variant of the Nostradamus attack was introduced by Benedikt et al., and the time complexity was reduced from (O(\sqrt {n}\cdot 2^{2n/3})) to (O(\sqrt [3]{n}\cdot 2^{3n/7})). In ToSC 2023, the first dedicated Nostradamus attack targeting AES-like hash functions was proposed by Zhang et al., and subsequently at ToSC 2024 the meet-in-the-middle attack framework was improved by Dong et al., resulting in enhanced attack results. In this paper, a more efficient algorithm for constructing diamond structures is proposed. By designing an unbalanced diamond structure shaped as an unbalanced binary tree, the time complexity of the offline phase is reduced from (O(\sqrt [3]{k}\cdot 2^{(n+2k)/3})) to O(2(n + 2k)/3) in the qRAM setting, where k represents the height of the diamond structure. In detail, the time complexity of the quantum Nostradamus attack is improved from (O(\sqrt [3]{n}\cdot 2^{3n/7})) to O(23n/7). Furthermore, this new offline structure is applied to the MITM Nostradamus attack targeting AES-MMO, yielding lower time complexity results in the qRAM setting.
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.
Our work explores the key recovery attack using the Grover's search on the three variants of AES (-128, -192, -256). In total, we develop a pool of 26 implementations per AES variant (totaling 78), by taking the state-of-the-art advancements in the relevant fields into account. We present the least Toffoli depth and full depth implementations of AES, thereby improving from Zou et al.'s Asiacrypt'20 paper by more than 97 percent for each variant of AES. We show that the qubit count - Toffoli depth product is reduced from theirs by more than 87 percent. Furthermore, we analyze the Jaques et al.'s Eurocrypt'20 implementations in detail, fix the bugs (arising from some problem of the quantum computing tool used), and report corrected benchmarks (which seem to improve from the authors' own bug-fixing, thanks to our architecture consideration). To the best of our finding, our work improves from all the previous works (including the Asiacrypt'22 paper by Huang and Sun, the Asiacrypt'23 paper by Liu et al. and the Asiacrypt'24 paper by Shi and Feng) in terms of various quantum circuit complexity metrics. To be more precise, we estimate the currently best-known quantum attack complexities for AES-128 ( 2 156.2630 ), AES-192 ( 2 221.5801 ) and AES-256 ( 2 286.0731 ). Additionally, we achieve the least Toffoli depth - qubit count product for AES-128 ( 121920 , improving from 130720 by Shi and Feng in Asiacrypt'24), AES-192 ( 161664 , improving from 188880 by Liu et al. in Asiacrypt'23) and AES-256 ( 206528 , improving from 248024 by Liu et al. in Asiacrypt'23) so far. We further investigate the prospect of the Grover's search. We propose four new implementations of the S-box, one new implementation of the MixColumn; as well as five new architecture (one is motivated by the architecture by Jaques et al. in Eurocrypt'20, and the rest four are entirely our innovation). Under the MAXDEPTH constraint (specified by NIST), the circuit depth metrics (Toffoli depth, T -depth and full depth) become crucial factors and parallelization for often becomes necessary. We provide the least depth implementation in this respect that offers the best performance in terms of metrics like depth-squared - qubit count product, depth - gate count product.
To enhance the efficiency of the quantum differential Meet-In-The-Middle attack, an improved scheme based on quantum collision search is proposed. The traditional quantum search steps were replaced with Ambainis’ quantum collision search algorithm. This replacement optimized the matching process between candidate keys and plaintexts in the Meet-in-the-Middle phase and significantly reduced time complexity. The improved attack scheme is applied to PIPO-128, SKINNY-128-384, and AES-256, achieving key recovery attacks for 8, 23, and 12 rounds, respectively. Analysis results under both Q1 and Q2 models demonstrate that the proposed scheme outperforms existing classical and quantum attacks in both time and memory complexity, validating its effectiveness and superiority in cryptanalysis.
Key-length extension (KLE) techniques provide a general approach to enhancing the security of block ciphers by using longer keys. There are mainly two classes of KLE techniques, cascade encryption and XOR-cascade encryption. This paper presents several quantum meet-in-the-middle (MITM) attacks against two specific KLE constructions.
For the two-key triple encryption (2kTE), we propose two quantum MITM attacks under the Q2 model. The first attack, leveraging the quantum claw-finding (QCF) algorithm, achieves a time complexity of O(22κ/3) with O(22κ/3) quantum random access memory (QRAM). The second attack, based on Grover's algorithm, achieves a time complexity of O(2κ/2) with O(2κ) QRAM. The latter complexity is nearly identical to Grover-based brute-force attack on the underlying block cipher, indicating that 2kTE does not enhance security under the Q2 model when sufficient QRAM resources are available.
For the 3XOR-cascade encryption (3XCE), we propose a quantum MITM attack applicable to the Q1 model. This attack requires no QRAM and has a time complexity of O(2(κ+n)/2) (κ and n are the key length and block length of the underlying block cipher, respectively.), achieving a quadratic speedup over classical MITM attack.
Furthermore, we extend the quantum MITM attack to quantum sieve-in-the-middle (SITM) attack, which is applicable for more constructions. We present a general quantum SITM framework for the construction ELE=E2∘L∘E1 and provide specific attack schemes for three different forms of the middle layer L. The quantum SITM attack technique can be further applied to a broader range of quantum cryptanalysis scenarios.
Recently, Hosoyamada and Sasaki (EUROCRYPT 2020), and Xiaoyang Dong et al. (ASIACRYPT 2020) proposed quantum collision attacks against AES-like hashing modes AES-MMO and AES-MP. Their collision attacks are based on the quantum version of the rebound attack technique exploiting the differential trails whose probabilities are too low to be useful in the classical setting but large enough in the quantum setting. In this work, we present dedicated quantum free-start collision attacks on Hirose’s double block length compression function instantiated with AES-256, namely HCF-AES-256. The best publicly known classical attack against HCF-AES-256 covers up to 9 out of 14 rounds. We present a new 10-round differential trail for HCF-AES-256 with probability 2−160, and use it to find collisions with a quantum version of the rebound attack. Our attack succeeds with a time complexity of 285.11 and requires 216 qRAM in the quantum-attack setting, where an attacker can make only classical queries to the oracle and perform offline computations. We also present a quantum free-start collision attack on HCF-AES-256 with a time complexity of 286.07 which outperforms Chailloux, Naya-Plasencia, and Schrottenloher’s generic quantum collision attack (ASIACRYPT 2017) in a model when large qRAM is not available.