Full Cryptanalysis of LPS and Morgenstern Hash Function

Christophe Petit; Kristin Lauter; Jean-Jacques Quisquater

Paper 2008/173

Full Cryptanalysis of LPS and Morgenstern Hash Function

Christophe Petit, 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.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. Unknown where it was published
Keywords: Hash Functions Cayley Graphs Cryptanalysis
Contact author(s): christophe petit @ uclouvain be
History: 2008-04-21: received
Short URL: https://ia.cr/2008/173
License: CC BY

BibTeX

@misc{cryptoeprint:2008/173,
      author = {Christophe Petit and Kristin Lauter and Jean-Jacques Quisquater},
      title = {Full Cryptanalysis of {LPS} and Morgenstern Hash Function},
      howpublished = {Cryptology {ePrint} Archive, Paper 2008/173},
      year = {2008},
      url = {https://eprint.iacr.org/2008/173}
}