Abstract
In 2023, Liu et al. summarized the Feistel-like structures which use a single round function, and proposed a unified form of these structures which is named the unified structure. This paper focuses on the classification and cryptanalysis of a particular kind of unified structures which covers the vast majority of known situations and is named regular unified structure. The main results are as follows:
First of all, we give the definition of Affine Equivalence between different structures, present a condition for two regular structures being affine equivalent, and give two normalized forms of a regular unified structure. Surprisingly, we find that a target-heavy generalised Feistel cipher is always affine equivalent to a source-heavy generalised Feistel cipher with the same round function, which shows these two structures always have almost the same cryptographic properties.
Secondly, we give the definition of a Self-Equivalent structure, whose dual structure is affine equivalent to the structure itself. We prove that there is a large portion of the unified structures such as the SM4 and the Mars structures that are among the self-equivalent ones. For these structures, there is a one-to-one correspondence between the impossible differentials and the zero correlation linear hulls, which illustrates that the longest integral of a self-equivalent structure covers at least the rounds of the longest zero correlation linear hull/impossible differential.
At last, we give the definition of the Refined Full-Diffusion Round of a structure, and exploit the \(\epsilon \)-\(\delta \) technique to compute this value, which can be further used to give provable security evaluations of unified structures against impossible differential and zero correlation linear cryptanalysis. For example, we prove that both the longest impossible differential and zero correlation linear hull of the d-branch SM4-like structures cover exactly \(3d-1\) rounds.
Our results could give new guidelines for both the cryptanalysis and the design of Feistel-like ciphers.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Aoki, K., et al.: Camellia: a 128-bit block cipher suitable for multiple platforms — design and analysis. In: Stinson, D.R., Tavares, S. (eds.) Selected Areas in Cryptography, pp. 39–56. Springer, Berlin, Heidelberg (2001). https://doi.org/10.1007/3-540-44983-3_4
Beaulieu, R., Shors, D., Smith, J., Treatman-Clark, S., Weeks, B., Wingers, L.: The SIMON and SPECK families of lightweight block ciphers. IACR Cryptol. ePrint Arch. 2013, 404 (2013). http://eprint.iacr.org/2013/404
Berger, T.P., Minier, M.: Some results using the matrix methods on impossible, integral and zero-correlation distinguishers for Feistel-like ciphers. In: Biryukov, A., Goyal, V. (eds.) Progress in Cryptology – INDOCRYPT 2015: 16th International Conference on Cryptology in India, Bangalore, India, December 6-9, 2015, Proceedings, pp. 180–197. Springer International Publishing, Cham (2015). https://doi.org/10.1007/978-3-319-26617-6_10
Berger, T.P., Minier, M., Thomas, G.: Extended generalized Feistel networks using matrix representation. In: Lange, T., Lauter, K., Lisoněk, P. (eds.) Selected Areas in Cryptography – SAC 2013, pp. 289–305. Springer, Berlin, Heidelberg (2014). https://doi.org/10.1007/978-3-662-43414-7_15
Beyne, T., Liu, Y.: Truncated differential attacks on contracting Feistel ciphers. IACR Trans. Symmetric Cryptol. 2022(2), 141–160 (2022). https://doi.org/10.46586/tosc.v2022.i2.141-160
Biham, E., Biryukov, A., Shamir, A.: Cryptanalysis of skipjack reduced to 31 rounds using impossible differentials. In: Stern, J. (ed.) Advances in Cryptology — EUROCRYPT ’99, pp. 12–23. Springer, Berlin, Heidelberg (1999). https://doi.org/10.1007/3-540-48910-X_2
Blondeau, C., Bogdanov, A., Wang, M.: On the (In)equivalence of impossible differential and zero-correlation distinguishers for Feistel- and Skipjack-type ciphers. In: Boureanu, I., Owesarski, P., Vaudenay, S. (eds.) Applied Cryptography and Network Security: 12th International Conference, ACNS 2014, Lausanne, Switzerland, June 10-13, 2014. Proceedings, pp. 271–288. Springer International Publishing, Cham (2014). https://doi.org/10.1007/978-3-319-07536-5_17
Blondeau, C., Leander, G., Nyberg, K.: Differential-linear cryptanalysis revisited. J. Cryptol. 30(3), 859–888 (2017). https://doi.org/10.1007/s00145-016-9237-5
Blondeau, C., Nyberg, K.: New links between differential and linear cryptanalysis. In: Johansson, T., Nguyen, P.Q. (eds.) Advances in Cryptology – EUROCRYPT 2013: 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, May 26-30, 2013. Proceedings, pp. 388–404. Springer, Berlin, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38348-9_24
Blondeau, C., Nyberg, K.: Links between truncated differential and multidimensional linear properties of block ciphers and underlying attack complexities. In: Nguyen, P.Q., Oswald, E. (eds.) Advances in Cryptology – EUROCRYPT 2014, pp. 165–182. Springer, Berlin, Heidelberg (2014). https://doi.org/10.1007/978-3-642-55220-5_10
Bogdanov, A., Leander, G., Nyberg, K., Wang, M.: Integral and multidimensional linear distinguishers with correlation zero. In: Wang, X., Sako, K. (eds.) Advances in Cryptology – ASIACRYPT 2012, pp. 244–261. Springer, Berlin, Heidelberg (2012). https://doi.org/10.1007/978-3-642-34961-4_16
Bogdanov, A., Rijmen, V.: Linear hulls with correlation zero and linear cryptanalysis of block ciphers. Des. Codes Cryptogr. 70(3), 369–383 (2014). https://doi.org/10.1007/s10623-012-9697-z
Carlet, C.: Boolean functions for cryptography and error correcting codes. Boolean Methods and Models (2006)
Cauchois, V., Gomez, C., Thomas, G.: General Diffusion Analysis: how to find optimal permutations for generalized Type-II Feistel schemes. IACR Trans. Symmetric Cryptol. 2019(1), 264–301 (2019). https://doi.org/10.13154/tosc.v2019.i1.264-301
Chabaud, F., Vaudenay, S.: Links between differential and linear cryptanalysis. In: De Santis, A. (ed.) Advances in Cryptology — EUROCRYPT’94, pp. 356–365. Springer, Berlin, Heidelberg (1995). https://doi.org/10.1007/BFb0053450
Cid, C., Hosoyamada, A., Liu, Y., Sim, S.M.: Quantum cryptanalysis on contracting Feistel structures and observation on related-key settings. In: Bhargavan, K., Oswald, E., Prabhakaran, M. (eds.) Progress in Cryptology – INDOCRYPT 2020: 21st International Conference on Cryptology in India, Bangalore, India, December 13–16, 2020, Proceedings, pp. 373–394. Springer International Publishing, Cham (2020). https://doi.org/10.1007/978-3-030-65277-7_17
Daemen, J., Rijmen, V.: The Design of Rijndael: AES - The Advanced Encryption Standard. Information Security and Cryptography, Springer (2002). https://doi.org/10.1007/978-3-662-04722-4
Demirci, H., Selçuk, A.A.: A meet-in-the-middle attack on 8-Round AES. In: Nyberg, K. (ed.) Fast Software Encryption, pp. 116–126. Springer, Berlin, Heidelberg (2008). https://doi.org/10.1007/978-3-540-71039-4_7
Diffie, W., Ledin, G.: SMS4 encryption algorithm for wireless networks. IACR Cryptol. ePrint Arch., 329 (2008). http://eprint.iacr.org/2008/329
Guo, J., Jean, J., Nikolic, I., Sasaki, Y.: Meet-in-the-middle attacks on classes of contracting and expanding Feistel constructions. IACR Trans. Symmetric Cryptol. 2016(2), 307–337 (2016). https://doi.org/10.13154/tosc.v2016.i2.307-337
Hao, Y., Leander, G., Meier, W., Todo, Y., Wang, Q.: Modeling for three-subset division property without unknown subset. J. Cryptol. 34(3), 22 (2021). https://doi.org/10.1007/s00145-021-09383-2
Hu, K., Sun, S., Wang, M., Wang, Q.: An algebraic formulation of the division property: revisiting degree evaluations, cube attacks, and key-independent sums. In: Moriai, S., Wang, H. (eds.) Advances in Cryptology – ASIACRYPT 2020: 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, December 7–11, 2020, Proceedings, Part I, pp. 446–476. Springer International Publishing, Cham (2020). https://doi.org/10.1007/978-3-030-64837-4_15
Kwon, D., et al.: New Block Cipher: ARIA. In: Lim, J.-I., Lee, D.-H. (eds.) ICISC 2003. LNCS, vol. 2971, pp. 432–445. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24691-6_32
Lai, X., Massey, J.L.: A proposal for a new block encryption standard. In: Damgård, I.B. (ed.) Advances in Cryptology — EUROCRYPT ’90, pp. 389–404. Springer, Berlin, Heidelberg (1991). https://doi.org/10.1007/3-540-46877-3_35
Leander, G.: On linear hulls, statistical saturation attacks, PRESENT and a cryptanalysis of PUFFIN. In: Paterson, K.G. (ed.) Advances in Cryptology – EUROCRYPT 2011, pp. 303–322. Springer, Berlin, Heidelberg (2011). https://doi.org/10.1007/978-3-642-20465-4_18
Liu, J., et al.: New wine old bottles: Feistel structure revised. IEEE Trans. Inf. Theory 69(3), 2000–2008 (2023). https://doi.org/10.1109/TIT.2022.3223139
Schneier, B., Kelsey, J.: Unbalanced Feistel networks and block cipher design. In: Gollmann, D. (ed.) Fast Software Encryption, pp. 121–144. Springer, Berlin, Heidelberg (1996). https://doi.org/10.1007/3-540-60865-6_49
Sun, B.: Provable security evaluation of block ciphers against Demirci-Selçuk’s meet-in-the-middle attack. IEEE Trans. Inf. Theory 67(7), 4838–4844 (2021). https://doi.org/10.1109/TIT.2021.3058377
Sun, B., Li, R., Qu, L., Li, C.: SQUARE attack on block ciphers with low algebraic degree. Sci. China Inf. Sci. 53(10), 1988–1995 (2010). https://doi.org/10.1007/s11432-010-4061-2
Sun, B., Liu, M., Guo, J., Rijmen, V., Li, R.: Provable security evaluation of structures against impossible differential and zero correlation linear cryptanalysis. In: Fischlin, M., Coron, J.-S. (eds.) Advances in Cryptology – EUROCRYPT 2016: 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part I, pp. 196–213. Springer, Berlin, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49890-3_8
Sun, B., et al.: Links among impossible differential, integral and zero correlation linear cryptanalysis. In: Gennaro, R., Robshaw, M. (eds.) Advances in Cryptology – CRYPTO 2015: 35th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2015, Proceedings, Part I, pp. 95–115. Springer, Berlin, Heidelberg (2015). https://doi.org/10.1007/978-3-662-47989-6_5
Suzaki, T., Minematsu, K.: Improving the generalized Feistel. In: Hong, S., Iwata, T. (eds.) Fast Software Encryption, pp. 19–39. Springer, Berlin, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13858-4_2
Todo, Y.: Structural evaluation by generalized integral property. In: Oswald, E., Fischlin, M. (eds.) Advances in Cryptology – EUROCRYPT 2015: 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April 26-30, 2015, Proceedings, Part I, pp. 287–314. Springer, Berlin, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46800-5_12
Vaudenay, S.: On the Lai-Massey scheme. In: Lam, K.-Y., Okamoto, E., Xing, C. (eds.) Advances in Cryptology - ASIACRYPT’99, pp. 8–19. Springer, Berlin, Heidelberg (1999). https://doi.org/10.1007/978-3-540-48000-6_2
Yanagihara, S., Iwata, T.: On permutation layer of type 1, source-heavy, and target-heavy generalized Feistel structures. In: Lin, D., Tsudik, G., Wang, X. (eds.) Cryptology and Network Security, pp. 98–117. Springer, Berlin, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25513-7_8
Yanagihara, S., Iwata, T.: Improving the permutation layer of type 1, type 3, source-heavy, and target-heavy generalized Feistel structures. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 96-A(1), 2–14 (2013). https://doi.org/10.1587/transfun.E96.A.2
Acknowledgement
The authors would like to express our sincere gratitude to the anonymous reviewers for their useful comments and suggestions, and to Zhenzhen Bao for her shepherding. This work is supported by the National Natural Science Foundation of China (No: U2336209, 62272147, 62272470, 62072466, 62002370, 62201585), Science and Technology on Communication Security Laboratory Foundation (No: 6142103012207), the Innovation Group Project of the Natural Science Foundation of Hubei Province of China (No: 2023AFA021), and the Innovation Program for Quantum Science and Technology (No: 2021ZD0302902).
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 International Association for Cryptologic Research
About this paper
Cite this paper
Sun, B. et al. (2024). Feistel-Like Structures Revisited: Classification and Cryptanalysis. In: Reyzin, L., Stebila, D. (eds) Advances in Cryptology – CRYPTO 2024. CRYPTO 2024. Lecture Notes in Computer Science, vol 14923. Springer, Cham. https://doi.org/10.1007/978-3-031-68385-5_9
Download citation
DOI: https://doi.org/10.1007/978-3-031-68385-5_9
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-68384-8
Online ISBN: 978-3-031-68385-5
eBook Packages: Computer ScienceComputer Science (R0)
