Cryptology ePrint Archive: Report 2008/173
Full Cryptanalysis of LPS and Morgenstern Hash Function
Christophe Petit and Kristin Lauter and Jean-Jacques Quisquater
Abstract: Collisions in the LPS cryptographic hash function of Charles, Goren and Lauter have been found by Zémor and
Tillich, but it was not clear whether computing preimages was also easy for this hash
function. We present a probabilistic polynomial time algorithm solving this problem. Subsequently, we study the
Morgenstern hash, an interesting variant of LPS hash, and break this function as well. Our attacks build upon the ideas of Zémor and Tillich but are not straightforward extensions of it. Finally, we discuss fixes for the
Morgenstern hash function and other applications of our results.
Category / Keywords: cryptographic protocols / Hash Functions, Cayley Graphs, Cryptanalysis
Date: received 15 Apr 2008
Contact author: christophe petit at uclouvain be
Available format(s): PDF | BibTeX Citation
Version: 20080421:093426 (All versions of this report)
Short URL: ia.cr/2008/173
[ Cryptology ePrint archive ]