nach oben

Designs, Codes and Cryptography

Erschienen in:

17.08.2023

Quantum impossible differential attacks: applications to AES and SKINNY

verfasst von: Nicolas David, María Naya-Plasencia, André Schrottenloher

Erschienen in: Designs, Codes and Cryptography | Ausgabe 3/2024

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In this paper we propose the first efficient quantum version of key-recovery attacks on block ciphers based on impossible differentials, which was left as an open problem in previous work. These attacks work in two phases. First, a large number of differential pairs are collected, by solving a limited birthday problem with the attacked block cipher considered as a black box. Second, these pairs are filtered with respect to partial key candidates. We show how to translate the pair filtering step into a quantum procedure, and provide a complete analysis of its complexity. If the path of the attack can be properly reoptimized, this procedure can reach a significant speedup with respect to classical attacks. We provide two applications on SKINNY-128-256 and AES-192/256. These results do not threaten the security of these ciphers but allow us to better understand their (post-quantum) security margin.

Vorheriger Artikel Analysis and computation of multidimensional linear complexity of periodic arrays

Nächster Artikel Antipodal two-weight rank metric codes

Note that sometimes, not all key schedule relations can be used in the decomposition, and so, the set \(K_1 \times K_2 \times \cdots \times K_\ell \) is larger than \(K_{\textrm{in} \cup \textrm{out}}\) itself.

Ambainis A.: Quantum walk algorithm for element distinctness. SIAM J. Comput. 37(1), 210–239 (2007). https://doi.org/10.1137/S0097539705447311.MathSciNetCrossRef

Batcher K.E.: Sorting networks and their applications. In: AFIPS Spring Joint Computing Conference. AFIPS Conference Proceedings, vol. 32, pp. 307–314. Thomson Book Company, Washington D.C. (1968)

Beierle C., Jean J., Kölbl S., Leander G., Moradi A., Peyrin T., Sasaki Y., Sasdrich P., Sim S.M.: The SKINNY family of block ciphers and its low-latency variant MANTIS. In: CRYPTO (2). Lecture Notes in Computer Science, vol. 9815, pp. 123–153. Springer (2016)

Bennett C.H., Bernstein E., Brassard G., Vazirani U.V.: Strengths and weaknesses of quantum computing. SIAM J. Comput. 26(5), 1510–1523 (1997). https://doi.org/10.1137/S0097539796300933.MathSciNetCrossRef

Biham E., Biryukov A., Shamir A.: Cryptanalysis of skipjack reduced to 31 rounds using impossible differentials. J. Cryptol. 18(4), 291–311 (2005). https://doi.org/10.1007/s00145-005-0129-3.MathSciNetCrossRef

Bonnetain X., Jaques S.: Quantum period finding against symmetric primitives in practice. IACR Trans. Cryptogr. Hardw. Embed. Syst. 2022(1), 1–27 (2022).

Bonnetain X., Naya-Plasencia M., Schrottenloher A.: On quantum slide attacks. In: SAC. Lecture Notes in Computer Science, vol. 11959, pp. 492–519. Springer (2019)

Bonnetain X., Naya-Plasencia M., Schrottenloher A.: Quantum security analysis of AES. IACR Trans. Symmetric Cryptol. 2019(2), 55–93 (2019). https://doi.org/10.13154/tosc.v2019.i2.55-93.CrossRef

Bonnetain X., Hosoyamada A., Naya-Plasencia M., Sasaki Y., Schrottenloher A.: Quantum attacks without superposition queries: The offline simon’s algorithm. In: ASIACRYPT (1). Lecture Notes in Computer Science, vol. 11921, pp. 552–583. Springer (2019)

10.

Bonnetain X., Chailloux A., Schrottenloher A., Shen Y.: Finding many collisions via reusable quantum walks. In: EUROCRYPT 2023, to Appear. Lecture Notes in Computer Science (2023). https://eprint.iacr.org/2022/676

11.

Boura C., Naya-Plasencia M., Suder V.: Scrutinizing and improving impossible differential attacks: applications to clefia, camellia, lblock and simon. In: ASIACRYPT (1). Lecture Notes in Computer Science, vol. 8873, pp. 179–199. Springer (2014)

12.

Boura C., Lallemand V., Naya-Plasencia M., Suder V.: Making the impossible possible. J. Cryptol. 31(1), 101–133 (2018). https://doi.org/10.1007/s00145-016-9251-7.MathSciNetCrossRef

13.

Brassard G., Høyer P., Tapp A.: Quantum cryptanalysis of hash and claw-free functions. In: LATIN. Lecture Notes in Computer Science, vol. 1380, pp. 163–169. Springer (1998)

14.

Brassard G., Hoyer P., Mosca M., Tapp A.: Quantum amplitude amplification and estimation. Contemp.Math. 305, 53–74 (2002).MathSciNetCrossRef

15.

Childs A.M., Eisenberg J.M.: Quantum algorithms for subset finding. Quantum Inf. Comput. 5(7), 593–604 (2005).

16.

Daemen J., Rijmen V.: The design of Rijndael: AES—the advanced encryption standard. Information security and cryptography. Springer, Cham (2002) https://doi.org/10.1007/978-3-662-04722-4.CrossRef

17.

Daemen J., Knudsen L.R., Rijmen V.: The block cipher square. In: FSE. Lecture Notes in Computer Science, vol. 1267, pp. 149–165. Springer (1997)

18.

Dawson C.M., Nielsen M.A.: The Solovay–Kitaev algorithm. Quantum Inf. Comput. 6(1), 81–95 (2006).MathSciNet

19.

Demirci H., Selçuk A.A.: A meet-in-the-middle attack on 8-round AES. In: FSE. Lecture Notes in Computer Science, vol. 5086, pp. 116–126. Springer (2008)

20.

Derbez P., Fouque P., Jean J.: Improved key recovery attacks on reduced-round AES in the single-key setting. In: EUROCRYPT. Lecture Notes in Computer Science, vol. 7881, pp. 371–387. Springer (2013)

21.

Ferguson N., Kelsey J., Lucks S., Schneier B., Stay M., Wagner D.A., Whiting D.: Improved cryptanalysis of rijndael. In: FSE. Lecture Notes in Computer Science, vol. 1978, pp. 213–230. Springer (2000)

22.

Gilbert H., Peyrin T.: Super-sbox cryptanalysis: Improved attacks for aes-like permutations. In: FSE. Lecture Notes in Computer Science, vol. 6147, pp. 365–383. Springer (2010)

23.

Grover L.K.: A fast quantum mechanical algorithm for database search. In: STOC, pp. 212–219. ACM (1996)

24.

Hosoyamada A., Naya-Plasencia M., Sasaki Y.: Improved attacks on sliscp permutation and tight bound of limited birthday distinguishers. IACR Trans. Symmetric Cryptol. 2020(4), 147–172 (2020).CrossRef

25.

Kaplan M., Leurent G., Leverrier A., Naya-Plasencia M.: Breaking symmetric cryptosystems using quantum period finding. In: CRYPTO (2). Lecture Notes in Computer Science, vol. 9815, pp. 207–237. Springer (2016)

26.

Kaplan M., Leurent G., Leverrier A., Naya-Plasencia M.: Quantum differential and linear cryptanalysis. IACR Trans. Symmetric Cryptol. 2016(1), 71–94 (2016). https://doi.org/10.13154/tosc.v2016.i1.71-94.CrossRef

27.

Kliuchnikov V., Maslov D., Mosca M.: Fast and efficient exact synthesis of single-qubit unitaries generated by clifford and T gates. Quantum Inf. Comput. 13(7–8), 607–630 (2013).MathSciNet

28.

Knudsen L.: Deal-a 128-bit block cipher. Complexity 258(2), 216 (1998).

29.

Kuperberg G.: Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem. In: TQC. LIPIcs, vol. 22, pp. 20–34. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2013)

30.

Liu Q., Zhandry M.: On finding quantum multi-collisions. In: EUROCRYPT (3). Lecture Notes in Computer Science, vol. 11478, pp. 189–218. Springer (2019)

31.

Lu J., Kim J., Keller N., Dunkelman O.: Improving the efficiency of impossible differential cryptanalysis of reduced camellia and MISTY1. In: CT-RSA. Lecture Notes in Computer Science, vol. 4964, pp. 370–386. Springer (2008)

32.

Mala H., Dakhilalian M., Rijmen V., Modarres-Hashemi M.: Improved impossible differential cryptanalysis of 7-round AES-128. In: INDOCRYPT. Lecture Notes in Computer Science, vol. 6498, pp. 282–291. Springer (2010)

33.

Nielsen M.A., Chuang I.: Quantum computation and quantum information. American Association of Physics Teachers (2002)

34.

Sadeghi S., Mohammadi T., Bagheri N.: Cryptanalysis of reduced round SKINNY block cipher. IACR Trans. Symmetric Cryptol. 2018(3), 124–162 (2018). https://doi.org/10.13154/tosc.v2018.i3.124-162.CrossRef

35.

Xie H., Yang L.: Quantum impossible differential and truncated differential cryptanalysis. CoRR (2017) arXiv:1712.06997

36.

Xie H., Yang L.: Using Bernstein–Vazirani algorithm to attack block ciphers. Des. Codes Cryptogr. 87(5), 1161–1182 (2019). https://doi.org/10.1007/s10623-018-0510-5.MathSciNetCrossRef

Titel: Quantum impossible differential attacks: applications to AES and SKINNY
verfasst von: Nicolas David
María Naya-Plasencia
André Schrottenloher
Publikationsdatum: 17.08.2023
Verlag: Springer US
Erschienen in: Designs, Codes and Cryptography / Ausgabe 3/2024
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-023-01280-y

Springer Professional

Quantum impossible differential attacks: applications to AES and SKINNY

Abstract

Premium Partner

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Weitere Artikel der Ausgabe 3/2024

Introducing nega-Forrelation: quantum algorithms in analyzing nega-Hadamard and nega-crosscorrelation spectra

Editorial Note: Coding and Cryptography 2022

New quantum codes from self-dual codes over

On the (in)security of optimized Stern-like signature schemes

Constructing irreducible polynomials recursively with a reverse composition method

Hardness estimates of the code equivalence problem in the rank metric

Premium Partner