Finding a collision for the 75-round SHA-1 hash function using clusters of GPUs

SHA-1 is one of the most widely used cryptographic hash functions. An important property of all cryptographic hash functions is the collision resistance, i.e., the infeasibility of finding two different input messages such that they have the same hash values. A further development of the differential attack method for SHA-1 and its reduced versions are proposed. The porting collision search based on the method of characteristics is described for GPU clusters. The method of characteristics employs the backtracking search, which leads to a low GPU performance due to branch divergence if implemented naively. Using a number of optimizations, we reduce the branch divergence and achieve a GPU usage efficiency of 50%, which gives an acceleration of 39 times over a single CPU core. With the aid of our application running on a 512-GPU cluster, we were able to find a collision for a version of SHA-1 reduced to 75 rounds, which is currently (February 2012) the world's best result in terms of number of rounds for SHA-1.