TY - GEN
T1 - Hard and easy components of collision search in the Źemor-tillich hash function
T2 - Cryptographers' Track at the RSA Conference, CT-RSA 2009
AU - Petit, Christophe
AU - Quisquater, Jean Jacques
AU - Tillich, Jean Pierre
AU - Źemor, Gilles
PY - 2009
Y1 - 2009
N2 - The Zémor-Tillich hash function has remained unbroken since its introduction at CRYPTO'94.We present the first generic collision and preimage attacks against this function, in the sense that the attacks work for any parameters of the function. Their complexity is the cubic root of the birthday bound; for the parameters initially suggested by Tillich and Zémor they are very close to being practical. Our attacks exploit a separation of the collision problem into an easy and a hard component. We subsequently present two variants of the Zémor-Tillich hash function with essentially the same collision resistance but reduced outputs of 2n and n bits instead of the original 3n bits. Our second variant keeps only the hard component of the collision problem; for well-chosen parameters the best collision attack on it is the birthday attack.
AB - The Zémor-Tillich hash function has remained unbroken since its introduction at CRYPTO'94.We present the first generic collision and preimage attacks against this function, in the sense that the attacks work for any parameters of the function. Their complexity is the cubic root of the birthday bound; for the parameters initially suggested by Tillich and Zémor they are very close to being practical. Our attacks exploit a separation of the collision problem into an easy and a hard component. We subsequently present two variants of the Zémor-Tillich hash function with essentially the same collision resistance but reduced outputs of 2n and n bits instead of the original 3n bits. Our second variant keeps only the hard component of the collision problem; for well-chosen parameters the best collision attack on it is the birthday attack.
UR - http://www.scopus.com/inward/record.url?scp=67650168932&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-00862-7_12
DO - 10.1007/978-3-642-00862-7_12
M3 - Conference contribution
AN - SCOPUS:67650168932
SN - 9783642008610
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 182
EP - 194
BT - Topics in Cryptology - CT-RSA 2009 - The Cryptographers' Track at the RSA Conference 2009, Proceedings
PB - Springer Verlag
Y2 - 20 April 2009 through 24 April 2009
ER -