¡@
Journal of Information Science and Engineering, Vol. 26 No.
6, pp. 2143-2157 (November 2010)
New Disturbance Vector for SHA-0 Collision*
SHUANG WU, DENG-GUO FENG AND WEN-LING WU
State Key Laboratory of Information Security
Institute of Software
Chinese Academy of Sciences
Beijing, 100190 P.R. China
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) v (c ^ d) v (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.
Keywords:
hash function, collision search attack, disturbance vector, differential path,
message modification, SHA-0
Retrieve PDF document (201011_13.pdf)
Received November 6, 2008; revised May 11 & July 29, 2009; accepted September 3, 2009.
Communicated by Tzong-Chen Wu.
* This work was supported by the National High-Tech Research and Development 863 Plan of China (No. 2007
AA01Z470), the National Natural Science Foundation of China (No. 60873259), and the National Grand
Fundamental Research 973 Program of China (No. 2004CB318004).
1 In this paper we use actual weight of a disturbance vector to denote numbers of sufficient conditions in steps
21-80 of the differential path derived from the vector, which is highly related to the searching complexity.