 | This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. (October 2014) |
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. 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 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. 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.