A Case Study of Key-Dependent Permutations in Feistel Ciphers

Authors: Hani Almimi, Ola Osabi, Azman Samsudin

Abstract:

Many attempts have been made to strengthen Feistel based block ciphers. Among the successful proposals is the key- dependent S-box which was implemented in some of the high-profile ciphers. In this paper a key-dependent permutation box is proposed and implemented on DES as a case study. The new modified DES, MDES, was tested against Diehard Tests, avalanche test, and performance test. The results showed that in general MDES is more resistible to attacks than DES with negligible overhead. Therefore, it is believed that the proposed key-dependent permutation should be considered as a valuable primitive that can help strengthen the security of Substitution-Permutation Network which is a core design in many Feistel based block ciphers.

Keywords: Block Cipher, Feistel Structure, DES, Diehard Tests, Avalanche Effect.

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

References:

[1] W. Stallings, Cryptography and Network Security Principles and Practices. Prentice Hall, 2006.
[2] A. Menezes, P. Van Oorschot, and S. Vanstone, The Handbook of Applied Cryptography. CRC Press, Inc., 1996.
[3] B. Schneier, Applied Cryptography, Second Edition: Protocols, Algorthms, and Source Code in C. John Wiley & Sons, Inc., 1996.
[4] R. Zhang and L. Chen, "A Block Cipher Using Key-Dependent S-box and P-boxes," in IEEE International Symposium on Industrial Electronics, ISIE 2008, pp. 1463 - 1468.
[5] The Florida State University, The Marsaglia Random Number CDROM including the Diehard Battery of Tests of Randomness. (Online). http://www.stat.fsu.edu/pub/diehard/
[6] V. Katos, "A Randomness Test for Block Ciphers," Applied Mathematics and Computation, Vol. 162, p. 29–35, 2005.
[7] M. E. Yalcin, J. A. K. Suykens, and J. Vandewalle, "A Double Scroll Based True Random Bit Generator," in Proc. IEEE Int. Symp. Circuits and Systems (ISCAS’04), Vancouver, BC, Canada, 2004, p. 581–584.
[8] I. Jang and H. S. Yoo, "Pseudorandom Number Generator Using Optimal Normal Basis," in Proc. International Conference on Computational Science and its Applications, Glasgow, Royaume-uni, 2006, vol. 3984, pp. 206-212.
[9] D. Bucerzan, "A Cryptographic Algorithm Based on a Pseudorandom Number Generator," in 10th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, 2008, pp. 453-456.
[10] P. Hellekalek, and S. Wegekittl, "Empirical Evidence Concerning AES," ACM Transactions on Modeling and Computer Simulation, vol. 13, p. 322–333, 2003.
[11] J. Soto, "Statistical Testing of Random Number Generators," in Proceedings of the 22nd National Information Systems Security Conference, Virginia - USA, 2000.
[12] X. Zhangy, K. Tangy and L. Shuz, "A Chaotic Cipher Mmohocc and Its Randomness Evaluation," in International Conference on Complex Systems (ICCS2006), Boston, 2006
[not published].
[13] K. M. A. Suwais, "Parallel Platform For New Secure Stream Ciphers Based On NP-HARD Problems”, Phd thesis, Uinversity Sains Malaysia, 2009.
[14] S. H. Lee, H. Y. Jeong and Y. S. Lee, "Application-Adaptive Pseudo Random Number Generators and Binding Selector," in The 23rd International Technical Conference on Circuits/Systems, Computers and Communications, Shimonoseki - Japan, 2008, pp. 1561 - 1564.
[15] F. Pareschi, R. Rovatti and G. Setti, "Second-level NIST Randomness Tests for Improving Test Reliability," in IEEE International Symposium on Circuits and Systems, NewOrleans, 2007, pp. 1437-1440.
[16] "FIPS 140-1 Non-Proprietary Cryptographic Module Security Policy," 2000. http://csrc.nist.gov/groups/STM/cmvp/documents/140- 1/140sp/140sp111.pdf. visited in October, 2009.
[17] I. Vattulainen, T. Ala-Nissila and K. Kankaala, "Physical Tests for Random Numbers in Simulations," Phys. Rev. Lett. 73, 19, 2513–2516. 1994.
[18] K. H. Tsoi, K. H. Leung and P. H. W. Leong, "High Performance Physical Random Number Generator," IET computers & digital techniques, pp. 349-352, 2007.
[19] K. H. Yalcin, J. A. K. Suykens and J. Vandewalle, "True Random Bit Generation From a Double-Scroll Attractor," in IEEE Transactions on Circuits and Systems I, 2004, pp. 1395 - 1404.
[20] F. A. Feldman, "A New Spectral Test for Nonrandomness and the DES," in IEEE Transactions on Software Engineering, 1990, pp. 261 - 267.
[21] A. G. Konheim, Crytography: A Primer. Wiley Interscience, 1981.