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.
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.