Fugue
From The ECRYPT Hash Function Website
Contents |
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)
- 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.
- Proceedings of ACISP (short paper), 2011, 2011
- [Electronic Edition] [Bibtex] Author : Praveen Gauravaram, Lars R.Knudsen, Nasour Bagher, Lei Wei[Abstract]
Title : Improved Security Analysis of Fugue-256 (a second round SHA-3 candidate)
In : Proceedings of ACISP (short paper), 2011 -
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[Abstract]
Title : Practical Near-Collisions for Reduced Round Blake, Fugue, Hamsi and JH
In : Second SHA-3 Candidate Conference -
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[Abstract]
Title : Analysis of Fugue-256
In : Posting to NIST hash mailing list -
Dmitry Khovratovich - Cryptanalysis of hash functions with structures
- Proceedings of Selected Areas in Cryptography, 2009
- [Electronic Edition] [Bibtex] Author : Dmitry Khovratovich[Abstract]
Title : Cryptanalysis of hash functions with structures
In : Proceedings of Selected Areas in Cryptography -
