Finding partial hash collisions by brute force parallel programming

摘要

A hash function hashes a longer message of arbitrary length into a much shorter bit string of fixed length, called a hash. Inevitably, there will be a lot of different messages being hashed to the same or similar hash. We call this a hash collision or a partial hash collision. By utilizing multiple processors from the CUNY High Performance Computing Center's clusters, we can locate partial collisions for the hash functions MD5 and SHA1 by brute force parallel programming in C with MPI library. The brute force method of finding a second preimage collision entails systematically computing all of the permutations, hashes, and Hamming distances of the target preimage. We explore varying size target strings and the number of processors allocation to examine the effect these variables have on finding partial collisions. The results show that for the same message space the search time for the partial collisions is roughly halved for each doubling of the number of processors; the longer the message is the better partial collisions are produced.