We exploit the additional freedom provided by this model by using a new start-from-the-middle approach in combination with improvements on the cryptanalysis tools that have been developed for SHA-1 in the recent years. This results in particular in better differential paths than the ones used for hash function collisions so far.
Overall, our attack requires about $2^{50}$ evaluations of the compression function in order to compute a one-block free-start collision for a 76-step reduced version, which is so far the highest number of steps reached for a collision on the SHA-1 compression function. We have developed an efficient GPU framework for the highly branching code typical of a cryptanalytic collision attack and used it in an optimized implementation of our attack on recent GTX-970 GPUs.
We report that a single cheap US$350 GTX-970 is sufficient to find the collision in less than 5 days. This showcases how recent mainstream GPUs seem to be a good platform for expensive and even highly-branching cryptanalysis computations. Finally, our work should be taken as a reminder that cryptanalysis on SHA-1 continues to improve. This is yet another proof that the industry should quickly move away from using this function.
Category / Keywords: secret-key cryptography / SHA-1, hash function, cryptanalysis, free-start collision, GPU implementation Original Publication (with minor differences): IACR-CRYPTO-2015 Date: received 1 Jun 2015 Contact author: pierre karpman at gmail com Available format(s): PDF | BibTeX Citation Version: 20150605:000311 (All versions of this report) Short URL: ia.cr/2015/530 Discussion forum: Show discussion | Start new discussion