Cryptology ePrint Archive: Report 2013/233

Attacks on JH, GrÝ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 significant collision and preimage attacks on JH-$s$ and Gr{\o}stl-$s$. For collision and preimage attack, the adversary needs $ 2^{s/4+l/2+1}$ and $2^{(s+l)/2+1}$ queries to the underlying compression function respectively, where $l$ denotes the encoded bit length of the message; for JH, $l=128$ and for Gr{\o}stl, $l=64$.

If the message length is not padded to the last message block, for $s=224$, the attacker only needs $2^{57}$ and $2^{113}$ compression function queries to mount a collision attack and preimage attack respectively.

For the real JH and Gr{\o}stl, the message length is encoded into 128 and 64 bits respectively. For JH-512, the collision and preimage attack needs $2^{193}$ and $2^{321}$ queries to the compression function respectively. For Gr{\o}stl-512, the collision and preimage attack needs $2^{163}$ and $2^{289}$ queries to the compression function respectively.

Our attacks exploit structure flaws in the design of JH and Gr{\o}stl. It is easily applied to MJH and SMASH since they have similar structure (we call it Evan-Mansour structure) as the above hash functions. 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 against collision and preimage attack.

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

Date: received 22 Apr 2013, last revised 3 May 2013

Contact author: luoyiyuan at gmail com

Available format(s): PDF | BibTeX Citation

Note: The original title of this paper is <Attacks on JH Hash Function>. We found our attack can also be applied to GrÝstl and SMASH since they have similar structure. This is the latest version.

Version: 20130503:084507 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]