Towards Finding Active Number of S-Boxes in Block Ciphers using Mixed Integer Linear Programming

Vikas Tiwari, Neelima Jampala, Appala Naidu Tentu, Ashutosh Saxena


Secure lightweight block ciphers have become an important aspect due to the fact that they are a popular choice for providing security in ubiquitous devices. Two of the most important attacks on block ciphers are differential cryptanalysis [1] and linear cryptanalysis [2]. Calculating the number of active S-boxes is one of the method to examine the security of block ciphers against differential attack. In this paper, we count the minimum number of active S-boxes for several rounds of the lightweight ciphers namely KLEIN, LED and AES. We utilized the method proposed in [9], where calculation of the minimum number of active S-boxes is formulated as a Mixed Integer Linear Programming (MILP) problem. The objective function is to minimize the number of active S-boxes, subject to the constraints imposed by the differential propagation of the cipher. The experimental results are presented in this paper and found to be encouraging.

Full Text:



Biham E., Shamir A. (1991) Differential Cryptanalysis of DES-like Cryptosystems.Advances in Cryptology-CRYPTO 90.CRYPTO 1990. Lecture Notes in ComputerScience, vol 537. Springer, Berlin, Heidel-berg.

Matsui M. Linear Cryptanalysis Methodfor DES Cipher. Advances in Cryptology- EUROCRYPT 93. EUROCRYPT 1993.Lecture Notes in Computer Science, vol 765.Springer, Berlin, Heidelberg, 1994.

Daemen J., Clapp C. Fast Hashing andStream Encryption with Panama. Fast Soft-ware Encryption. FSE 1998. Lecture Notesin Computer Science, vol 1372. Springer,Berlin, Heidelberg, 1998.

Daemen, J., Rijmen, V.: The Design ofRijndael: AES - The Advanced EncryptionStandard. Springer, 2002.

Das, M.L., Saxena, A., Gulati, V.P. An efficient proxy signature scheme with re-vocation, Informatica, Vol. 15 Issue 4,pp.455-464, 2004.

C. S. Ma and R. H. Miller, MILP opti-mal path planning for real-time applications,2006 American Control Conference, Min-neapolis, MN, , pp. 6 pp.-, 2006.


Bogdanov A. et al. PRESENT: An Ultra-Lightweight Block Cipher. CryptographicHardware and Embedded Systems - CHES2007. CHES 2007. Lecture Notes in Com-puter Science, vol 4727. Springer, Berlin,Heidelberg 2007.

Borghoff J., Knudsen L.R., Stolpe M.Bivium as a Mixed-Integer Linear Program-ming Problem. Cryptography and Coding.IMACC 2009. Lecture Notes in ComputerScience, vol 5921. Springer, Berlin, Heidel-berg 2009.

Mouha N., Wang Q., Gu D., Preneel B.Differential and Linear Cryptanalysis UsingMixed-Integer Linear Programming. Infor-mation Security and Cryptology. Inscrypt2011. Lecture Notes in Computer Science,vol 7537. Springer, Berlin, Heidelberg, 2011.

Guo J., Peyrin T., Poschmann A., RobshawM. The LED Block Cipher. CryptographicHardware and Embedded Systems CHES2011. CHES 2011. Lecture Notes in Com-puter Science, vol 6917. Springer, Berlin,Heidelberg, 2011.

Moradi A., Poschmann A., Ling S., PaarC., Wang H. Pushing the Limits: A VeryCompact and a Threshold Implementationof AES. Advances in Cryptology EURO-CRYPT 2011. EUROCRYPT 2011. LectureNotes in Computer Science, vol 6632.Springer, Berlin, Heidelberg, 2011.

Gong Z., Nikova S., Law Y.W. KLEIN: ANew Family of Lightweight Block Ciphers.Security and Privacy. RFIDSec 2011. Lec-ture Notes in Computer Science, vol 7055.Springer, Berlin, Heidelberg, 2012.

Fathy A., Tarrad I.F., Hamed H.F.A., AwadA.I. Advanced Encryption Standard Algo-rithm: Issues and Implementation Aspects.Advanced Machine Learning Technologiesand Applications. AMLTA 2012. Commu-nications in Computer and InformationScience, vol 322. Springer, Berlin, Heidel-berg, 2012.

Sun S., Hu L., Wang P., Qiao K., Ma X.,Song L. Automatic Security Evaluation and(Related-key) Differential CharacteristicSearch: Application to SIMON, PRESENT,LBlock, DES(L) and Other Bit-OrientedBlock Ciphers. Advances in Cryptology -ASIACRYPT 2014. ASIACRYPT 2014.Lecture Notes in Computer Science, vol8873. Springer, Berlin, Heidelberg, 2014.

Banik S. et al. Midori: A Block Cipherfor Low Energy. Advances in CryptologyASIACRYPT 2015. ASIACRYPT 2015.Lecture Notes in Computer Science, vol9453. Springer, Berlin, Heidelberg, 2015.

Bhattacharya, Rajeev, Linear Programming.Palgrave Encyclopedia of Strategic Man-agement, ISBN 978-1-137-49190-9, PalgraveMacmillan UK, 2014.

Xiang Z., Zhang W., Bao Z., Lin D. ApplyingMILP Method to Searching Integral Distin-guishers Based on Division Property for 6Lightweight Block Ciphers. ASIACRYPT2016. ASIACRYPT 2016. Lecture Notesin Computer Science, vol 10031. Springer,Berlin, Heidelberg, 2016.

Ping Yang, Chuankun Wu, Wentao Zhang,Automatic Security Analysis of EPCBCagainst Differential Attacks, Procedia Com-puter Science, Volume 107, 2017, Pages176-182, ISSN 1877-0509, 2017.

Pei Zhang, Wenying Zhang. DifferentialCryptanalysis on Block Cipher Skinny withMILP Program. Hindawi Security and Com-munication Networks Volume 2018.

Zhou, C., Zhang, W., Ding, T., & Xiang, Z.Improving the MILP-based Security Evalu-ation Algorithm against Differential/LinearCryptanalysis Using A Divide-and-ConquerApproach. IACR Transactions on SymmetricCryptology, 438469, 2020.

E. Bagherzadeh and Z. Ahmadian, MILP-based automatic differential search for LEAand HIGHT block ciphers, in IET Informa-tion Security, vol. 14, no. 5, pp. 595-603,2020.

H. Zhao, G. Han, L. Wang and W. Wang,MILP-Based Differential Cryptanalysis onRound-Reduced Midori64, in IEEE Access,vol. 8, pp. 95888-95896, 2020.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.