Document Type : Research Article

Authors

1 Department of Electrical Engineering, Khorasgan (Isfahan) Branch, Islamic Azad University, Isfahan, Iran.

2 Faculty of Information Technology, Monash University, Melbourne, Australia.

Abstract

In terms of security, MDS matrices are one of the best choices for diffusion layer of block ciphers. However, as these matrices grow in size, their software implementation becomes a challenge. In this paper, to benefit from the properties of MDS matrices and avoid the mentioned challenge, we use 4*4 MDS matrices to build some 16*16 matrices with low number of zero elements. We show that if these matrices are used as diffusion layer of software-based SPN structures, the resulting block ciphers have similar properties as AES in software implementation complexity (i.e. the number of required CPU instructions) and resistance against linear and differential attacks. Moreover, the best impossible differential and square distinguishers for the proposed 16*16 structures have similar length as SPN structures with 16*16 MDS matrices. Thus, the new structures outperform AES with respect to the impossible differential and square attacks. Additionally, we show that if the proposed SPN structure uses the AES key schedule, its results for the differential related-key attacks are better than those for AES. We also extend the idea and use 4*4 MDS matrices to design 24*24 and 32*32 matrices with acceptable properties for SPN structure design. Finally, we extend the idea to propose some matrices for Feistel structures with SP-type F-functions. We show that the resulting structures are more secure than the improved type-II GFS.

Keywords

[1] C. Shannon. Communication theory of secrecy systems. Bell System Technical Journals,28(4):656–715, 1949.
[2] Lawrence Bassham, C ̧ a ̆gda ̧s C ̧ alık, Kerry McKay, and Meltem S ̈onmez Turan. Submission requirements and evaluation criteria for the lightweight cryptography standardization process. US National Institute of Standards and Technology, 2018.
[3] Joan Daemen and Vincent Rijmen. The design of Rijndael, volume 2. Springer, 2002.
[4] Kaisa Nyberg. Generalized feistel networks. In International conference on the theory and application of cryptology and information security, pages 91–104. Springer, 1996.
[5] Yuliang Zheng, Tsutomu Matsumoto, and Hideki Imai. On the construction of block ciphers provably secure and not relying on any unproved hypotheses. In Conference on the Theory and Application of Cryptology, pages 461–480. Springer, 1989.
[6] T. Shirai and K. Shibutani. Improving immunity of feistel ciphers against differential cryptanalysis by using multiple MDS matrices. In FSE 2004, volume 3017, pages 260–278. Springer-Verlag, 2004.
[7] Taizo Shirai and Kyoji Shibutani. On feistel structures using a diffusion switching mechanism. In International Workshop on Fast Software Encryption, pages 41–56. Springer, 2006.
[8] T. Shirai and K. Araki. On generalized feistel structures using the diffusion switching mechanism. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E91-A(8):2120–2129, 2008.
[9] Yukiyasu Tsunoo, Etsuko Tsujihara, Maki Shigeri, Teruo Saito, Tomoyasu Suzaki, and Hiroyasu Kubo. Impossible differential cryptanalysis of CLEFIA. In International Workshop on Fast Software Encryption, pages 398–411.
Springer, 2008.
[10] K. Shibutani. On the diffusion of generalized feistel structures regarding differential and linear cryptanalysis. In SAC 2010, volume 6544, pages 211–228. Springer-Verlag, 2011.
[11] Taizo Shirai, Kyoji Shibutani, Toru Akishita, Shiho Moriai, and Tetsu Iwata. The 128-bit blockcipher CLEFIA. In International workshop on fast software encryption, pages 181–195. Springer, 2007.
[12] Mahdi Sajadieh, Arash Mirzaei, Hamid Mala, and Vincent Rijmen. A new counting method to bound the number of active s-boxes in Rijndael and 3D. Designs, Codes and Cryptography, 83(2):327–343, 2017.
[13] Mahdi Sajadieh, Mohammad Dakhilalian, Hamid Mala, and Pouyan Sepehrdad. Efficient recursive diffusion layers for block ciphers and hash functions. Journal of Cryptology, 28(2):240–256, 2015.
[14] Serge Vaudenay. On the need for multipermutations: Cryptanalysis of MD4 and SAFER. In International Workshop on Fast Software Encryption, pages 286–297. Springer, 1994.
[15] Hamid Mala, Mohammad Dakhilalian, Vincent Rijmen, and Mahmoud Modarres-Hashemi. Improved impossible differential cryptanalysis of 7-round AES-128. In International Conference on Cryptology in India, pages 282–291. Springer, 2010.
[16] Joan Daemen, Lars Knudsen, and Vincent Rijmen. The block cipher Square. In International Workshop on Fast Software Encryption, pages 149–165. Springer, 1997.
[17] Niels Ferguson, John Kelsey, Stefan Lucks, Bruce Schneier, Mike Stay, David Wagner, and Doug Whiting. Improved cryptanalysis of Rijndael. In International Workshop on Fast Software Encryption, pages 213–230. Springer, 2000.
[18] Ting Cui, Chenhui Jin, and Jing Ma. A new method for finding impossible differentials of generalized feistel structures. Chinese Journal of Electronics, 27(4):728–733, 2018.
[19] Bing Sun, Meicheng Liu, Jian Guo, Vincent Rijmen, and Ruilin Li. Provable security evaluation of structures against impossible differential and zero correlation linear cryptanalysis. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 196–213. Springer, 2016.
[20] Taizo Shirai and Kyoji Shibutani. Improving immunity of feistel ciphers against differential cryptanalysis by using multiple MDS matrices. In International Workshop on Fast Software Encryption, pages 260–278. Springer, 2004.
[21] Mahdi Sajadieh and Mohammad Vaziri. Using MILP in analysis of feistel structures and improving type II GFS by switching mechanism. In International Conference on Cryptology in India, pages 265–281. Springer, 2018.
[22] Sumanta Sarkar and Habeeb Syed. Lightweight diffusion layer: Importance of toeplitz matrices.
Cryptology ePrint Archive, 2016.
[23] Chaoyun Li and Qingju Wang. Design of lightweight linear diffusion layers from near-MDS matrices. Cryptology ePrint Archive, 2017.
[24] Kishan Chand Gupta, Sumit Kumar Pandey, and Ayineedi Venkateswarlu. Towards a general construction of recursive MDS diffusion layers. Designs, Codes and Cryptography, 82(1):179–195, 2017.
[25] Akbar Mahmoodi Rishakani, Mohammad Reza Mirzaee Shamsabad, Seyed Mojtaba Dehnavi, Mohammad Amin Amiri, Hamidreza Maimani, and Nasour Bagheri. Lightweight 4x4 MDS matrices for hardware-oriented cryptographic primitives. The ISC International Journal of Information Security, 11(1):35–46, 2019.
[26] Mahdi Sajadieh and Mohsen Mousavi. Construction of MDS matrices from generalized feistel structures. Designs, Codes and Cryptography, 89(7):1433–1452, 2021.
[27] Christophe De Canni`ere. Trivium: A stream cipher construction inspired by block cipher design principles. In International Conference on Information Security, pages 171–186. Springer, 2006.
[28] Joan Daemen. Cipher and hash function design strategies based on linear and differential cryptanalysis. PhD thesis, Doctoral Dissertation, March 1995, KU Leuven, 1995.
[29] Jongsung Kim, Seokhie Hong, Jaechul Sung, Sangjin Lee, Jongin Lim, and Soohak Sung. Impossible differential cryptanalysis for block cipher structures. In Progress in Cryptology - IN-DOCRYPT 2003, pages 82–96. Springer Berlin
Heidelberg, 2003.
[30] Taizo Shirai, Shoji Kanamaru, and George Abe. Improved upper bounds of differential and linear characteristic probability for camellia. In International Workshop on Fast Software Encryption, pages 128–142. Springer, 2002.
[31] Lorenzo Grassi, Christian Rechberger, and Sondre Rønjom. A new structural-differential property of 5-round AES. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 289–
317. Springer, 2017.
[32] Pierre-Alain Fouque, J ́er ́emy Jean, and Thomas Peyrin. Structural evaluation of AES and chosen-key distinguisher of 9-round AES-128. In Advances in Cryptology – CRYPTO 2013, pages 183–203. Springer Berlin Heidelberg, 2013.
[33] Nicky Mouha, Qingju Wang, Dawu Gu, and Bart Preneel. Differential and linear cryptanalysis using mixedinteger linear programming. In International Conference on Information Security and Cryptology, pages 57–76. Springer, 2011.
[34] Masayuki Kanda. Practical security evaluation against differential and linear cryptanalyses for feistel ciphers with SPN round function. In International Workshop on Selected Areas in Cryptography, pages 324–338. Springer, 2000.
[35] Y. Tsunoo, E. Tsujihara, M. Shigeri, T. Saito,T. Suzaki, and H. Kubo. Impossible differential cryptanalysis of CLEFIA. In FSE 2008, volume 5086, pages 398–411. Springer-Verlag, 2008.