Fugue

1 The algorithm

Shai Halevi, William E. Hall, Charanjit S. Jutla - The Hash Function Fugue
Submission to NIST (updated), 2009
[Electronic Edition] [Bibtex]
Author : Shai Halevi, William E. Hall, Charanjit S. Jutla
Title : The Hash Function Fugue
In : Submission to NIST (updated) -

Shai Halevi, William E. Hall, Charanjit S. Jutla - The Hash Function Fugue
Submission to NIST, 2008
[Electronic Edition] [Bibtex]
Author : Shai Halevi, William E. Hall, Charanjit S. Jutla
Title : The Hash Function Fugue
In : Submission to NIST -

2 Cryptanalysis

We distinguish between two cases: results on the complete hash function, and results on underlying building blocks.

A description of the tables is given here.

Recommended security parameters: (k,r,t) = (2,5,13) for (n=224,256); (k,r,t) = (3,5,13) for (n=384); (k,r,t) = (4,8,13) for (n=512)

2.1 Hash function

Here we list results on the hash function according to the NIST requirements. The only allowed modification is to change the security parameter.

 Type of Analysis Hash Size (n) Parameters Compression Function Calls Memory Requirements Reference

2.2 Building blocks

Here we list results on underlying building blocks, and the hash function modified by other means than the security parameter.

Note that these results assume more direct control or access over some internal variables (aka. free-start, pseudo, compression function, block cipher, or permutation attacks).

 Type of Analysis Hash Function Part Hash Size (n) Parameters/Variants Compression Function Calls Memory Requirements Reference observations hash 256 (2,5,13) - - Gauravaram et al. meet-in-the-middle preimage hash 256 (2,5,13) 2416 2416 Gauravaram et al. distinguisher output transformation 256 (2,5,11.5), keyed 28 - Gauravaram et al. semi-free-start collision compression function 256 (2,1,5) example - Turan,Uyan semi-free-start near-collision compression function 256 (2,2,10) example - Turan,Uyan distinguisher(1) output transformation 256 1 - Aumasson,Phan distinguisher output transformation 256 (2,5,0.5), keyed 28 - Aumasson,Phan internal collision hash function 256 (2,5,13) 2352 2352 Khovratovich internal collision hash function 512 (4,8,13) 2480 2480 Khovratovich

(1)The Fugue team commented on these distinguishers in this note using this figure.

Praveen Gauravaram, Lars R.Knudsen, Nasour Bagher, Lei Wei - Improved Security Analysis of Fugue-256 (a second round SHA-3 candidate)
Proceedings of ACISP (short paper), 2011, 2011
[Electronic Edition] [Bibtex]
Author : Praveen Gauravaram, Lars R.Knudsen, Nasour Bagher, Lei Wei
Title : Improved Security Analysis of Fugue-256 (a second round SHA-3 candidate)
In : Proceedings of ACISP (short paper), 2011 -
[Abstract]

Meltem Sönmez Turan, Erdener Uyan - Practical Near-Collisions for Reduced Round Blake, Fugue, Hamsi and JH
Second SHA-3 Candidate Conference, 2010
[Electronic Edition] [Bibtex]
Author : Meltem Sönmez Turan, Erdener Uyan
Title : Practical Near-Collisions for Reduced Round Blake, Fugue, Hamsi and JH
In : Second SHA-3 Candidate Conference -
[Abstract]

Jean-Philippe Aumasson, Raphael C.-W. Phan - Analysis of Fugue-256
Posting to NIST hash mailing list, 2010
[Electronic Edition] [Bibtex]
Author : Jean-Philippe Aumasson, Raphael C.-W. Phan
Title : Analysis of Fugue-256
In : Posting to NIST hash mailing list -
[Abstract]

Dmitry Khovratovich - Cryptanalysis of hash functions with structures
Proceedings of Selected Areas in Cryptography, 2009
[Electronic Edition] [Bibtex]
Author : Dmitry Khovratovich
Title : Cryptanalysis of hash functions with structures
In : Proceedings of Selected Areas in Cryptography -
[Abstract]