### Abstract

Fugue is a cryptographic hash function designed by Halevi, Hall and Jutla and was one
of the fourteen hash algorithms of the second round of NIST’s SHA3 hash competition. We consider
Fugue-256, the 256-bit instance of Fugue. Fugue-256 updates a state of 960 bits with a round transformation
R parametrized by a 32-bit message word. Twice in every state update, this transform
invokes an AES like round function called SMIX. Fugue-256 relies on a final transformation G
to output digests that look random. G has 18 rounds where each round invokes SMIX twice and
finally the 960-bit output of the G transform is mapped with a transform to a 256-bit digest.
In this paper, we present some improved as well as new analytical results of Fugue-256 (with lengthpadding).
First we improve Aumasson and Phans’ integral distinguisher on the 5.5 rounds of the
G transform to 16.5 rounds, thus showing weak diffusion in the G transform. Next we improve the
designers’ meet-in-the-middle preimage attack on Fugue-256 from 2480 time and memory to 2416.
Next we study the security of Fugue-256 against free-start distinguishers and free-start collisions. In
this direction, we use an improved variant of the differential characteristic of the G transform shown
by the designers to present an efficient distinguisher for the (G)(.) transform showing another weak
diffusion property of G. We then extend this distinguisher to some interesting practical free-start
distinguishers and free-start collisions for the length padded Fugue-256 in 233 complexity. Finally,
we show that free-start collision attacks on the length-padded Fugue-256 can be found in just O(1)

Original language | English |
---|

Publication status | Published - 2011 |
---|

### Keywords

- Hash function analysis
- SHA-3 hash competition
- Fugue-256

## Cite this

Gauravaram, P., Bagheri, N., Knudsen, L. R., & Lei, W. (2011).

*Improved security analysis of Fugue-256*.