nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

Quantum Cryptanalysis on Contracting Feistel Structures and Observation on Related-Key Settings

verfasst von : Carlos Cid, Akinori Hosoyamada, Yunwen Liu, Siang Meng Sim

Erschienen in: Progress in Cryptology – INDOCRYPT 2020

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

In this paper we show several quantum chosen-plaintext attacks (qCPAs) on contracting Feistel structures. In the classical setting, a d-branch r-round contracting Feistel structure can be shown to be PRP-secure when d is even and \(r \ge 2d-1\), meaning it is secure against polynomial-time chosen-plaintext attacks. We propose a polynomial-time qCPA distinguisher on the d-branch \((2d-1)\)-round contracting Feistel structure, which solves an open problem by Dong et al. In addition, we show a polynomial-time qCPA that recovers the keys of the d-branch r-round contracting Feistel structure when each round function \(F^{(i)}_{k_i}\) has the form \(F^{(i)}_{k_i}(x) = F_i(x \oplus k_i)\) for a public random function \(F_i\). This is applicable to the Chinese block cipher standard SM4, which is a special case where \(d=4\). Finally, in addition to quantum attacks under single-key setting, we also show related-key quantum attacks on balanced Feistel structures in the model that adversaries can only control part of the key difference in quantum superposition. Our related-key attacks on balanced Feistel structures can easily be extended to ones on contracting Feistel structures.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Computing Expected Differential Probability of (Truncated) Differentials and Expected Linear Potential of (Multidimensional) Linear Hulls in SPN Block Ciphers

Nächstes Kapitel Evaluation of Quantum Cryptanalysis on SPECK

Feistel structures divide internal states into some words and update the states iteratively by applying word-wise operations. Each word is referred to as a branch and depicted as a single wire in the figures.

In this work, we adopt the Feistel structure notation used in [14].

A keyed permutation is said to be a secure PRP (resp., SPRP) if it cannot be distinguished from a random permutation by polynomial-time chosen-plaintext attacks (CPAs) (resp., chosen-ciphertext attacks (CCAs)).

We note that a previous work [3] has shown a quantum attack on a contracting Feistel structure (GMiMC-crf), but the attack only works when all the round keys are identical.

A previous work (Sect. 6.1 of [4]) does study a related-key attack in the quantum setting where an adversary can choose only a part of the differences on the key. However that attack does not make superposition queries to keyed oracles.

Here, n denotes the branch size and the round key size.

We can use any constant p such that \(0< p < 1\) as the threshold instead of 1/2. We use the value 1/2 just for convenience.

The set of multiple periods of f forms a linear space because, if s and \(s'\) are periods of f, \(s \oplus s'\) is also a period of f.

If f has multiple periods, we have to consider a generalization of (2’). See Section A.3 of this paper’s full version for details.

It is desirable to show that the conjecture holds, but proving quantum query lower bounds is quite difficult when quantum queries are made to both of E and \(E^{-1}\).

The previous polynomial-time qCPA on 3-round Feistel-KF structure [7] recovers the keys without nested Simon’s algorithm.

To be more precise, we have to simulate \(\mathcal {O}^7_A\) (truncation) by using \(\mathcal {O}^7\). This can be done by using the technique explained in Remark 1.

Here, we assume it to be the same public function for all rounds. In fact, every round can be an arbitrary public function and the attack still works.

To be more precise, the conditions become equivalent with an overwhelming probability when the round function F is a random function.

Aoki, K., et al.: Camellia: A 128-bit block cipher suitable for multiple platforms—design and analysis. In: Stinson, D.R., Tavares, S. (eds.) SAC 2000. LNCS, vol. 2012, pp. 39–56. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44983-3_4CrossRef

Biryukov, A., Wagner, D.: Advanced slide attacks. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 589–606. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-45539-6_41CrossRef

Bonnetain, X.: Collisions on Feistel-MiMC and univariate GMiMC. IACR Cryptol. ePrint Arch. 2019, 951 (2019)

Bonnetain, X., Hosoyamada, A., Naya-Plasencia, M., Sasaki, Yu., Schrottenloher, A.: Quantum attacks without superposition queries: the offline Simon’s algorithm. In: Galbraith, S.D., Moriai, S. (eds.) ASIACRYPT 2019. LNCS, vol. 11921, pp. 552–583. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-34578-5_20CrossRef

Bonnetain, X., Naya-Plasencia, M., Schrottenloher, A.: On quantum slide attacks. In: Paterson, K.G., Stebila, D. (eds.) SAC 2019. LNCS, vol. 11959, pp. 492–519. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-38471-5_20CrossRef

Cid, C., Hosoyamada, A., Liu, Y., Sim, S.M.: Quantum cryptanalysis on contracting Feistel structures and observation on related-key settings. IACR Cryptol. ePrint Arch. 2020, 959 (2020)

Daiza, T., Kurosawa, K.: Quantum/classical key recovery attack on 3-round Feistel-KF structure (2020), unpublished manuscript

Diffie, W., Ledin, G.: SMS4 encryption algorithm for wireless networks. IACR Cryptology ePrint Archive 2008, vol. 329 (2008). http://eprint.iacr.org/2008/329

Dong, X., Li, Z., Wang, X.: Quantum cryptanalysis on some generalized Feistel schemes. Sci. China Inf. Sci. 62(2), 22501:1–22501:12 (2019)MathSciNetCrossRef

10.

Dong, X., Wang, X.: Quantum key-recovery attack on Feistel structures. Sci. China Inf. Sci. 61(10), 102501:1–102501:7 (2018)CrossRef

11.

Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22–24, 1996, pp. 212–219 (1996)

12.

Hodžić, S., Knudsen Ramkilde, L., Brasen Kidmose, A.: On quantum distinguishers for type-3 generalized Feistel network based on separability. In: Ding, J., Tillich, J.-P. (eds.) PQCrypto 2020. LNCS, vol. 12100, pp. 461–480. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-44223-1_25CrossRef

13.

Hosoyamada, A., Sasaki, Yu.: Quantum demiric-selçuk meet-in-the-middle attacks: applications to 6-round generic Feistel constructions. In: Catalano, D., De Prisco, R. (eds.) SCN 2018. LNCS, vol. 11035, pp. 386–403. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-98113-0_21CrossRef

14.

Ito, G., Hosoyamada, A., Matsumoto, R., Sasaki, Yu., Iwata, T.: Quantum chosen-ciphertext attacks against Feistel ciphers. In: Matsui, M. (ed.) CT-RSA 2019. LNCS, vol. 11405, pp. 391–411. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-12612-4_20CrossRef

15.

Kaplan, M., Leurent, G., Leverrier, A., Naya-Plasencia, M.: Breaking symmetric cryptosystems using quantum period finding. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9815, pp. 207–237. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53008-5_8CrossRef

16.

Kuwakado, H., Morii, M.: Quantum distinguisher between the 3-round Feistel cipher and the random permutation. In: ISIT 2010, Proceedings, pp. 2682–2685. IEEE (2010)

17.

Kuwakado, H., Morii, M.: Security on the quantum-type even-Mansour cipher. In: ISITA 2012, pp. 312–316. IEEE (2012)

18.

Leander, G., May, A.: Grover meets Simon – quantumly attacking the FX-construction. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. LNCS, vol. 10625, pp. 161–178. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70697-9_6CrossRef

19.

Luby, M., Rackoff, C.: How to construct pseudo-random permutations from pseudo-random functions. In: Williams, H.C. (ed.) CRYPTO 1985. LNCS, vol. 218, pp. 447–447. Springer, Heidelberg (1986). https://doi.org/10.1007/3-540-39799-X_34CrossRef

20.

National Bureau of Standards: Data encryption standard. FIPS 46, January 1977

21.

Ni, B., Ito, G., Dong, X., Iwata, T.: Quantum attacks against type-1 generalized Feistel ciphers and applications to CAST-256. In: Hao, F., Ruj, S., Sen Gupta, S. (eds.) INDOCRYPT 2019. LNCS, vol. 11898, pp. 433–455. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-35423-7_22CrossRef

22.

NIST: Announcing request for nominations for public-key post-quantum cryptographic algorithms. National Institute of Standards and Technology (2016)

23.

Rötteler, M., Steinwandt, R.: A note on quantum related-key attacks. Inf. Process. Lett. 115(1), 40–44 (2015)CrossRef

24.

Simon, D.R.: On the power of quantum computation. In: 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, 20–22 November 1994, pp. 116–123 (1994)

25.

Zhang, L.T., Wu, W.L.: Pseudorandomness and super pseudorandomness on the unbalanced feistel networks with contracting functions. China J. Comput., 32(7), 1320–1330 (2009). http://cjc.ict.ac.cn/eng/qwjse/view.asp?id=2909

Titel: Quantum Cryptanalysis on Contracting Feistel Structures and Observation on Related-Key Settings
verfasst von: Carlos Cid
Akinori Hosoyamada
Yunwen Liu
Siang Meng Sim
Verlag: Springer International Publishing
Buch: Progress in Cryptology – INDOCRYPT 2020
Print ISBN: 978-3-030-65276-0

Electronic ISBN: 978-3-030-65277-7

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-65277-7_17

Springer Professional

Abstract

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

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner