Towards Finding Active Number of S-Boxes in Block Ciphers using Mixed Integer Linear Programming
DOI:
https://doi.org/10.31449/inf.v45i6.3427Abstract
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.
References
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.
https://doi.org/10.1007/3-540-38424-3_1
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.
https://doi.org/10.1007/3-540-48285-7_33
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.
https://doi.org/10.1007/3-540-69710-1_5
Daemen, J., Rijmen, V.: The Design ofRijndael: AES - The Advanced EncryptionStandard. Springer, 2002.
https://doi.org/10.1007/978-3-662-60769-5_3
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.
https://doi.org/10.15388/Informatica.2004.072
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.
https://10.1109/ACC.2006.1657504
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.
https://doi.org/10.1007/978-3-540-74735-2_31
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.
https://doi.org/10.1007/978-3-642-10868-6_9
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.
https://doi.org/10.1007/978-3-642-34704-7_5
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.
https://doi.org/10.1007/978-3-642-23951-9_22
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.
https://doi.org/10.1007/978-3-642-20465-4_6
https://www.ibm.com/in-en/analytics/cplex-optimizer
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.
https://doi.org/10.1007/978-3-642-25286-0_1
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.
https://doi.org/10.1007/978-3-642-35326-0_51
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.
https://doi.org/10.1007/978-3-662-45611-8_9
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.
https://doi.org/10.1007/978-3-662-48800-3_17
Bhattacharya, Rajeev, Linear Programming.Palgrave Encyclopedia of Strategic Man-agement, ISBN 978-1-137-49190-9, PalgraveMacmillan UK, 2014.
https://ssrn.com/abstract=2981081
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.
https://doi.org/10.1007/978-3-662-53887-6_24
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.
https://doi.org/10.1016/j.procs.2017.03.075
Pei Zhang, Wenying Zhang. DifferentialCryptanalysis on Block Cipher Skinny withMILP Program. Hindawi Security and Com-munication Networks Volume 2018.
https://doi.org/10.1155/2018/3780407
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.
https://doi.org/10.13154/tosc.v2019.i4.438-469
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.
https://doi.org/10.1049/iet-ifs.2018.5539
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.
Downloads
Published
Issue
Section
License
I assign to Informatica, An International Journal of Computing and Informatics ("Journal") the copyright in the manuscript identified above and any additional material (figures, tables, illustrations, software or other information intended for publication) submitted as part of or as a supplement to the manuscript ("Paper") in all forms and media throughout the world, in all languages, for the full term of copyright, effective when and if the article is accepted for publication. This transfer includes the right to reproduce and/or to distribute the Paper to other journals or digital libraries in electronic and online forms and systems.
I understand that I retain the rights to use the pre-prints, off-prints, accepted manuscript and published journal Paper for personal use, scholarly purposes and internal institutional use.
In certain cases, I can ask for retaining the publishing rights of the Paper. The Journal can permit or deny the request for publishing rights, to which I fully agree.
I declare that the submitted Paper is original, has been written by the stated authors and has not been published elsewhere nor is currently being considered for publication by any other journal and will not be submitted for such review while under review by this Journal. The Paper contains no material that violates proprietary rights of any other person or entity. I have obtained written permission from copyright owners for any excerpts from copyrighted works that are included and have credited the sources in my article. I have informed the co-author(s) of the terms of this publishing agreement.
Copyright © Slovenian Society Informatika
