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
\textit{round transformation} \textbf{R} parametrized by a 32-bit
message word. Twice in every state update, this transform invokes an AES like
round function called \textbf{SMIX}. Fugue-256 relies on a \textit{final
transformation} \textbf{G} to output digests that look random. \textbf{G} has 18
rounds where each round invokes \textbf{SMIX} twice and finally the 960-bit
output of the \textbf{G} transform is mapped with a transform $\tau$ to a
256-bit digest. \\
In this paper, we present some improved as well as new analytical results of
Fugue-256 (with length-padding). First we improve Aumasson and Phans' integral
distinguisher on the 5.5
rounds of the \textbf{G} transform to 16.5 rounds, thus showing \textit{weak}
diffusion in the \textbf{G} transform. Next we improve the
designers' meet-in-the-middle preimage attack
on Fugue-256 from $2^{480}$ time and memory to $2^{416}$.
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 \textbf{G}
transform shown by the designers to present an efficient distinguisher for the
$\tau(\mathbf{G})(.)$ transform showing another \textit{weak}
diffusion property of \textbf{G}. We then extend this distinguisher to some
interesting practical free-start distinguishers and free-start collisions for
the length padded Fugue-256 in $2^{33}$ complexity. Finally, we show that
free-start collision attacks on the length-padded Fugue-256 can be
found in just $\mathcal{O}(1)$ \textit{without} relying on the differential
properties of the \textbf{G} transform and even \textit{without} inverting
it.
Keywords: Fugue-256, Hash function analysis, SHA-3 hash
competition, Distinguishers, Meet-in-the-Middle Preimage attack.
Paper download: [ pdf]