International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Full Cryptanalysis of LPS and Morgenstern Hash Function

Authors:
Christophe Petit
Kristin E. Lauter
Jean-Jacques Quisquater
Download:
URL: http://eprint.iacr.org/2008/173
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2008-17850,
  title={Full Cryptanalysis of LPS and Morgenstern Hash Function},
  booktitle={IACR Eprint archive},
  keywords={cryptographic protocols / Hash Functions, Cayley Graphs, Cryptanalysis},
  url={http://eprint.iacr.org/2008/173},
  note={ christophe.petit@uclouvain.be 13984 received 15 Apr 2008},
  author={Christophe Petit and Kristin E. Lauter and Jean-Jacques Quisquater},
  year=2008
}