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

Clc Number:

TP309

  • Article
  • | |
  • Metrics
  • |
  • Reference [20]
  • |
  • Related [20]
  • | | |
  • 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
    [1] NIST.FIPS 180-1:Secure hash standard.1995.https://nvlpubs.nist.gov/nistpubs/Legacy/FIPS/fipspub180-1.pdf
    [2] Stevens M.New collision attacks on SHA-1 based on optimal joint local-collision analysis.In:Johansson T, Nguyen PQ, eds.Proc.of the Advances in Cryptology (EUROCRYPT 2013).Berlin, Heidelberg:Springer-Verlag, 2013.245-261.
    [3] Stevens M.Attacks on hash functions and applications[Ph.D.Thesis].Leiden:Leiden University, 2012.
    [4] Leurent G, Peyrin T.From collisions to chosen-prefix collisions application to full SHA-1.In:Ishai Y, Rijmen V, eds.Proc.of the Advances in Cryptology (EUROCRYPT 2019).Berlin, Heidelberg:Springer-Verlag, 2019.527-555.
    [5] Leurent G, Peyrin T.SHA-1 is a shambles:first chosen-prefix collision on SHA-1 and application to the PGP Web of trust.In:Capkun S, Roesner F, eds.Proc.of the 29th USENIX Security Symp.Berkeley:USENIX, 2020.1839-1856.
    [6] Manuel S.Classification and generation of disturbance vectors for collision attacks against SHA-1.Designs, Codes and Cryptography, 2011, 59(1):247-263.
    [7] Wang XY, Yin YL, Yu HB.Finding collisions in the full SHA-1.In:Shoup V, ed.Proc.of the Advances in Cryptology (CRYPTO 2005).Berlin, Heidelberg:Springer-Verlag, 2005.17-36.
    [8] Joux A, Peyrin T.Hash functions and the (amplified) boomerang attack.In:Menezes A, ed.Proc.of the Advances in Cryptology (CRYPTO 2007).Berlin, Heidelberg:Springer-Verlag, 2007.244-263.
    [9] Yajima J, Iwasaki T, Naito Y, et al.A strict evaluation on the number of conditions for SHA-1 collision search.IEICE Trans.on Fundamentals of Electronics, Communications and Computer Sciences, 2009, 92-A(1):87-95.
    [10] Tang YC, Zeng G, Han WB.Classification of disturbance vectors for collision attack in SHA-1.Science China Information Sciences, 2015, 58(11):1-10.
    [11] Chabaud F, Joux A.Differential collisions in SHA-0.In:Hrawczyk H, ed.Proc.of the Advances in Cryptology (CRYPTO'98).Berlin, Heidelberg:Springer-Verlag, 1998.56-71.
    [12] Wang XY, Yu HB.How to break MD5 and other Hash functions.In:Cramer R, ed.Proc.of the Advances in Cryptology (EUROCRYPT 2005).Berlin, Heidelberg:Springer-Verlag, 2005.19-35.
    [13] Wang XY, Yao AC, Yao F.Cryptanalysis of SHA-1.In:Proc.of the Presented at the Cryptographic Hash Workshop Hosted by NIST.2005.https://csrc.nist.gov/Events/2005/First-Cryptographic-Hash-Workshop
    [14] Cannière CD, Rechberger C.Finding SHA-1 characteristics:general results and applications.In:Lai XJ, Chen KF, eds.Proc.of the Advances in Cryptology (ASIACRYPT 2006).Berlin, Heidelberg:Springer-Verlag, 2006.1-20.
    [15] Cannière CD, Mendel F, Rechberger C.Collisions for 70-step SHA-1:On the full cost of collision search.In:Adams C, Miri A, Wiener M, eds.Proc.of the Selected Areas in Cryptography.Berlin, Heidelberg:Springer-Verlag, 2007.56-73.
    [16] Chen R.New techniques for cryptanalysis of cryptographic hash functions[Ph.D.Thesis].Haifa:The Senate of the Technion——Israel Institute of Technology, 2011.
    [17] Adinetz AV, Grechnikov EA.Building a collision for 75-round reduced SHA-1 using GPU clusters.In:Kaklamanis C, Papatheodorou T, Spirakis PG, eds.Proc.of the Euro-Par 2012 Parallel Processing.Berlin, Heidelberg:Springer-Verlag, 2012.933-944.
    [18] Stevens M, Karpman P, Peyrin T.Freestart collision for full SHA-1.In:Fischlin M, Coron JS, eds.Proc.of the Advances in Cryptology (EUROCRYPT 2016).Berlin, Heidelberg:Springer-Verlag, 2016.459-483.
    [19] Stevens M, Bursztein E, Karpman P, Albertini A, Markov Y.The first collision for full SHA-1.In:Katz J, Shacham H, eds.Proc.of the Advances in Cryptology (CRYPTO 2017).Berlin, Heidelberg:Springer-Verlag, 2017.570-596.
    [20] Yajima J, Sasaki Y, Naito Y, et al.A new strategy for finding a differential path of SHA-1.In:Pieprzyk J, Ghodosi H, Dawson E, eds.Proc.of the Information Security and Privacy.Berlin, Heidelberg:Springer-Verlag, 2007.45-58.
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

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

Copy
Share
Article Metrics
  • Abstract:644
  • PDF: 1864
  • HTML: 2197
  • Cited by: 0
History
  • Received:October 29,2020
  • Revised:January 10,2021
  • Online: December 03,2022
  • Published: December 06,2022
You are the first2038030Visitors
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