Skip to main content
SpringerLink
Log in

Generalized Feistel networks revisited

  • Published:
Designs, Codes and Cryptography Aims and scope Submit manuscript

Abstract

This work deals with the classification, security and efficiency of generalized Feistel networks (GFNs) with 4 lines. We propose a definition of a GFN, essentially limiting consideration to Feistel-type constructions with domain-preserving F-functions and rotation by one line between rounds. Under this definition, we demonstrate that there are only two non-contracting representatives in the class of 4-line GFNs up to equivalence, namely, the type-I and type-II GFNs that avoid obvious differential effects. We propose to instantiate the GFNs with SPS-functions (two substitution layers separated by a permutation layer) instead of single SP-functions (one substitution-permutation layer only). We prove tight lower bounds on the number of differentially and linearly active functions and S-boxes in such ciphers. We show that the instantiation with SPS-functions using MDS diffusion provides a proportion of differentially and linearly active S-boxes by up to 33 and 50 % higher than that with single SP-functions for type-I and type-II GFNs, respectively, if the same matrix is used in all rounds. Moreover, we present the upper bounds on the differential and the linear hull probability for the type-II GFNs with SPS-functions. This opens up the possibility of designing more efficient block ciphers based on GFN structure.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Aoki K., Ichikawa T., Kanda M., Matsui M., Moriai S., Nakajima J., Tokita T.: Camellia: a 128-bit block cipher suitable for multiple platforms—design and analysis. In: SAC’00. LNCS, vol. 2012, pp. 39–56. Springer, Heidelberg (2001).

  2. Biham E., Dunkelman O.: The SHAvite-3 hash function. Tweaked Version (2009).

  3. Biham E., Biryukov A., Shamir A.: Cryptanalysis of Skipjack reduced to 31 rounds using impossible differentials. In: EUROCRYPT’99. LNCS, vol. 1592, pp. 12–23. Springer, Heidelberg (1999).

  4. Bogdanov A.: On the differential and linear efficiency of balanced Feistel networks. Inf. Process. Lett 110(20), 861–866 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  5. Bogdanov A.: On unbalanced Feistel networks with contracting MDS diffusion. Des. Codes Cryptogr. Special issue: Coding and Cryptography’09 59(1–3), 35–58 (2011)

    MathSciNet  MATH  Google Scholar 

  6. Bogdanov A., Rijmen V.: Zero-correlation linear cryptanalysis of block ciphers (submitted). Available as IACR eprint report 2011/123 (2011).

  7. Bogdanov A., Shibutani K.: Double SP-functions: enhanced generalized feistel networks—extended abstract. In: Parampalli U., Hawkes P. (eds.) Proceedings of the 16th Australasian Conference on Information Security and Privacy, ACISP 2011, Melbourne, Australia, July 11–13, 2011. Lecture Notes in Computer Science, vol. 6812, pp. 106–119. Springer, Heidelberg (2011).

  8. Bogdanov A., Wang M.: Zero correlation linear cryptanalysis with reduced data complexity. In: LNCS. Springer, Heidelberg (2012).

  9. Borst J., Knudsen L.R., Rijmen V.: Two attacks on reduced IDEA. In: EUROCRYPT’97. LNCS, vol. 1233, pp. 1–13. Springer, Heidelberg (1997).

  10. Bouillaguet C., Dunkelman O., Leurent G., Fouque P.A.: Attacks on hash functions based on generalized Feistel—application to reduced-round Lesamnta and SHAvite-3512. Report 2009/634 of Cryptology ePrint Archive (2010).

  11. Bouillaguet C., Dunkelman O., Leurent G., Fouque P.A.: Attacks on hash functions based on generalized Feistel—application to reduced-round Lesamnta and SHAvite-3512. In: SAC’10. LNCS. Springer, Heidelberg (2010).

  12. Burwick C., Coppersmith D., D’Avignon E., Gennaro R., Halevi S., Jutla C., Matyas S.M. Jr., O’Connor L., Safford M.P.D., Zunic N.: MARS—A Candidate Cipher for AES. IBM Corporation (1999).

  13. Choy J., Yap H.: Impossible boomerang attack for block cipher structures. In: IWSEC’09. LNCS, vol. 5824, pp. 22–37. Springer, Heidelberg (2009).

  14. Daemen J., Rijmen V.: The Design of Rijndael: AES—The Advanced Encryption Standard. Springer, Heidelberg (2002)

    MATH  Google Scholar 

  15. Feistel H.: Cryptography and computer privacy. Sci. Am 228, 15–23 (1973)

    Article  Google Scholar 

  16. FIPS: Data Encryption Standard. National Bureau of Standards. U.S. Department of Commerce (1977).

  17. FIPS: Advanced Encryption Standard: Publication 197. National Bureau of Standards, U.S. Department of Commerce (2001).

  18. FIPS: Secure Hash Standard: Publication 180-2. National Bureau of Standards, U.S. Department of Commerce (2002).

  19. Hirose S., Kuwakado H., Yoshida H.: SHA-3 Proposal: Lesamnta. Submission to NIST (2008). http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/Lesamnta.zip.

  20. Hong S., Lee S., Lim J., Sung J., Cheon D.H., Cho I.: Provable security against differential and linear cryptanalysis for the SPN structure. In: Schneier B. (ed.) FSE. Lecture Notes in Computer Science, vol. 1978, pp. 273–283. Springer, Heidelberg (2000).

  21. Hong D., Chang D., Sung J., Lee S., Hong S., Lee J., Moon D., Chee S.: A new dedicated 256-bit hash function: FORK-256. In: Robshaw M.J.B. (ed.) FSE. Lecture Notes in Computer Science, vol. 4047, pp. 195–209. Springer, Heidelberg (2006).

  22. Hong D., Sung J., Hong S., Lim J., Lee S., Koo B., Lee C., Chang D., Lee J., Jeong K., Kim H., Kim J., Chee S.: HIGHT: a new block cipher suitable for low-resource device. In: CHES’06. LNCS, vol. 4249, pp. 46–59. Springer, Heidelberg (2006).

  23. Kanda M., Moriai S., Aoki K., Ueda H., Takashima Y., Ohta K., Matsumoto T.: E2—a new 128-bit block cipher. IEICE Trans. Fundam. E83-A(1), 48–59 (2000).

  24. Kanda M.: Practical security evaluation against differential and linear cryptanalyses for Feistel ciphers with SPN round function. In: SAC’00. LNCS, vol. 2012, pp. 324–338. Springer, Heidelberg (2001).

  25. Kim J., Lee C., Sung J., Hong S., Lee S., Lim J.: Seven new block cipher structures with provable security against differential cryptanalysis. IEICE Trans. 91-A(10), 3047–3058 (2008).

  26. Lu J., Dunkelman O., Keller N., Kim J.: New impossible differential attacks on AES. In: INDOCRYPT’08. LNCS, vol. 5365, pp. 279–293. Springer, Heidelberg (2008).

  27. Minematsu K., Suzaki T., Shigeri M.: On maximum differential probability of generalized feistel. In: Parampalli U., Hawkes P. (eds.) Proceedings of the 16th Australasian Conference on Information Security and Privacy, ACISP 2011, Melbourne, Australia, July 11–13, 2011. Lecture Notes in Computer Science, vol. 6812, pp. 89–105. Springer, Heidelberg (2011).

  28. Moriai S., Vaudenay S.: On the pseudorandomness of top-level schemes of block ciphers. In: ASIACRYPT’00. LNCS, vol. 1976, pp. 289–302. Springer, Heidelberg (2000).

  29. Nyberg K.: Generalized Feistel networks. In: Kim K., Matsumoto T. (eds.) ASIACRYPT. Lecture Notes in Computer Science, vol. 1163, pp. 91–104. Springer, Heidelberg (1996).

  30. Park S., Sung S.H., Chee S., Yoon E.J., Lim J.: On the security of Rijndael-like structures against differential and linear cryptanalysis. In: Zheng Y. (ed.) ASIACRYPT. Lecture Notes in Computer Science, vol. 2501, pp. 176–191. Springer, Heidelberg (2002).

  31. Park S., Sung 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. Lecture Notes in Computer Science, vol. 2887, pp. 247–260. Springer, Heidelberg (2003).

  32. Phan R.C.W.: Impossible differential cryptanalysis of 7-round Advanced Encryption Standard (AES). Inf. Process. Lett 91(1), 33–38 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  33. Rivest R.L.: A description of the RC2(r) encryption algorithm. RFC 2268 (1998).

  34. Rivest R.L., Robshaw M.J.B., Yin Y.L.: RC6 as the AES. In: AES Candidate Conference, pp. 337–342 (2000).

  35. Shibutani K.: On the diffusion of generalized Feistel structures regarding differential and linear cryptanalysis. In: SAC’10. LNCS. Springer, Heidelberg (2010).

  36. Shirai T., Araki K.: On generalized Feistel structures using the diffusion switching mechanism. IEICE Trans. 91-A(8), 2120–2129 (2008).

  37. Shirai T., Preneel B.: On Feistel ciphers using optimal diffusion mappings across multiple rounds. In: ASIACRYPT’04. LNCS, vol. 3329, pp. 1–15. Springer, Heidelberg (2004).

  38. Shirai T., Shibutani K.: Improving immunity of Feistel ciphers against differential cryptanalysis by using multiple MDS matrices. In: FSE’04. LNCS, vol. 3017, pp. 260–278. Springer, Heidelberg (2004).

  39. Shirai T., Shibutani K.: On Feistel structures using a diffusion switching mechanism. In: FSE’06. LNCS, vol. 4047, pp. 41–56. Springer, Heidelberg (2006).

  40. Shirai T., Shibutani K., Akishita T., Moriai S., Iwata T.: The 128-bit blockcipher CLEFIA (extended abstract). In: FSE’07. LNCS, vol. 4593, pp. 181–195. Springer, Heidelberg (2007).

  41. Sung J., Lee S., Lim J.I., Hong S., Park S.: Provable security for the Skipjack-like structure against differential cryptanalysis and linear cryptanalysis. In: ASIACRYPT’00. LNCS, vol. 1976, pp. 274–288. Springer, Heidelberg (2000).

  42. Suzaki T., Minematsu K.: Improving the generalized Feistel. In: FSE’10. LNCS, vol. 6147, pp. 19–39. Springer, Heidelberg (2010).

  43. Tsunoo Y., Tsujihara E., Shigeri M., Saito T., Suzaki T., Kubo H.: Impossible differential cryptanalysis of CLEFIA. In: FSE’08. LNCS, vol. 5086, pp. 398–411. Springer, Heidelberg (2008).

  44. Wang Q., Bogdanov A.: The provable constructive effect of the diffusion switching mechanism for CLEFIA-type block ciphers. Inf. Process. Lett. 112(1–2), 427–432 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  45. Wu W., Zhang W., Lin D.: Security on generalized Feistel scheme with SP round function. Int. J. Netw. Secur. 3(3), 215–224 (2006)

    Google Scholar 

  46. Zheng Y., Matsumoto T., Imai H.: On the construction of block ciphers provably secure and not relying on any unproved hypotheses. In: CRYPTO’89. LNCS, vol. 435, pp. 461–480. Springer, Heidelberg (1989).

Download references

Author information

Authors and Affiliations

  1. Katholieke Universiteit Leuven, ESAT/COSIC and IBBT, Kasteelpark Arenberg 10, 3001, Heverlee, Belgium

    Andrey Bogdanov

  2. Sony Corporation, 1-7-1 Konan, Minato-ku, Tokyo, 108-0075, Japan

    Kyoji Shibutani

Authors
  1. Andrey Bogdanov
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Kyoji Shibutani
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Kyoji Shibutani.

Additional information

This is one of several papers published in Designs, Codes and Cryptography comprising the “Special Issue on Coding and Cryptography”.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bogdanov, A., Shibutani, K. Generalized Feistel networks revisited. Des. Codes Cryptogr. 66, 75–97 (2013). https://doi.org/10.1007/s10623-012-9660-z

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10623-012-9660-z

Keywords

Mathematics Subject Classification

Search

Navigation