Efficient Hash Collision Search Strategies on Special-Purpose Hardware

摘要

Hash functions play an important role in various cryptographic applications. Modern cryptography relies on a few but supposedly well analyzed hash functions which are mostly members of the so-called MD4-family. This work shows whether it is possible to significantly speedup collision search for MD4-family hash functions using special-purpose hardware. A thorough analysis of the computational requirements for MD4-family hash functions and 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 (concerning MD4-family hash-functions) general-purpose microprocessor with minimal area requirements and, based on this, a full collision search unit. Comparing the performance characteristics of both ASICs with standard PC processors and clusters, it turns out that our design, massively parallelized, is nearly four times more cost-efficient than parallelized standard PCs. Although with further optimizations this factor can certainly be improved, we believe that special-purpose hardware does not provide a too significant benefit for hash collision search algorithms with respect to modern off-the-shelf general-purpose processors.