Efficient Hash Collision Search Strategies on Special-Purpose Hardware

Tim Güneysu, Chris­tof Paar, Sven Schäge

Research in Cryptology, Second Western European Workshop, WEWoRC 2007, Bochum, Germany, July 4-6, 2007, Revised Selected Papers


Abstract

Hash functions play an important role in various cryptographic applications. Modern cryptography relies on a few but supposedly well analyzed hash functions, most of which are part of the so called MD4-family. This work shows whether it is possible, using special-purpose hardware, to signi?cantly speedup collision search for MD4-family hash functions. A thorough analysis of the computational requirements of MD4-family hash functions and their corresponding collision attacks reveals that a microprocessor based architecture is best suited for the implementation of collision search algorithms. Consequently, we designed and implemented a general-purpose microprocessor for MD4-family hash-functions with minimal area requirements and, based on this, a full collision search integrated circuit. Comparing the performance characteristics of both ASICs with standard PC processors and networks, it turns out that our design, massively parallelized, is nearly four times more cost-efficient than parallelized standard PCs. We believe that there is much room for further improvements left.

[DOI] [BibTeX] [pdf]

Tags: crypto attack, Hash functions, special-purpose hardware