Cryptology ePrint Archive: Report 2015/494

Cryptanalysis of the LSH and SHA-V Hash Functions

Yonglin Hao and Hongbo Yu

Abstract: In this paper, we study the security of two hash function families LSH and SHA-V.

We find that the wide-pipe MD structural LSH hash functions do not apply the traditional feeding forward operation. This structural feature enables us to launch free-start collision and pseudo-preimage attacks on full-round LSH hash functions with negligible complexities. We think the existence of these attacks is inappropriate for LSH although they does not challenge its overall security levels.

We also evaluate the strength of the LSH round function by launching 14-round boomerang attacks on LSH-512 and LSH-256 hash functions with complexities $2^{308}$ and $2^{242}$ respectively. We verify the correctness of our boomerang attacks by giving practical 11-round boomerang quartets. These boomerang results indicate that the round functions of LSH are well designed.

Based on our analysis, we recommend LSH to adopt the feeding forward operation regardless of its well designed round function.

The PMD structural SHA-V parallelizes two SHA-1-like streams and each stream processes independent 512-bit message blocks. This structure enable us to utilize the divide-and-conquer strategy to find preimages and collisions. Our preimage attack can be applied to full-round SHA-V with time \& memory complexities $O(2^{80})$. Our trivial collision attacks also requires $O(2^{80})$ complexities but, utilizing existing results on SHA-1, we can find a SHA-V collision with a time complexity $O(2^{61})$ and a negligible memory complexity. These results indicate that there are weaknesses in both the structure and the round function of SHA-V.

Category / Keywords: secret-key cryptography / Hash Function, Boomerang Attack, LSH, SHA-V, MD Structure, Feeding Forward

Date: received 24 May 2015, last revised 30 May 2015, withdrawn 23 Jun 2015

Contact author: haoyl14 at mails tsinghua edu cn

Available format(s): (-- withdrawn --)

Version: 20150624:052600 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]