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

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

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

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.