SHA-1差分路径搜索算法和连接策略研究
作者:
作者单位:

作者简介:

曾光(1980-),男,博士,副教授,主要研究领域为密码学与算法分析,密码工程技术;杨阳(1980-),女,博士,副教授,主要研究领域为密码学与算法分析,密码算法设计;李婧瑜(1996-),女,硕士生,主要研究领域为Hash函数攻击技术.

通讯作者:

杨阳,E-mail:yangyang_wawa@126.com

中图分类号:

TP309

基金项目:

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


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

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    Hash函数SHA-1的攻击技术研究一直受到密码分析者的广泛关注,其中,差分路径构造是影响攻击复杂度大小的重要环节.提出了带比特条件的全轮差分路径构造方法,统一了第1轮差分路径构造和后3轮的差分路径构造.该方法既与原有第1轮路径构造相容,又能省去后3轮路径约简、消息约简等繁琐技术环节,具有良好的兼容性.此外,综合考虑状态差分、布尔函数差分与比特条件之间的制约关系,提出了带比特条件的前向扩展、后向扩展和中间连接这3个子算法,并提出3个指标——比特条件的更新次数、扩展结果的相容性和候选集合的正确率对中间连接的成功率进行评价,结合提前终止策略,提出了最优的中间连接算法.理论分析结果表明,该方法有助于提高SHA-1差分路径构造的成功率.最后,采用该算法进行路径搜索,可以得到正确的可用于碰撞搜索的差分路径.

    Abstract:

    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 to bitconditions, compatibility of extension results, and accuracy of candidate sets. Analyzing these three indexes, the relationship between the success rate and them is achieved. The number of forward expansions is proportional to the update times to bitconditions. As for the compatibility of extension results, the times to judge the consistency between the expansion result and original conditions is inversely proportional to the success rate. These two indexes are affected by the number of forward or backward expansions. The accuracy of candidate sets refers to the correct rate of the selectable of working state difference, Boolean function difference and message difference. Analyses finds that the order of the expansions can affect this accuracy. The accuracy of two expansions in opposite directions is higher than that in the same direction. So forward expansions and backward expansions are executed alternately at the first four expansions of the connect algorithm in this study. According to these conclusions, the optimal connect algorithm is selected from 25 possible algorithms. Combining early-abort strategy, the connect algorithm proposed in this study has higher success rate and lower complexity. Theoretical analysis results show that this method helps to improve the success rate of SHA-1 differential path construction. At last, valid differential paths which are used for collision search can be constructed using the algorithm in this study.

    参考文献
    相似文献
    引证文献
引用本文

曾光,李婧瑜,杨阳. SHA-1差分路径搜索算法和连接策略研究.软件学报,2022,33(12):4784-4803

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2020-10-29
  • 最后修改日期:2021-01-10
  • 录用日期:
  • 在线发布日期: 2022-12-03
  • 出版日期: 2022-12-06
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号