Division Property-Based Integral Attack on Reduced-Round SAND-128

Mirzaie, Atiyeh; Ahmadi, Siavash; Aref, Mohammad Reza

doi:10.22042/isecure.2025.216458

Division Property-Based Integral Attack on Reduced-Round SAND-128

Document Type : Research Article

Authors

Atiyeh Mirzaie ¹

Siavash Ahmadi ²

Mohammad Reza Aref ³

¹ nformation Systems and Security Lab (ISSL), Department of Electrical Engineering, Sharif University of Tech., Tehran, Iran

² Electronics Research Institute, Sharif University of Technology, Tehran, Iran

³ Information Systems and Security Lab (ISSL), Department of Electrical Engineering, Sharif University of Technology, Tehran, Iran

https://doi.org/10.22042/isecure.2025.216458

Abstract

Given the rapid evolution of emerging technologies, such as the Internet of Things (IoT), there is a growing interest in lightweight block ciphers. This paper focuses on the security assessment of SAND-128, a newly proposed lightweight block cipher based on SIMON, recognized for its reliance on S-box-based security evaluation approaches. By employing Xiang’s MILP-aided method for integral distinguisher search, this study utilizes a MILP optimizer to identify a 16-round integral characteristic for SAND-128 with nine balanced bits. Furthermore, by extending the distinguisher to 17 rounds utilizing a novel idea without an increase in data complexity, we propose a comprehensive 20-round integral attack on SAND-128, including the key recovery step. This attack leverages the partial sums technique, resulting in a time complexity of 2119, memory complexity of 276 bytes, and data complexity of 2127. This cryptanalysis is, to the best of our knowledge, the best integral attack on reduced-round SAND-128 presented thus far.

Keywords

Division Property

Integral Distinguisher

MILP

SAND Block Cipher

[1] Subhadeep Banik, Andrey Bogdanov, Takanori Isobe, Kyoji Shibutani, Harunaga Hiwatari, Toru Akishita, and Francesco Regazzoni. Midori: A block cipher for low energy. In International Conference on the Theory and Application of Cryptology and Information Security, pages 411–436. Springer, 2015.
[2] Andrey Bogdanov, Lars R Knudsen, Gregor Leander, Christof Paar, Axel Poschmann, Matthew JB Robshaw, Yannick Seurin, and Charlotte Vikkelsoe. Present: An ultralightweight block cipher. In International workshop on cryptographic hardware and embedded systems, pages 450–466. Springer, 2007.
[3] Christof Beierle, Gregor Leander, Amir Moradi, and Shahram Rasoolzadeh. Craft: lightweight tweakable block cipher with efficient protection against dfa attacks. IACR Transactions on Symmetric Cryptology, 2019(1):5–45, 2019.
[4] 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.
[5] Christof Beierle, J´er´emy Jean, Stefan K¨olbl, Gregor Leander, Amir Moradi, Thomas Peyrin, Yu Sasaki, Pascal Sasdrich, and Siang Meng Sim. The skinny family of block ciphers and its low-latency variant mantis. In Annual International Cryptology Conference, pages 123–153. Springer, 2016.
[6] Subhadeep Banik, Sumit Kumar Pandey, Thomas Peyrin, Yu Sasaki, Siang Meng Sim, and Yosuke Todo. Gift: a small present. In International conference on cryptographic hardware and embedded systems, pages 321–345. Springer, 2017.
[7] Qingling Song, Lang Li, and Xiantong Huang. Lelbc: A low energy lightweight block cipher for smart agriculture. Internet of Things, 25:101022, 2024.
[8] Ying Guo, Wenfen Liu, Wen Chen, Qingwen Yan, and Yongcan Lu. Eclbc: A lightweight block cipher with error detection and correction mechanisms. IEEE Internet of Things Journal, 2024.
[9] Ray Beaulieu, Douglas Shors, Jason Smith, Stefan Treatman-Clark, Bryan Weeks, and Louis Wingers. The simon and speck families of lightweight block ciphers. cryptology eprint archive, 2013.
[10] Shiyao Chen, Yanhong Fan, Ling Sun, Yong Fu, Haibo Zhou, Yongqing Li, Meiqin Wang, Weijia Wang, and Chun Guo. Sand: an and-rx feistel lightweight block cipher supporting s-box-based security evaluations. Designs, Codes and Cryp-
tography, 90(1):155–198, 2022.
[11] Je Sen Teh and Alex Biryukov. Differential cryptanalysis of warp. Journal of Information Security and Applications, 70:103316, 2022.
[12] Je Sen Teh, Li Jing Tham, Norziana Jamil, and Wun-She Yap. New differential cryptanalysis results for the lightweight block cipher boron. Journal of Information Security and Applications, 66:103129, 2022.
[13] Siavash Ahmadi and Mohammad Reza Aref. Generalized meet in the middle cryptanalysis of block ciphers with an automated search algorithm. IEEE Access, 8:2284–2301, 2019.
[14] Prakash Dey, Raghvendra Singh Rohit, and Avishek Adhikari. Single key mitm attack and biclique cryptanalysis of full round khudra. Journal of Information Security and Applications, 41:117–123, 2018.
[15] Siavash Ahmadi, Zahra Ahmadian, Javad Mohajeri, and Mohammad Reza Aref. Low-data com-plexity biclique cryptanalysis of block ciphers with application to piccolo and hight. IEEE Transactions on Information Forensics and Security, 9(10):1641–1652, 2014.
[16] Atiyeh Mirzaie, Siavash Ahmadi, and Mohammad Reza Aref. Integral cryptanalysis of round-reduced shadow-32 for iot nodes. IEEE Internet of Things Journal, 2023.
[17] Atiyeh Mirzaie, Siavash Ahmadi, and Mohammad Reza Aref. Integral cryptanalysis of reduced-round sand-64 based on bit-based division property. The ISC International Journal of Information Security, 15(3), 2023.
[18] Xavier Bonnetain and Virginie Lallemand. On boomerang attacks on quadratic feistel ciphers: New results on katan and simon. IACR Transactions on Symmetric Cryptology, 2023(3):101–145, 2023.
[19] Dachao Wang, Baocang Wang, and Siwei Sun. Sat-aided automatic search of boomerang distinguishers for arx ciphers. IACR Transactions on Symmetric Cryptology, pages 152–191, 2023.
[20] Jianing Zhang, Haoyang Wang, and Deng Tang. Impossible boomerang attacks revisited: Applications to deoxys-bc, joltik-bc and skinny. IACR Transactions on Symmetric Cryptology, 2024(2):254–295, 2024.
[21] Xavier Bonnetain, Margarita Cordero, Virginie Lallemand, Marine Minier, and Mar´ıa Naya-Plasencia. On impossible boomerang attacks: Application to simon and skinnyee. IACR Transactions on Symmetric Cryptology, 2024(2):222–253, 2024.
[22] Wei Jian Teng, Je Sen Teh, and Norziana Jamil. On the security of lightweight block ciphers against neural distinguishers: Observations on lbc-iot and slim. Journal of Information Security and Applications, 76:103531, 2023.
[23] Yosuke Todo. Structural evaluation by generalized integral property. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 287–314. Springer, 2015.
[24] Yosuke Todo and Masakatu Morii. Bit-based division property and application to simon family. In International Conference on Fast Software Encryption, pages 357–377. Springer, 2016.

[25] Zejun Xiang, Wentao Zhang, Zhenzhen Bao, and Dongdai Lin. Applying milp method to searching integral distinguishers based on division property for 6 lightweight block ciphers. In International Conference on the Theory and Application of Cryptology and Information Security, pages 648–678. Springer, 2016.
[26] Nicky Mouha, Qingju Wang, Dawu Gu, and Bart Preneel. Differential and linear cryptanalysis using mixed-integer linear programming. In International Conference on Information Security and Cryptology, pages 57–76. Springer, 2011.
[27] Wenying Zhang and Vincent Rijmen. Division cryptanalysis of block ciphers with a binary diffusion layer. IET Information Security, 13(2):87–95, 2019.
[28] Ling Sun, Wei Wang, and Meiqin Q Wang. Milpaided bit-based division property for primitives with non-bit-permutation linear layers. IET Information Security, 14(1):12–20, 2020.
[29] Kai Hu, Qingju Wang, and Meiqin Wang. Finding bit-based division property for ciphers with complex linear layers. IACR Transactions on Symmetric Cryptology, pages 396–424, 2020.
[30] Senpeng Wang, Bin Hu, Jie Guan, Kai Zhang, and Tairong Shi. Milp-aided method of searching division property using three subsets and applications. In International Conference on the Theory and Application of Cryptology and Information Security, pages 398–427. Springer, 2019.
[31] Senpeng Wang, Bin Hu, Jie Guan, Kai Zhang, and Tairong Shi. Exploring secret keys in searching integral distinguishers based on division property. IACR Transactions on Symmetric Cryptology, pages 288–304, 2020.
[32] Niels Ferguson, John Kelsey, Stefan Lucks, Bruce Schneier, Mike Stay, David Wagner, and Doug Whiting. Improved cryptanalysis of rijndael. In Fast Software Encryption: 7th International Workshop, FSE 2000 New York, NY, USA, April 10–12, 2000 Proceedings 7, pages 213–230. Springer, 2001.
[33] Kai Zhang, Senpeng Wang, Xuejia Lai, Lei Wang, Jie Guan, Bin Hu, and Tairong Shi. Impossible differential cryptanalysis and a security evaluation framework for and-rx ciphers. IEEE Transactions on Information Theory, 2023.
[34] Yosuke Todo. Integral cryptanalysis on full misty1. Journal of Cryptology, 30(3):920–959, 2017.
[35] http://www.gurobi.com/.