Previous [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10] [ 11] [ 12] [ 13] [ 14] [ 15] [ 16] [ 17] [ 18] [ 19] [ 20] [ 21] [ 22] [ 23] [ 24] [ 25]

@

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

Full Text () 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.