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 (either 224, 256, 384 or 512 bits).
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.
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 function SHA-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 (32 nm), e.g.
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.
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.
The designers claim advanced proofs of resistance to differential collision attacks for this improved version.