Paper 2014/423

The Hash Function "Fugue"

Shai Halevi, William E. Hall, and Charanjit S. Jutla


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 kind of attacks that were developed for Grindahl, as well as earlier hash functions like SHA-1. 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 4 X 4 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, and yet be efficient to implement. 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.

Available format(s)
Publication info
Preprint. MINOR revision.
Contact author(s)
csjutla @ us ibm com
2014-06-06: received
Short URL
Creative Commons Attribution


      author = {Shai Halevi and William E.  Hall and Charanjit S.  Jutla},
      title = {The Hash Function "Fugue"},
      howpublished = {Cryptology ePrint Archive, Paper 2014/423},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.