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

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

Abstract


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:

PDF

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.




DOI: https://doi.org/10.31449/inf.v45i6.3427

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