Diffusion Analysis of a Scalable Feistel Network

Authors: Subariah Ibrahim, Mohd Aizaini Maarof

Abstract:

A generalization of the concepts of Feistel Networks (FN), known as Extended Feistel Network (EFN) is examined. EFN splits the input blocks into n > 2 sub-blocks. Like conventional FN, EFN consists of a series of rounds whereby at least one sub-block is subjected to an F function. The function plays a key role in the diffusion process due to its completeness property. It is also important to note that in EFN the F-function is the most computationally expensive operation in a round. The aim of this paper is to determine a suitable type of EFN for a scalable cipher. This is done by analyzing the threshold number of rounds for different types of EFN to achieve the completeness property as well as the number of F-function required in the network. The work focuses on EFN-Type I, Type II and Type III only. In the analysis it is found that EFN-Type II and Type III diffuses at the same rate and both are faster than Type-I EFN. Since EFN-Type-II uses less F functions as compared to EFN-Type III, therefore Type II is the most suitable EFN for use in a scalable cipher.

Keywords: Cryptography, Extended Feistel Network, Diffusion Analysis.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1072337

References:

[1] Canda, V. and Trung, T. Scalable Block Ciphers Based on Feistel-Like Structure). Proceedings of Tatracrypt 2001, Tatra Mountains, Mathematica Pub. 25:39-57, 2002.
[2] Biryukov,A. Block Ciphers and Stream Ciphers: The State of the Art. State of the Art in Applied Cryptography, Course on Computer Security and Industrial Cryptogtraphy, LNCS. B.Preneel (Ed.) Springer-Verlag, 2003.
[3] Fibikova, L., Provable Secure Scalable Block Ciphers. PHD Dissertation. University Duisburg - Essen, Germany, 2003.
[4] Rivest, R.L., Robshaw, M.J.B., Sidney, R. and Yin, Y.L., The RC6 Block Cipher. NIST AES, 1998.
[5] Adams, C., Heys, H.M., Tavares, S.E. and Wiener, M. An Analysis of the CAST-256 Cipher. 1999. Available: http://www.engr.mun.ca/ ~howard/PAPERS/cast256.ps.
[6] Burwick, C., Coppersmith, D., D-Avignon, E., Genmaro, R., Halevi, S., Jutla, C., Matyas, S.M., O-Connor, L., Peyravian, M., Safford, D. and Zunic, N. (1999). MARS - A Candidate Cipher for AES. Available: http://www.research.ibm.com/security/mars.pdf
[7] Nakahara, J., Vanderwalle, J. and Preneel, B. Diffusion Analysis of Feistel Networks. Proceedings of 20th Symposium on Information Theory in the Benelux, Hasrode, Belgium. May 27-28. pp. 101-108, 1999.
[8] Kam, J.B. and Davida G.I. Structured Design of Substitution- Permutation Encryption Networks. IEEE Transactions on Computers, Vol. C-28, No. 10, pp. 747-753, 1979.
[9] Moriai S. and Vaudenay, S. Advances in Cryptology ASIACRYPT-00, Kyoto, Japan. LNCS 1976, pp. 289-302. Springer-Verlag, 2000.
[10] Zheng, Y. On the Construction of Block Ciphers Provably Secure and Not Relying on Any Unproved Hypothesis. Advances in Cryptology - In Proceedings of CRYPTO-89 LNCS 435, pp. 461-480. Springer-Verlag, 1989.
[11] Schneier, B. and Kelsey, J. Unbalanced Feistel Networks and Block Cipher Design. In Proceedings of Fast Software Encryption 1996. LNCS 1039, pp. 121-144, Springer-Verlag, 1996.