Daily Archives: November 26, 2007

TMTOs and lattice based collision attacks against LASH-x

LASH, the lattice-based hash function designed by Kamel Bentahar, Dan Page, Markku-Juhani O. Saarinen and Nigel Smart has been broken into tiny little pieces. A septumvirate of authors (Scott Contini, Krystian Matusiewicz, Josef Pieprzyk, Ron Steinfeld, Jian Guo, San Ling, and Huaxiong Wang) have submitted the following devastating analysis of LASH-x to FSE 2008:

  • Preimages for LASH-x in about 20.36x hash evaluations (and memory).
  • Collisions for LASH-x in about 20.57x work (and storage). LASH-160’s maximum security level thus effectively is about 58 bits, for LASH-256 we get 93 bits.
  • Long-message attacks using lattice reduction techniques
  • LASH is not a pseudo-random function (control 1 byte of input and distinguish the output from random with probability 2^{-8})
  • A TMTO attack on the final compression function working in about O(x2x/4) time and memory
  • Heuristics for a CVP attack against LASH-160 (using NTL‘s BKZ implementation)

The pre-image and collision attacks presented in the paper exploit the specific fact that LASH uses an all-zero IV, however the authors also demonstrate that tweaking the hash function by changing the IV will not help much. An extended version of the article is available on the IACR’s ePrint server.
Update 2007-12-03: as correctly pointed out in a comment by random, this paper has only been submitted to FSE 2008. It is not clear yet whether it is accepted or not, since notifications of acceptance will only be sent out on December, 10th, 2007. Sorry for the confusion!
Update 2007-12-18: The list of accepted papers for the FSE 2008 is public. The LASH paper has been accepted.