Cryptology ePrint Archive: Report 2009/376

Cryptanalysis of the Tillich-Z\'emor hash function

Markus Grassl and Ivana Ilic and Spyros Magliveras and Rainer Steinwandt

Abstract: At CRYPTO ’94, Tillich and Z\'emor proposed a family of hash functions, based on computing a suitable matrix product in groups of the form SL_2(F_{2^n}).We show how to construct collisions between palindromic bit strings of length 2n + 2 for Tillich and Z\'emor’s construction. The approach also yields collisions for related proposals by Petit et al. from ICECS ’08 and CT-RSA ’09. It seems fair to consider our attack as practical: for parameters of interest, the colliding bit strings have a length of a few hundred bits and can be found on a standard PC within seconds.

Category / Keywords: foundations / cryptanalysis, hash functions

Date: received 30 Jul 2009

Contact author: rsteinwa at fau edu

Available formats: PDF | BibTeX Citation

Version: 20090803:194937 (All versions of this report)

Discussion forum: Show discussion | Start new discussion