2005 | Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu
This paper presents new collision search attacks on the SHA-1 hash function, achieving a complexity of less than \(2^{69}\) hash operations. This is the first attack on the full 80-step SHA-1 with complexity below the theoretical bound of \(2^{80}\). The authors introduce several techniques to overcome major obstacles in collision search, including finding near-collision differential paths with low Hamming weight, adjusting differential paths to avoid consecutive and truncated local collisions, and transforming one-block near-collision paths into two-block collision paths. These techniques are applied to SHA-0 and reduced variants of SHA-1, achieving real collisions with complexities below \(2^{39}\) and \(2^{33}\) hash operations, respectively. The paper also discusses the implications of these results and provides detailed analyses of the attack strategies, including the construction of differential paths and the derivation of conditions on messages and chaining variables.This paper presents new collision search attacks on the SHA-1 hash function, achieving a complexity of less than \(2^{69}\) hash operations. This is the first attack on the full 80-step SHA-1 with complexity below the theoretical bound of \(2^{80}\). The authors introduce several techniques to overcome major obstacles in collision search, including finding near-collision differential paths with low Hamming weight, adjusting differential paths to avoid consecutive and truncated local collisions, and transforming one-block near-collision paths into two-block collision paths. These techniques are applied to SHA-0 and reduced variants of SHA-1, achieving real collisions with complexities below \(2^{39}\) and \(2^{33}\) hash operations, respectively. The paper also discusses the implications of these results and provides detailed analyses of the attack strategies, including the construction of differential paths and the derivation of conditions on messages and chaining variables.