Cryptanalysis of the Tillich-Zémor hash function

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(ℱ 2n). 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. © 2010 International Association for Cryptologic Research.