New Disturbance Vector for SHA-0 Collision

摘要

Most of recent collision attacks on SHA-0 are based on the differential path given by Xiaoyun Wang et al. Their disturbance vector was thought to be the best one. We noticed that the way they calculate number of sufficient conditions is not accurate, and we also found some new properties of the third Boolean function MAJ (b ∧ c) ∨ (c ∧d)∨ (d ∧ b). In this paper we present a new disturbance vector, and a new differential path is derived from it. In our differential path, there are less sufficient conditions after step 20 but more of them are in the range of message modification techniques, which means this path has great potential in reducing complexity of SHA-0 collision attack. By advanced message modification, all conditions in up to step 23 can be satisfied. The complexity of our attack is 235 SHA-0 operations. This is the best single block collision attack on SHA-0.