Quantum Meet-in-the-Middle Attacks on Key-Length Extension Constructions

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\(2^2κ/3\) with O\(2^2κ/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=E^2circ Lcirc E¹ 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.