Paper 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 $$ and $$ 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 $$. Our trivial collision attacks also requires $$ complexities but, utilizing existing results on SHA-1, we can find a SHA-V collision with a time complexity $$ and a negligible memory complexity. These results indicate that there are weaknesses in both the structure and the round function of SHA-V.