TY - GEN
T1 - Preimages for the tillich-zémor hash function
AU - Petit, Christophe
AU - Quisquater, Jean Jacques
PY - 2011
Y1 - 2011
N2 - After 15 years of unsuccessful cryptanalysis attempts by the research community, Grassl et al. have recently broken the collision resistance property of the Tillich-Zémor hash function. In this paper, we extend their cryptanalytic work and consider the preimage resistance of the function. We present two algorithms for computing preimages, each algorithm having its own advantages in terms of speed and preimage lengths. We produce theoretical and experimental evidence that both our algorithms are very efficient and succeed with a very large probability on the function parameters. Furthermore, for an important subset of these parameters, we provide a full proof that our second algorithm always succeeds in deterministic cubic time. Our attacks definitely break the Tillich-Zémor hash function and show that it is not even one-way. Nevertheless, we point out that other hash functions based on a similar design may still be secure.
AB - After 15 years of unsuccessful cryptanalysis attempts by the research community, Grassl et al. have recently broken the collision resistance property of the Tillich-Zémor hash function. In this paper, we extend their cryptanalytic work and consider the preimage resistance of the function. We present two algorithms for computing preimages, each algorithm having its own advantages in terms of speed and preimage lengths. We produce theoretical and experimental evidence that both our algorithms are very efficient and succeed with a very large probability on the function parameters. Furthermore, for an important subset of these parameters, we provide a full proof that our second algorithm always succeeds in deterministic cubic time. Our attacks definitely break the Tillich-Zémor hash function and show that it is not even one-way. Nevertheless, we point out that other hash functions based on a similar design may still be secure.
UR - http://www.scopus.com/inward/record.url?scp=79952590519&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-19574-7_20
DO - 10.1007/978-3-642-19574-7_20
M3 - Conference contribution
AN - SCOPUS:79952590519
SN - 9783642195730
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 282
EP - 301
BT - Selected Areas in Cryptography - 17th International Workshop, SAC 2010, Revised Selected Papers
T2 - 17th International Workshop on Selected Areas in Cryptography, SAC 2010
Y2 - 12 August 2010 through 13 August 2010
ER -