Difference between revisions of "Fugue"
m (→Building blocks: added Gauravaram et al. bib item) |
(→Building blocks: added Gauravaram et al. results) |
||
| Line 58: | Line 58: | ||
|- style="background:#efefef;" | |- style="background:#efefef;" | ||
| Type of Analysis || Hash Function Part || Hash Size (n) || Parameters/Variants || Compression Function Calls || Memory Requirements || Reference | | Type of Analysis || Hash Function Part || Hash Size (n) || Parameters/Variants || Compression Function Calls || Memory Requirements || Reference | ||
| − | |- | + | |- |
| + | | observations || hash || 256 || (2,5,13) || - || - || [http://www2.mat.dtu.dk/pg-projects/Fugue-256-analysis-v1.pdf Gauravaram et al.] | ||
| + | |- | ||
| + | | meet-in-the-middle preimage || hash || 256 || (2,5,13) || 2<sup>416</sup> || 2<sup>416</sup> || [http://www2.mat.dtu.dk/pg-projects/Fugue-256-analysis-v1.pdf Gauravaram et al.] | ||
| + | |- | ||
| + | | distinguisher || output transformation || 256 || (2,5,11.5), keyed || 2<sup>8</sup> || - || [http://www2.mat.dtu.dk/pg-projects/Fugue-256-analysis-v1.pdf Gauravaram et al.] | ||
| + | |- | ||
| semi-free-start collision || compression function || 256 || (2,1,5) || example || - || [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/TURAN_Paper_Erdener.pdf Turan,Uyan] | | semi-free-start collision || compression function || 256 || (2,1,5) || example || - || [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/TURAN_Paper_Erdener.pdf Turan,Uyan] | ||
|- | |- | ||
Latest revision as of 09:05, 12 July 2011
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
BibtexAuthor : 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
BibtexAuthor : 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 |
| 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)
- ,2011
- http://www2.mat.dtu.dk/pg-projects/Fugue-256-analysis-v1.pdf
BibtexAuthor : Praveen Gauravaram, Lars R.Knudsen, Nasour Bagher, Lei Wei
Title : Improved Security Analysis of Fugue-256 (a second round SHA-3 candidate)
In : -
Address :
Date : 2011
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
BibtexAuthor : 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
BibtexAuthor : Jean-Philippe Aumasson, Raphael C.-W. Phan
Title : Analysis of Fugue-256
In : -
Address :
Date : 2010
Dmitry Khovratovich - Cryptanalysis of hash functions with structures
