Fugue is a cryptographic hashing algorithm, designed by Charanjit Jutla, Shai Halevi and Eric Hall from IBM T.J. Watson Research Center. Fugue was submitted to NIST as a candidate for the next SHA-3 hashing standard.
THE HASH FUNCTION FUGUE
Shai Halevi, William E. Hall, and Charanjit S. Jutla
Abstract: We describe Fugue, a hash function supporting inputs of length upto 2^64–1 bits and hash outputs of length upto 512 bits. Notably, Fugue is not based on a compression function. Rather, it is directly a hash function that supports variable-length inputs.
The starting point for Fugue is the hash function Grindahl, but it extends that design to protect against the kinds of attacks that were developed for Grindahl, as well as earlier hash functions like SHA1. A key enhancement is the design of a much stronger round function which replaces the AES round function of Grindahl, using better codes (over longer words) than the AES 4x4 MDS matrix. Also, Fugue makes judicious use of this new round function on a much larger internal state.
The design of Fugue is proof-oriented: the various components are designed in such a way as to allow proofs of security. As a result, we can prove that current attack methods cannot find collisions in Fugue any faster than the trivial birthday attack. Although the proof is computer assisted, the assistance is limited to computing ranks of various matrices.
The Round II version of the NIST Submission can be found here. There is no change in the specification of the algorithms.
If you are implementing Fugue, debug traces can be found through the links on the top left corner.
Last updated 18 Sep 2009