[HGI-News] HGI-Seminar, Montag 4.06.2007: Efficient Hash Collision Search Strategies on Special-Purpose Hardware

[Newsletter des Horst Görtz Instituts]

                Sven Schäge, Ruhr Universität Bochum

             Montag 4. Juni 2007, 13:15 Uhr IC 4 / 39-41

 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, most of which are part of the so called MD4-
family. No wonder that in 2005, a new theoretical attack on SHA-1 caused
great excitement in the cryptographic community, since it reduced attack
complexity to find a random collision from O(2^80) to O(2^63) step
computations.

This presentation shows whether it is possible, using special-purpose
hardware, to significantly speedup collision search for SHA-1 so that
finding a single collision comes into practical reach.

A thorough analysis of MD5 and current collision search algorithms
reveals that a microprocessor based architecture is best suited for the
implementation of collision search algorithms for hash functions of the
MD4-family.

Consequently, we designed and implemented a (concerning MD4-family hash-
functions) general-purpose microprocessor with minimal area requirements
and, based on this, a complete collision search unit. Additionally, we
developed an assembler to equip our collision search unit with a full
implementation of suited collision search algorithms.

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.


_____________________________________________________________________________
Die Webseite des HGI-Seminars mit allen Informationen zu vergangenen und
zukünftigen Vorträgen: http://www.hgi.rub.de/deutsch/lehrangebot/seminar.html

-- 
Für das HGI, Michael Psarros <michael.psarros at nds.rub.de>