Fugue

1 The algorithm

• Author(s): Shai Halevi and William E. Hall and Charanjit S. Jutla
• Website: http://domino.research.ibm.com/comm/research_projects.nsf/pages/fugue.index.html
• NIST submission package:
  • round 1/2: Fugue_Round2_Update.zip (old versions: Fugue.zip, FugueUpdate.zip, Fugue_Round2.zip)

Shai Halevi, William E. Hall, Charanjit S. Jutla - The Hash Function Fugue

,2009

http://domino.research.ibm.com/comm/research_projects.nsf/pages/fugue.index.html/$FILE/fugue_09.pdf
Bibtex

Author : Shai Halevi, William E. Hall, Charanjit S. Jutla
Title : The Hash Function Fugue
In : -
Address :
Date : 2009

Shai Halevi, William E. Hall, Charanjit S. Jutla - The Hash Function Fugue

,2008

http://domino.research.ibm.com/comm/research_projects.nsf/pages/fugue.index.html/$FILE/NIST-submission-Oct08-fugue.pdf
Bibtex

Author : Shai Halevi, William E. Hall, Charanjit S. Jutla
Title : The Hash Function Fugue
In : -
Address :
Date : 2008

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
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
internal collision	hash function	256	(2,5,13)	2352	2352	Khovratovich
internal collision	hash function	512	(4,8,13)	2480	2480	Khovratovich

⁽¹⁾The Fugue team commented on these distinguishers in this note using this figure.

Meltem Sönmez Turan, Erdener Uyan - Practical Near-Collisions for Reduced Round Blake, Fugue, Hamsi and JH

,2010

http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/TURAN_Paper_Erdener.pdf
Bibtex

Author : Meltem Sönmez Turan, Erdener Uyan
Title : Practical Near-Collisions for Reduced Round Blake, Fugue, Hamsi and JH
In : -
Address :
Date : 2010

Jean-Philippe Aumasson, Raphael C.-W. Phan - Analysis of Fugue-256

,2010

http://ehash.iaik.tugraz.at/uploads/c/cd/Fugue_path.pdf
Bibtex

Author : Jean-Philippe Aumasson, Raphael C.-W. Phan
Title : Analysis of Fugue-256
In : -
Address :
Date : 2010

Dmitry Khovratovich - Cryptanalysis of hash functions with structures

,2009

http://cryptolux.org/mediawiki/uploads/9/99/Struct2.pdf
Bibtex

Author : Dmitry Khovratovich
Title : Cryptanalysis of hash functions with structures
In : -
Address :
Date : 2009