Cryptographic properties and application of a generalized unbalanced Feistel network structure. (English) Zbl 1307.94048

Boyd, Colin (ed.) et al., Information security and privacy. 14th Australasian conference, ACISP 2009, Brisbane, Australia, July 1–3, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-02619-5/pbk). Lecture Notes in Computer Science 5594, 73-89 (2009).
Summary: In this paper, we study GF-NLFSR, a Generalized Unbalanced Feistel Network (GUFN) which can be considered as an extension of the outer function FO of the KASUMI block cipher. We prove upper bounds for the differential and linear hull probabilities for any \(n+1\) rounds of an \(n\)-cell GF-NLFSR. Besides analyzing security against differential and linear cryptanalysis, we provide a frequency distribution for upper bounds on the true differential and linear hull probabilities. We also demonstrate a \((2n-1)\)-round impossible differential distinguisher and a \((3n-1)\)-round integral attack distinguisher on the \(n\)-cell GF-NLFSR. As an application, we design a new block cipher Four-Cell based on a 4-cell GF-NLFSR. We prove the security of Four-Cell against differential, linear, and boomerang attack. Based on the 7-round impossible differential and 11-round integral attack distinguisher, we set the number of rounds of Four-Cell to be 25 for protection against these attacks. Furthermore, Four-Cell can be shown to be secure against other attacks such as higher order differential attack, cube attack, interpolation attack, XSL attack and slide attack.
For the entire collection see [Zbl 1165.94302].


94A60 Cryptography


CLEFIA; Square
Full Text: DOI


[1] Biham, E., Shamir, A.: Differential Cryptanalysis of the Data Encryption Standard. Springer, New York (1993) · Zbl 0778.94005 · doi:10.1007/978-1-4613-9314-6
[2] Biryukov, A., Wagner, D.: Slide Attack. In: Knudsen, L.R. (ed.) FSE 1999. LNCS, vol. 1636, pp. 245–259. Springer, Heidelberg (1999) · Zbl 0942.94020 · doi:10.1007/3-540-48519-8_18
[3] Cid, C., Leurent, G.: An Analysis of the XSL Algorithm. In: Roy, B. (ed.) ASIACRYPT 2005. LNCS, vol. 3788, pp. 333–352. Springer, Heidelberg (2005) · Zbl 1154.94384 · doi:10.1007/11593447_18
[4] Courtois, N., Pieprzyk, J.: Cryptanalysis of Block Ciphers with Overdefined Systems of Equations. IACR eprint server 2002/044 (March 2002), http://www.iacr.org · Zbl 1065.94543
[5] Courtois, N., Pieprzyk, J.: Cryptanalysis of Block Ciphers with Overdefined Systems of Equations. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 267–287. Springer, Heidelberg (2002) · Zbl 1065.94543 · doi:10.1007/3-540-36178-2_17
[6] Daemen, J., Rijmen, V.: The Design of Rijndael: AES, The Advanced Encryption Standard. Springer, Heidelberg (2002) · Zbl 1065.94005 · doi:10.1007/978-3-662-04722-4
[7] Dinur, I., Shamir, A.: Cube Attacks on Tweakable Black Box Polynomials, Cryptology Eprint Archive, Report 2008/385 · Zbl 1239.94045
[8] Jakobsen, T., Knudsen, L.R.: Attacks on Block ciphers of Low Algebraic Degree. Journal of Cryptology 14, 197–210 (2001) · Zbl 0976.94021 · doi:10.1007/s00145-001-0003-x
[9] Knudsen, L.R., Wagner, D.: Integral Cryptanalysis. In: Daemen, J., Rijmen, V. (eds.) FSE 2002. LNCS, vol. 2365, pp. 112–127. Springer, Heidelberg (2002) · Zbl 1045.94527 · doi:10.1007/3-540-45661-9_9
[10] Lai, X.: On the Design and Security of Block Ciphers, Thesis (1992)
[11] Lai, X., Massey, J.L., Murphy, S.: Markov Ciphers and Differential Cryptanalysis. In: Davies, D.W. (ed.) EUROCRYPT 1991. LNCS, vol. 547, pp. 17–38. Springer, Heidelberg (1991) · Zbl 0777.94013 · doi:10.1007/3-540-46416-6_2
[12] Lim, C.W., Khoo, K.: An Analysis of XSL Applied on BES. In: Biryukov, A. (ed.) FSE 2007. LNCS, vol. 4593, pp. 242–253. Springer, Heidelberg (2007) · Zbl 1186.94459 · doi:10.1007/978-3-540-74619-5_16
[13] Liu, F., Ji, W., Hu, L., Ding, J., Lv, S., Pyshkin, A., Weinmann, R.: Analysis of the SMS4 Block Cipher. In: Pieprzyk, J., Ghodosi, H., Dawson, E. (eds.) ACISP 2007. LNCS, vol. 4586, pp. 158–170. Springer, Heidelberg (2007) · Zbl 1213.94121 · doi:10.1007/978-3-540-73458-1_13
[14] Matsui, M.: Linear Cryptanalysis Method for DES Cipher. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 386–397. Springer, Heidelberg (1994) · Zbl 0951.94519 · doi:10.1007/3-540-48285-7_33
[15] Matsui, M.: New Structure of Block Ciphers with Provable Security Against Differential and Linear Cryptanalysis. In: Gollmann, D. (ed.) FSE 1996. LNCS, vol. 1039, pp. 205–218. Springer, Heidelberg (1996) · Zbl 1373.94925 · doi:10.1007/3-540-60865-6_54
[16] Murphy, S., Robshaw, M.: Essential Algebraic Structure within the AES. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 1–16. Springer, Heidelberg (2002) · Zbl 1026.94537 · doi:10.1007/3-540-45708-9_1
[17] Nyberg, K.: Linear Approximation of Block Ciphers. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 439–444. Springer, Heidelberg (1995) · Zbl 0885.94023 · doi:10.1007/BFb0053460
[18] Nyberg, K.: Generalized Feistel Networks. In: Kim, K.-c., Matsumoto, T. (eds.) ASIACRYPT 1996. LNCS, vol. 1163, pp. 91–104. Springer, Heidelberg (1996) · Zbl 1004.94531 · doi:10.1007/BFb0034838
[19] Park, S., Sang, S.H., Lee, S., Lim, J.: Improving the Upper Bound on the Maximum Differential and the Maximum Linear Hull Probability for SPN Structures and AES. In: Johansson, T. (ed.) FSE 2003. LNCS, vol. 2887, pp. 247–260. Springer, Heidelberg (2003) · Zbl 1254.94040 · doi:10.1007/978-3-540-39887-5_19
[20] Schneier, B., Kelsey, J.: Unbalanced Feistel Networks and Block-Cipher Design. In: Gollmann, D. (ed.) FSE 1996. LNCS, vol. 1039, pp. 121–144. Springer, Heidelberg (1996) · Zbl 1373.94930 · doi:10.1007/3-540-60865-6_49
[21] Shirai, T., Shibutani, K., Akishita, T., Moriai, S., Iwata, T.: The 128-bit Blockcipher CLEFIA (Extended Abstract). In: Biryukov, A. (ed.) FSE 2007. LNCS, vol. 4593, pp. 181–195. Springer, Heidelberg (2007) · Zbl 1186.94471 · doi:10.1007/978-3-540-74619-5_12
[22] Daemen, J., Knudsen, L., Rijmen, V.: The Block Cipher Square. In: Biham, E. (ed.) FSE 1997. LNCS, vol. 1267, pp. 149–165. Springer, Heidelberg (1997) · Zbl 1385.94025 · doi:10.1007/BFb0052343
[23] Wagner, D.: The Boomerang Attack. In: Knudsen, L.R. (ed.) FSE 1999. LNCS, vol. 1636, pp. 156–170. Springer, Heidelberg (1999) · Zbl 0942.94022 · doi:10.1007/3-540-48519-8_12
[24] Wallen, J.: Design Principles of the KASUMI Block Cipher (June 2008), http://www.tml.tkk.fi/Opinnot/Tik-110.501/2000/papers/wallen.pdf
[25] Wu, W., Zhang, W., Lin, D.: On the Security of Generalized Feistel Scheme with SP Round Function. International Journal of Network Security 3(3), 215–224 (2006)
[26] Kim, J., Hong, S., Sung, J., Lee, S., Lim, J., Sung, S.: Impossible Differential Cryptanalysis for Block Cipher Structures. In: Johansson, T., Maitra, S. (eds.) INDOCRYPT 2003. LNCS, vol. 2904, pp. 82–96. Springer, Heidelberg (2003) · Zbl 1123.94352 · doi:10.1007/978-3-540-24582-7_6
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.