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

Clc Number:

TP309

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    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.

    Reference
    Related
    Cited by
Get Citation

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

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:October 29,2020
  • Revised:January 10,2021
  • Adopted:
  • Online: December 03,2022
  • Published: December 06,2022
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063