计算机科学

计算机科学 ›› 2023, Vol. 50 ›› Issue (11A): 220900231-8.doi: 10.11896/jsjkx.220900231

• 信息安全 • 上一篇    下一篇

基于MILP的GIFT积分区分器搜索及优化

祖锦源1, 刘杰1,2, 石一鹏1, 张涛1, 张国群3   

  1. 1 西北工业大学软件学院 西安 710000
    2 西北工业大学长三角研究院 江苏 太仓 215400
    3 上海机电工程研究所 上海 200000
  • 发布日期:2023-11-09
  • 通讯作者: 刘杰(lucky_jiel@ nwpu.edu.com)
  • 作者简介:(zujin@mail.nwpu.edu.cn)
  • 基金资助:
    上海航天科技创新基金(SAST2021-054);太仓市基础研究计划面上项目(TC2021JC32);中央高校基本科研业务费专项资金(D5000210638)

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)

985

摘要： Banik等提出的轻量级分组密码GIFT算法已经入选了NIST针对国际轻量级密码算法开展的标准化竞赛的最终轮。目前已有针对其的线性分析、差分分析等的相关研究,但针对GIFT的积分分析仍待进一步研究。针对GIFT在积分密码分析过程中可分路径表达冗余的问题,提出了基于混合整数线性规划模型的积分区分器搜索求解和优化算法。 首先对GIFT算法创建MILP积分分析模型,利用可分性质分别对GIFT算法的线性层和非线性层进行刻画。 对线性层利用传播规则进行表达;对非线性S盒在传播规则的基础上使用贪心算法对表达式进行精简优化,得到了15个不等式作为约束条件。 经过MILP求解后,得到64个9轮积分区分器。 在此基础上,针对基于贪心算法的MILP求解模型精确度不足问题,引入MILP模型对S盒的可分性质进行重新表达,设计基于MILP的约简算法对GIFT积分区分器搜索进行优化,并重新求解MILP模型,最高得到了3个13轮的积分区分器。因此,基于MILP的S盒新约简算法可以优化S盒可分性质的表达,有效增加对GIFT算法的积分区分器攻击轮数,提高积分攻击效果。

关键词: 积分密码分析, 混合整数线性规划算法, GIFT, 可分性质, SPN网络结构

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

中图分类号: 

  • 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.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市渝北区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发