A CellBE-based HPC Application for the Analysis of Vulnerabilities in Cryptographic Hash Functions

After some recent breaks presented in the technical literature, it has become of paramount importance to gain a deeper understanding of the robustness and weaknesses of cryptographic hash functions. In particular, in the light of the recent attacks to the MD5 hash function, SHA-1 remains currently the only function that can be used in practice, since it is the only alternative to MD5 in many security standards. This work presents a study of vulnerabilities in the SHA family, namely the SHA-0 and SHA-1 hash functions, based on a high-performance computing application run on the MariCel cluster available at the Barcelona Supercomputing Center. The effectiveness of the different optimizations and search strategies that have been used is validated by a comprehensive set of quantitative evaluations, presented in the paper. Most importantly, at the conclusion of our study, we were able to identify an actual collision for a 71-round version of SHA-1, the first ever found so far.