A Case Study of Key-Dependent Permutations in Feistel Ciphers

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.





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.