SHA-1差分路径搜索算法和连接策略研究  

Research on SHA-1 Differential Path Search Algorithms and Connect Strategies

作　　者：曾光 李婧瑜 杨阳 ZENG Guang;LI Jing-Yu;YANG Yang(State Key Laboratory of Mathematical Engineering and Advanced Computing(PLA Strategic Force Information Engineering University),Zhengzhou 450001,China;Trusted Computing and Information Assurance Laboratory,Institute of Software,Chinese Academy of Sciences,Beijing 100190,China;Huawei Technology Co.Ltd.,Beijing 100095,China)

机构地区：[1]数学工程与先进计算国家重点实验室(中国人民解放军战略支援部队信息工程大学),河南郑州450001 [2]中国科学院软件研究所可信计算与信息保障实验室,北京100190 [3]华为技术有限公司,北京100195

出　　处：《软件学报》2022年第12期4784-4803,共20页Journal of Software

基　　金：国家自然科学基金(61972413);国家重点研发计划(2017YFB0803203);数学工程与先进计算国家重点实验室开放基金(2020A08)。

摘　　要：Hash函数SHA-1的攻击技术研究一直受到密码分析者的广泛关注,其中,差分路径构造是影响攻击复杂度大小的重要环节.提出了带比特条件的全轮差分路径构造方法,统一了第1轮差分路径构造和后3轮的差分路径构造.该方法既与原有第1轮路径构造相容,又能省去后3轮路径约简、消息约简等繁琐技术环节,具有良好的兼容性.此外,综合考虑状态差分、布尔函数差分与比特条件之间的制约关系,提出了带比特条件的前向扩展、后向扩展和中间连接这3个子算法,并提出3个指标——比特条件的更新次数、扩展结果的相容性和候选集合的正确率对中间连接的成功率进行评价,结合提前终止策略,提出了最优的中间连接算法.理论分析结果表明,该方法有助于提高SHA-1差分路径构造的成功率.最后,采用该算法进行路径搜索,可以得到正确的可用于碰撞搜索的差分路径.As one of the most widely used Hash functions,the research on related attack techniques on SHA-1 algorithm has been widely concerned by cryptographers since it was put forward.In the collision attack against SHA-1,the construction of the differential path is an important step that affects the complexity of the attack.This study proposes the concept of a differential path with bitconditions and its construction method.The path comprehensively describes the Boolean function difference,bitcondition,message difference,and working state difference of each step.It is not only compatible with the original first round path construction,but also can save the complicated technologies such as path reduction and message reduction of the last three rounds.Therefore,the differential path with bitconditions has good compatibility.In addition,before proposing a corresponding construction algorithm for the differential path with bitconditions,this study firstly analyzes the value of the output Boolean function difference and its input bitconditions when the three input working state differences are fixed.That is the foundation for the later work.The differential path construction algorithm is divided into three sub-algorithms of forward expansion,backward expansion,and connect algorithm.The forward expansion and backward expansion mainly consider the relationship between the bitcondition on the working state and the output difference of the Boolean function.The forward of each step is based on the expansion result of the previous step,and so is the backward algorithm.The goal of the connect algorithm is to connect the results of forward expansion and backward expansion to form a complete and valid differential path.Whether the connect algorithm is successful determines whether the collision attack can be continued.If the connect algorithm fails,it is necessary to renew the forward expansion and backward expansion.In order to improve the success rate of connection algorithm,this study proposes three related indexes of update times

关 键 词：密码学 HASH函数 SHA-1算法 差分路径 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]