×

Quantum Demiric-Selcuk meet-in-the-middle attacks on reduced-round AES. (English) Zbl 1485.94123

Summary: In this paper, we employ quantum algorithms to attack the reduced-round AES based on the meet-in-the-middle attack proposed by Demiric and Selcuk (DS-MITM). Technically, we adopt the Grover’s algorithm and the quantum claw-finding algorithm respectively to implement the attack based on the \(Q1\) model (quantum computers perform offline computations, and classical methods perform online queries). Then we propose a data/memory/time trade-off to optimize the new quantum algorithm, which can further reduce the time complexity of the attack. Compared to the DS-MITM, the new algorithm can significantly reduce the complexities, and it can also be applied to AES-128.

MSC:

94A60 Cryptography
68P10 Searching and sorting
68Q25 Analysis of algorithms and problem complexity
81P68 Quantum computation
81P94 Quantum cryptography (quantum-theoretic aspects)

Software:

Square
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Daemen, J.; Knudsen, L.; Rijmen, V., The block cipher square, Lect. Notes Comput. Sci, 1267, 10 (1998) · Zbl 1385.94025
[2] Gilbert, H., Minier, M.: A collision attack on 7 rounds of rijndael. In: AES Candidate Conference, pp. 230-241 (2000)
[3] Demirci, H., Selçuk, A.A.: MA meet-in-the-middle attack on 8-round aes. In: Fast Software Encryption, pp 116-126. Springer, Berlin (2008) · Zbl 1154.68391
[4] Demirci, H., Taşkın, İ, Çoban, M., Baysal, A.: Improved meet-in-the-middle attacks on aes. In: Progress in Cryptology - INDOCRYPT 2009, pp 144-156. Springer, Berlin (2009) · Zbl 1273.94345
[5] Dunkelman, O.; Keller, N.; Shamir, A., Improved single-key attacks on 8-round aes-192 and aes-256, J. Cryptol., 28, 158-176 (2010) · Zbl 1253.94045
[6] Derbez, P., Fouque, P.-A., Jean, J.: Improved key recovery attacks on reduced-round aes in the single-key setting. In: Advances in Cryptology - EUROCRYPT 2013, pp 371-387. Springer, Berlin (2013) · Zbl 1306.94044
[7] Derbez, P., Fouque, P.-A.: Exhausting demirci-selçuk meet-in-the-middle attacks against reduced-round aes. In: Fast Software Encryption, pp 541-560. Springer, Berlin (2014) · Zbl 1321.94053
[8] Bouillaguet, C., Derbez, P., Fouque, P. -A.: Automatic search of attacks on round-reduced aes and applications. In: Advances in Cryptology - CRYPTO 2011, pp 169-187. Springer, Berlin (2011) · Zbl 1287.94056
[9] Biham, E., Keller, N.: Cryptanalysis of reduced variants of rijndael, 3rd AES Conference, vol. 230 (2000)
[10] Mala, H., Dakhilalian, M., Rijmen, V., Modarres-Hashemi, M.: Improved impossible differential cryptanalysis of 7-round aes-128. In: Progress in Cryptology - INDOCRYPT 2010, pp 282-291. Springer, Berlin (2010) · Zbl 1253.94060
[11] Boura, C.; Lallemand, V.; Naya-Plasencia, M.; Suder, V., Making the impossible possible, J. Cryptol., 31, 02 (2017) · Zbl 1421.94041
[12] Bogdanov, A., Khovratovich, D., Rechberger, C.: Biclique cryptanalysis of the full aes. In: Advances in Cryptology - ASIACRYPT 2011, pp 344-371. Springer, Berlin (2011) · Zbl 1227.94032
[13] Grassi, L., Rechberger, C., Sønjom, S.: A new structural-differential property of 5-round aes. In: Advances in Cryptology - EUROCRYPT 2017, pp 289-317. Springer International Publishing, Berlin (2017) · Zbl 1415.94433
[14] Grassi, L., Mixture differential cryptanalysis: a new approach to distinguishers and attacks on round-reduced aes, IACR Transactions on Symmetric Cryptology, 2018, 133-160 (2018) · doi:10.46586/tosc.v2018.i2.133-160
[15] Grover, L.: Fast quantum mechanical algorithm for database search. In: Proceedings of the 28th Annual ACM Symposium on the Theory of Computing (1996) · Zbl 0922.68044
[16] Brassard, G., Hoyer, P., Mosca, M., de Montreal, A.T.D.U., Aarhus, B.U.O., Waterloo, C.U.: Quantum amplitude amplification and estimation, arXiv: Quantum Physics (2000)
[17] Buhrman, H.; Durr, C.; Heiligman, M.; Høyer, P.; Magniez, F.; Santha, M.; Wolf, R., Quantum algorithms for element distinctness, SIAM J. Comput., 34, 131-137 (2001) · Zbl 1081.68029
[18] Brassard, G.; Høyer, P.; Tapp, A., Quantum algorithm for the collision problem, ACM SIGACT News (Cryptology Column), 28, 06 (1997)
[19] Wang, P.; Tian, S.; Sun, Z.; Xie, N., Quantum algorithms for hash preimage attacks, Quantum Eng, 2, 04 (2020) · doi:10.1002/que2.36
[20] Kaplan, M.: Quantum attacks against iterated block ciphers, arXiv: Quantum Physics, vol. arXiv:1410.1434 (2014)
[21] Leander, G., May, A.: Grover meets simon – quantumly attacking the fx-construction. In: Advances in Cryptology - ASIACRYPT 2017, pp 161-178. Springer International Publishing (2017) · Zbl 1380.94109
[22] Hosoyamada, A., Sasaki, Y.: Quantum demiric-selçuk meet-in-the-middle attacks: applications to 6-round generic feistel constructions. In: Security and Cryptography for Networks, pp 386-403. Springer International Publishing (2018) · Zbl 1514.81107
[23] Kuwakado, H., Morii, M.: Security on the quantum-type even-mansour cipher. In: 2012 International Symposium on Information Theory and its Applications, pp 312-316 (2012)
[24] Kaplan, M., Leurent, G., Leverrier, A., Naya-Plasencia, M.: Breaking symmetric cryptosystems using quantum period finding. In: Advances in Cryptology - CRYPTO 2016, pp 207-237. Springer, Berlin (2016) · Zbl 1391.94766
[25] Kuperberg, G., A subexponential-time quantum algorithm for the dihedral hidden subgroup problem, Siam Journal on Computing - SIAMCOMP, 35, 12 (2011)
[26] Boyer, M.; Brassard, G.; Høyer, P.; Tapp, A., Tight bounds on quantum search, Fortschritte der Physik, 46, 01 (1998) · doi:10.1002/(SICI)1521-3978(199806)46:4/5<493::AID-PROP493>3.0.CO;2-P
[27] Zalka, C., Grover’s quantum searching algorithm is optimal, Phys. Rev. A, 60, 10 (1999) · doi:10.1103/PhysRevA.60.2746
[28] Derbez, P., Perrin, L.: Meet-in-the-middle attacks and structural analysis of round-reduced prince. In: Fast Software Encryption, pp 190-216. Springer, Berlin (2015) · Zbl 1367.94308
[29] Ferguson, N., Kelsey, J., Lucks, S., Schneier, B., Stay, M., Wagner, D., Whiting, D.: Improved cryptanalysis of rijndael. In: Fast Software Encryption, pp 213-230. Springer, Berlin (2001) · Zbl 0994.68631
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.