Fugue is a cryptographic hash function submitted by IBM to the NIST hash function competition. It was designed by Shai Halevi, William E. Hall, and Charanjit S. Jutla. Fugue takes an arbitrary-length message and compresses it down to a fixed bit-length. The hash functions for the different output lengths are called Fugue-224, Fugue-256, Fugue-384 and Fugue-512. The authors also describe a parametrized version of Fugue. A weak version of Fugue-256 is also described using this parameterized version. The selling point of Fugue is the authors' claimed proof that a wide range of current attack strategies based on differential cryptanalysis cannot be efficient against Fugue. It is also claimed to be competitive with the NIST hash functionSHA-256 in both software and hardware efficiency, achieving up to 36.2 cycles per byte on an Intel Family 6 Model 15 Xeon 5150, and up to 25 cycles per byte on an Intel Core 2 processor T7700. On 45 nm Core2 processors, e.g. T9400, Fugue-256 runs at 16 cycles per byte using SSE4.1 instructions. On the newer Westmere architectures, e.g. Core i5, Fugue-256 runs at 14 cycles/byte. Fugue's design starts from the hash function Grindahl, and like Grindahl uses the S-box from AES, but it replaces the 4×4 column mixing matrix with a 16×16 "super-mix" operation which greatly improves diffusion. The "super-mix" operation is, however, only slightly more computationally expensive to implement than the AES mixing strategy.
SuperMix
The 224 and 256 bit variants of Fugue work with a state which can be represented in 4 by 30 matrix of unsigned bytes, whereas the 384 and 512 bit variants work with a 4 by 36 byte matrix. Operations can be performed in-place on this state. The core of the algorithm, known as the "SuperMix transformation", takes 4×4 matrix as input and returns a new 4x4 matrix. The input to SuperMix is simply the first four columns of the current 30-column state and the output is used to replace this same state area. The SuperMix function can be defined as: where: The transformation takes a 4x4 matrix, and rotates the -th row to the left by bytes, i.e.
Fugue 2.0
Fugue 2.0 is a tweak of original Fugue, which runs at about twice the speed of Fugue for 256-bit output. The designers claim advanced proofs of resistance to differential collision attacks for this improved version. A complete specification can be found at the link below.
