Paper 2009/376

Cryptanalysis of the Tillich-Zémor hash function

Markus Grassl and Ivana Ilic and Spyros Magliveras and Rainer Steinwandt

Abstract

At CRYPTO ’94, Tillich and Zémor 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émor’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.