Paper 2007/430
Cryptanalysis of LASH
Scott Contini, Krystian Matusiewicz, Josef Pieprzyk, Ron Steinfeld, Jian Guo, San Ling, and Huaxiong Wang
Abstract
We show that the LASH$x$ hash function is vulnerable to attacks that trade time for memory, including collision attacks as fast as $2^{\frac{4}{11}x}$ and preimage attacks as fast as $2^{\frac47x}$. Moreover, we describe heuristic lattice based collision attacks that use small memory but require very long messages. Based upon experiments, the lattice attacks are expected to find collisions much faster than $2^{x/2}$. All of these attacks exploit the designers' choice of an all zero IV. We then consider whether LASH can be patched simply by changing the IV. In this case, we show that LASH is vulnerable to a $2^{\frac78x}$ preimage attack. We also show that LASH is trivially not a PRF when any subset of input bytes is used as a secret key. None of our attacks depend upon the particular contents of the LASH matrix  we only assume that the distribution of elements is more or less uniform. Additionally, we show a generalized birthday attack on the final compression of LASH which requires $O\left(x2^{\frac{x}{2(1+\frac{107}{105})}}\right) \approx O(x2^{x/4})$ time and memory. Our method extends the Wagner algorithm to truncated sums, as is done in the final transform in LASH.
Metadata
 Available format(s)
 Category
 Secretkey cryptography
 Publication info
 Published elsewhere. Extended version of FSE 2008 submission
 Keywords
 LASHhash functioncollision attackpreimage attack
 Contact author(s)
 scontini @ ics mq edu au
 History
 20071124: received
 Short URL
 https://ia.cr/2007/430
 License

CC BY
BibTeX
@misc{cryptoeprint:2007/430, author = {Scott Contini and Krystian Matusiewicz and Josef Pieprzyk and Ron Steinfeld and Jian Guo and San Ling and Huaxiong Wang}, title = {Cryptanalysis of LASH}, howpublished = {Cryptology ePrint Archive, Paper 2007/430}, year = {2007}, note = {\url{https://eprint.iacr.org/2007/430}}, url = {https://eprint.iacr.org/2007/430} }