Fugue (hash function)
Encyclopedia
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 45nm Core2 processors, e.g. T9400, Fugue-256 runs at 16 cycles per byte using SSE4.1 instructions. On the newer Westmere architectures (32nm), 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 4x4 column mixing matrix with a 16x16 "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 core of the algorithm, known as the "SuperMix transformation", takes 4x4 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 (i.e. SuperMix affects only the 4x4 matrix at the head of the state).
The SuperMix function can be defined as:
where:
;
is a 4x4 matrix of bytes (i.e. the matrix after the S-Box substitution of the input); and
is the transpose of M.
The transformation
takes a 4x4 matrix, and rotates the 
-th row to the left by 
bytes, i.e.
Cryptographic hash function
A cryptographic hash function is a deterministic procedure that takes an arbitrary block of data and returns a fixed-size bit string, the hash value, such that an accidental or intentional change to the data will change the hash value...
submitted by IBM
IBM
International Business Machines Corporation or IBM is an American multinational technology and consulting corporation headquartered in Armonk, New York, United States. IBM manufactures and sells computer hardware and software, and it offers infrastructure, hosting and consulting services in areas...
to the NIST hash function competition
NIST hash function competition
The NIST hash function competition is an open competition held by the US National Institute of Standards and Technology for a new SHA-3 function to replace the older SHA-1 and SHA-2, which was formally announced in the Federal Register on November 2, 2007...
. 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
Differential cryptanalysis
Differential cryptanalysis is a general form of cryptanalysis applicable primarily to block ciphers, but also to stream ciphers and cryptographic hash functions. In the broadest sense, it is the study of how differences in an input can affect the resultant difference at the output...
cannot be efficient against Fugue. It is also claimed to be competitive with the NIST hash function SHA-256
SHA hash functions
In cryptography, SHA-1 is a cryptographic hash function designed by the United States National Security Agency and published by the United States NIST as a U.S. Federal Information Processing Standard. SHA stands for "secure hash algorithm". The three SHA algorithms are structured differently and...
in both software and hardware efficiency, achieving up to 36.2 cycles per byte
Cycles per byte
Cycles per byte is a unit of measurement which indicates the number of clock cycles a microprocessor will perform per byte of data processed in an algorithm. It is commonly used as a partial indicator of real-world performance in cryptographic functions....
on an Intel Family 6 Model 15 Xeon 5150, and up to 25 cycles per byte
Cycles per byte
Cycles per byte is a unit of measurement which indicates the number of clock cycles a microprocessor will perform per byte of data processed in an algorithm. It is commonly used as a partial indicator of real-world performance in cryptographic functions....
on an Intel Core 2 processor T7700. On 45nm Core2 processors, e.g. T9400, Fugue-256 runs at 16 cycles per byte using SSE4.1 instructions. On the newer Westmere architectures (32nm), 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
Advanced Encryption Standard
Advanced Encryption Standard is a specification for the encryption of electronic data. It has been adopted by the U.S. government and is now used worldwide. It supersedes DES...
, but it replaces the 4x4 column mixing matrix with a 16x16 "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 4x4 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 (i.e. SuperMix affects only the 4x4 matrix at the head of the state).
The SuperMix function can be defined as:
where:
; is a 4x4 matrix of bytes (i.e. the matrix after the S-Box substitution of the input); and is the transpose of M.The transformation
takes a 4x4 matrix, and rotates the -th row to the left by bytes, i.e.