A Strict Evaluation on the Number of Conditions for SHA-1 Collision Search

Jun YAJIMA
Terutoshi IWASAKI
Yusuke NAITO
Yu SASAKI
Takeshi SHIMOYAMA
Thomas PEYRIN
Noboru KUNIHIRO
Kazuo OHTA

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E92-A    No.1    pp.87-95
Publication Date: 2009/01/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E92.A.87
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: Hash Function
Keyword: 
hash function,  collision search,  SHA-1,  disturbance vector,  

Full Text: PDF(330.1KB)>>
Buy this Article



Summary: 
This paper proposes a new algorithm for evaluating the number of chaining variable conditions (CVCs) in the selecting step of a disturbance vector (DV) for the analysis of SHA-1 collision search. The algorithm is constructed by combining four strategies, that can evaluate the number of CVCs more strictly compared with the previous approach. By using our method, we found some DVs that have 57 (or 59) essential CVCs for 1st (or 2nd) block in the case if we assume that we can modify messages up to step 25, which we have not confirmed the practicability of the assumption.