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  

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
hash function,  collision search,  SHA-1,  disturbance vector,  

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

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.