Computer Science

Computer Science ›› 2023, Vol. 50 ›› Issue (11A): 220900231-8.doi: 10.11896/jsjkx.220900231

• Information Security • Previous Articles     Next Articles

Search and Optimization of GIFT Integral Distinguisher Based on MILP

ZU Jinyuan1, LIU Jie1,2, SHI Yipeng1, ZHANG Tao1, ZHANG Guoqun3   

  1. 1 College of Software,Northwestern Polytechnical University,Xi'an 710000,China
    2 Yangtze River Delta Research Institute,Nerthwestern Polytechnical University,Taicang,Jiangsu 215400,China
    3 Shanghai Institute of Mechanical and Electrical Engineering,Shanghai 200000,China
  • Published:2023-11-09
  • About author:ZU Jinyuan,born in 2001.His main research interests include information security and cryptography.
    LIU Jie,born in 1985,Ph.D,associate professor,is a member of China Computer Federation.His main research interests include cryptography and network security.
  • Supported by:
    Shanghai Aerospace Science and Technology Innovation Fund(SAST2021-054),Taicang City Basic Research Program on Project Fund(TC2021JC32) and Fundamental Research Funds for the Central Universities(D5000210638).

PDF (PC)

894

Abstract: The lightweight block cipher GIFT algorithm proposed by Banik et al.has been selected for the final round of the NIST standardization competition for international lightweight cryptographic algorithms.At present,there have been linear analysis,difference analysis and other related studies,but the integral analysis of GIFT still needs to be further studied.Aiming at the problem of division trails expression redundancy in the process of integral cryptanalysis of GIFT,an integral dividers solution and search optimization algorithm based on mixed integer linear programming model(MILP) is proposed.Firstly,the linear layer and the nonlinear layer of the GIFT algorithm are respectively described according to their bit division property.The linear layer is expressed by the propagation rule,the greedy algorithm is used to simplify the expression for the nonlinear S-box based on the propagation rule,and 15 inequalities are obtained as constraint conditions.64 9-round integral discriminators are found after the MILP solution.On this basis,in order to solve the problem of insufficient accuracy of the MILP solution model based on the greedy algorithm,the MILP model is introduced to reconstruct the bit division property of the S-box.Design a MILP-based reduction algorithm to optimize the GIFT integral dividers search,and re-solve the MILP model,then obtain two 13-round integral discriminators.Therefore,the MILP-based S-box new reduction algorithm can optimize the expression of the S-box division property,and can effectively increase the number of rounds of the integral dividers attack on the GIFT algorithm,and improve the integral attack effect.

Key words: Integral cryptanalysis, Mixed integer linear programming(MILP), GIFT, Division property, SPN network structure

CLC Number: 

  • TN918.1
[1]BANIK S,PANDEY S K,PEYRIN T,et al.GIFT:a small pre-sent[C]//International Conference on Cryptographic Hardware and Embedded Systems.Cham:Springer,2017:321-345.
[2]ZHU B,DONG X,YU H.MILP-based differential attack onround-reduced GIFT[C]//Cryptographers’ Track at the RSA Conference.Cham:Springer,2019:372-390.
[3]ZHANG J,LI L,LI Q,et al.Power analysis attack on a lightweight block cipher GIFT[C]//Proceedings of the 9th International Conference on Computer Engineering and Networks.Singapore:Springer,2021:565-574.
[4]CHEN L,WANG G,ZHANG G Y.MILP-based related-keyrectangle attack and its application to GIFT,Khudra,MIBS[J].The Computer Journal,2019,62(12):1805-1821.
[5]SUN S,HU L,WANG M,et al.Towards finding the best characteristics of some bit-oriented block ciphers and automatic enumeration of(related-key) differential and linear characteristics with predefined properties[J].Cryptology ePrint Archive,2014.
[6]DAEMEN J,KNUDSEN L,RIJMEN V.The block cipherSquare[C]//International Workshop on Fast Software Encryption.Berlin:Springer,1997:149-165.
[7]LUCKS S.The saturation attack－a bait for Twofish[C]//International Workshop on Fast Software Encryption.Berlin:Springer,2001:1-15.
[8]BIRYUKOV A,SHAMIR A.Structural cryptanalysis of SASAS[C]//International Conference on the Theory and Applications of Cryptographic Techniques.Berlin:Springer,2001:395-405.
[9]KNUDSEN L,WAGNER D.Integral cryptanalysis[C]//International Workshop on Fast Software Encryption.Berlin:Sprin-ger,2002:112-127.
[10]Z’ABA M R,RADDUM H,HENRICKSEN M,et al.Bit-pat-tern based integral attack[C]//International Workshop on Fast Software Encryption.Berlin:Springer,2008:363-381.
[11]TODO Y.Structural evaluation by generalized integral property[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques.Berlin:Springer,2015:287-314.
[12]TODO Y,MORII M.Bit-based division property and application to Simon family[C]//International Conference on Fast Software Encryption.Berlin:Springer,2016:357-377.
[13]XIANG Z,ZHANG W,BAO Z,et al.Applying MILP method to searching integral distinguishers based on division property for 6 lightweight block ciphers[C]//International Conference on the Theory and Application of Cryptology and Information Security.Berlin:Springer,2016:648-678.
[14]SUN L,WANG W,WANG M Q.MILP-aided bit-based division property for primitives with non-bit-permutation linear layers[J].IET Information Security,2020,14(1):12-20.
[15]HU K,WANG Q,WANG M.Finding bit-based division property for ciphers with complex linear layers[J].IACR Transactions on Symmetric Cryptology,2020:396-424.
[16]SHANG F Z,SHEN X,LIU G Q,et al.Integral cryptanalysis on PUFFIN based on MILP[J].Journal of Cryptologic Research,2019,6(5):627-638.
[17]SASAKI Y,TODO Y.New algorithm for modeling S-box inMILP based differential and division trail search[C]//International Conference for Information Technology and Communications.Cham:Springer,2017:150-165.
[18]SUN S,HU L,WANG P,et al.Automatic security evaluation and(related-key) differential characteristic search:application to SIMON,PRESENT,LBlock,DES(L) and other bit-oriented block ciphers[C]//International Conference on the Theory and Application of Cryptology and Information Security.Berlin:Springer,2014:158-178.
[1] YANG Han, FENG Yan, XIE Sijiang. Quantum Auction Protocol Based on Semi-quantum Private Comparison [J]. Computer Science, 2023, 50(6): 291-296.
[2] FENG Yan, WANG Rui-cong. Quantum Voting Protocol Based on Quantum Fourier Transform Summation [J]. Computer Science, 2022, 49(5): 311-317.
[3] WGAN Ting-ting, ZHU Jiang. Network Security Situation Forecast Based on Differential WGAN [J]. Computer Science, 2019, 46(11A): 433-437.
[4] MAO He-feng, HU Bin. Homomorphic Evaluation of Lightweight Block Cipher over Integers [J]. Computer Science, 2018, 45(11): 169-175.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.