Integral Cryptanalysis of Reduced-Round SAND-64 Based on Bit-Based Division Property

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

doi:10.22042/isecure.2023.187449

Integral Cryptanalysis of Reduced-Round SAND-64 Based on Bit-Based Division Property

Document Type : Research Article

Authors

Atiyeh Mirzaie ¹

Siavash Ahmadi ²

Mohammad Reza Aref ¹

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

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

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

Abstract

Conventional Bit-based Division Property (CBDP), as a generalization of integral property, has been a powerful tool for integral cryptanalysis of many block ciphers. Exploiting a Mixed Integral Linear Programming (MILP) optimizer, an alternative approach to searching integral distinguishers was proposed, which has overcome the bottleneck of the cipher block length. The MILP-aided method starts by modeling CBDP propagation by a system of linear inequalities. Then by choosing an appropriate objective function, the problem of searching distinguisher transforms into an MILP problem. As an application of this technique, we focused on a newly proposed lightweight block cipher SAND. SAND is a family of two AND-RX block ciphers SAND-64 and SAND-128, which was designed to overcome the difficulty regarding security
evaluation. For SAND-64, we found a 12-round distinguisher with 23 balanced bits and a data complexity of 263, with the superiority of a higher number of balanced bits than the designers’ one. Furthermore, we applied an integral attack on a 15 and 16-round SAND-64, including the key recovery step which resulted in time complexity of 2105 and 2109.91 and memory complexity of 252 and 285 bytes, respectively.

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 lowlatency 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] 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.
[8] 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.
[9] Lars Knudsen and David Wagner. Integral cryptanalysis. In International Workshop on Fast Software Encryption, pages 112–127. Springer, 2002.
[10] 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.
[11] Yosuke Todo. Integral cryptanalysis on full misty1. Journal of Cryptology, 30(3):920–959, 2017.
[12] 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.
[13] 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.
[14] 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.
[15] Wenying Zhang and Vincent Rijmen. Division cryptanalysis of block ciphers with a binary diffusion layer. IET Information Security, 13(2):87–95, 2019.
[16] 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.
[17] 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.
[18] 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 Infor-
mation Security, pages 398–427. Springer, 2019.
[19] 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.
[20] http://www.gurobi.com/.