Cryptology ePrint Archive: Report 2013/233

Attacks on JH, Gr{\o}stl and SMASH Hash Functions

Yiyuan Luo and Xuejia Lai

Abstract: JH and Gr{\o}stl hash functions are two of the five finalists in NIST SHA-3 competition. JH-$s$ and Gr{\o}stl-$s$ are based on a $2n$ bit compression function and the final output is truncated to $s$ bits, where $n$ is $512$ and $s$ can be $224$,$256$,$384$ and $512$. Previous security proofs show that JH-$s$ and Gr{\o}stl-$s$ are optimal collision resistance without length padding to the last block.

~~~~In this paper we present collision and preimage attacks on JH-$s$ and Gr{\o}stl-$s$ without length padding to the last block. For collision attack on JH-$s$, after a $\frac{1}{e}2^{s/4+n}$ precomputing, the adversary needs $2^{s/4}$ queries to the underlying compression function to find a new collision. For preimage attack on JH-$s$, after a $\frac{1}{e}2^{s/2+n}$ precomputing, the adversary needs $2^{s/2}$ queries to the underlying compression function to find a new preimage. If $s=224$, the attacker only needs $2^{57}$ and $2^{113}$ compression function queries to mount a new collision attack and preimage attack respectively. For Gr{\o}stl, the query complexity of our collision and preimage attack are one half of birthday collision attack and exhaustive preimage attack respectively.

~~~~We also discuss how our attack works when the length is padded to the last message block. Our attacks exploit structure flaws in the design of JH and Gr{\o}stl. It is easily applied to MJH and SMASH and other generalizations since they have similar structure (we call it Evan-Mansour structure). At the same time the provable security of chopMD in the literature is challenged. Through our attack, it is easy to see that the chopMD mode used in JH or Gr{\o}stl does not improve its security.

Category / Keywords: Hash Functions, SHA-3, JH, GrÝstl

Date: received 22 Apr 2013, last revised 12 Oct 2013

Contact author: luoyiyuan at gmail com

Available format(s): PDF | BibTeX Citation

Note: Some bugs in our attack are fixed in this version.

Version: 20131012:123447 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]