Abstract
Collisions in the LPS cryptographic hash function of Charles, Goren and Lauter have been found by Zémor and Tillich [17], 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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
FIPS 180-2 secure hash standard
Charles, D.X., Goren, E.Z., Lauter, K.E.: Cryptographic hash functions from expander graphs. Journal of Cryptology (to appear)
Contini, S., Lenstra, A.K., Steinfeld, R.: VSH, an efficient and provable collision-resistant hash function. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 165–182. Springer, Heidelberg (2006)
Flajolet, P., Soria, M.: Gaussian limiting distributions for the number of components in combinatorial structures. J. Comb. Theory Ser. A 53(2), 165–182 (1990)
Hoory, S., Linial, N., Wigderson, A.: Expander graphs and their applications. Bull. Amer. Math. Soc. 43, 439–561 (2006)
Lubotzky, A., Phillips, R., Sarnak, P.: Ramanujan graphs. Combinatorica 8, 261–277 (1988)
Lyubashevsky, V., Micciancio, D., Peikert, C., Rosen, A.: Provably secure FFT hashing. In: NIST 2nd Cryptogaphic Hash Workshop (2006)
Morgenstern, M.: Existence and explicit construction of q + 1 regular Ramanujan graphs for every prime power q. Journal of Combinatorial Theory B 62, 44–62 (1994)
Petit, C., Lauter, K.E., Quisquater, J.-J.: Full cryptanalysis of LPS and Morgenstern hash functions. Cryptology ePrint Archive, Report 2008/173 (2008), http://eprint.iacr.org/
Petit, C., Lauter, K.E., Quisquater, J.-J.: Cayley hashes: A class of efficient graph-based hash functions (preprint, 2007)
Shoup, V.: On the deterministic complexity of factoring polynomials over finite fields. Inf. Process. Lett. 33(5), 261–267 (1990)
Tillich, J.-P., Zémor, G.: Hashing with SL 2. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 40–49. Springer, Heidelberg (1994)
Tillich, J.-P., Zémor, G.: Group-theoretic hash functions. In: Cohen, G., Lobstein, A., Zémor, G., Litsyn, S.N. (eds.) Algebraic Coding 1993. LNCS, vol. 781, pp. 90–110. Springer, Heidelberg (1994)
Wang, X., Yin, Y.L., Yu, H.: Finding collisions in the full SHA-1. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 17–36. Springer, Heidelberg (2005)
Zémor, G.: Hash functions and Cayley graphs. Des. Codes Cryptography 4(4), 381–394 (1994)
Zémor, G., Tillich, J.-P.: Collisions for the LPS expander graph hash function. In: Smart, N. (ed.) EUROCRYPT 2008. LNCS, vol. 4965. Springer, Heidelberg (2008)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Petit, C., Lauter, K., Quisquater, JJ. (2008). Full Cryptanalysis of LPS and Morgenstern Hash Functions. In: Ostrovsky, R., De Prisco, R., Visconti, I. (eds) Security and Cryptography for Networks. SCN 2008. Lecture Notes in Computer Science, vol 5229. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-85855-3_18
Download citation
DOI: https://doi.org/10.1007/978-3-540-85855-3_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-85854-6
Online ISBN: 978-3-540-85855-3
eBook Packages: Computer ScienceComputer Science (R0)