Search

A good disturbance vector is one of the key techniques to find SHA-1 collisions and to construct valid differential paths. The main work of this paper is to classify the types of the optimal disturbance vectors. First, we improve the EEM disturbance vectors search algorithm by Manuel. We increase the Hamming weight of information window from 4 to 6, with 244 time complexity, which is 28 times better than that of Manuel’s work. Based on this result, we prove that there are only two types of the optimal disturbance vectors, type-I and type-II, which have minimum weight of 25 in the last 60 of the 80 expanded words, in the total 2512 disturbance vectors searching space.

In this paper, we give a new fast attack on HAVAL-128. Our attack includes many present methods of constructing hash collisions. Moreover, we present a neighborhood modification. We propose a new difference path different from the previous ones. The conclusion is that, when the output of each step satisfies our condition, the message m can collide with m′ = m+Δm, where Δm = (0, 0, 0, 0, 231, 0, ..., 0). There is only one bit difference between m and m′. Two pairs of collision examples for HAVAL-128 are given. In order to improve the probability of collision, we use four tricks of message modification. The attack’s running time is less than 225.83 2-pass HAVAL computations, which is the best result for one-bit collision of HAVAL so far.