Fugue (hash function)

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.

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 4×4 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:

$\text{SuperMix}(U) = \text{ROL} \left( M \cdot U + \begin{pmatrix} \sum_{j \ne 0} U_j^i & 0 & 0 & 0\\ 0 & \sum_{j \ne 1} U_j^i & 0 & 0\\ 0 & 0 & \sum_{j \ne 2} U_j^i & 0\\ 0 & 0 & 0 & \sum_{j \ne 3} U_j^i \end{pmatrix} \cdot M^T \right)$

where:

$M = \begin{pmatrix} 1 & 4 & 7 & 1\\ 1 & 1 & 4 & 7\\ 7 & 1 & 1 & 4\\ 4 & 7 & 1 & 1 \end{pmatrix}$;

$U$ is a 4x4 matrix of bytes (i.e. the matrix after the S-Box substitution of the input); and

$M^T$ is the transpose of M.

The transformation $ROL$ takes a 4x4 matrix, and rotates the $i$-th row to the left by $i$ bytes, i.e.

$\text{ROL}(W)_j^i = W_{j-i \pmod 4}^{i}$

Fugue 2.0

Fugue 2.0 is a tweak of original Fugue, which runs at about twice the speed of Fugue for 256-bit output. The designers claim advanced proofs of resistance to differential collision attacks for this improved version. A complete specification can be found at the link below.

External links

• The Hash Function Fugue