Difference between revisions of "Fugue"

From The ECRYPT Hash Function Website
m
(Cryptanalysis updated)
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  
 +
|-                 
 +
| 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 near-collision || compression function || 256 || (2,2,10) || example || - || [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/TURAN_Paper_Erdener.pdf Turan,Uyan]
 
|-                   
 
|-                   
 
| distinguisher<sup>(1)</sup> || output transformation || 256 ||    || 1  || - || [http://ehash.iaik.tugraz.at/uploads/c/cd/Fugue_path.pdf Aumasson,Phan]
 
| distinguisher<sup>(1)</sup> || output transformation || 256 ||    || 1  || - || [http://ehash.iaik.tugraz.at/uploads/c/cd/Fugue_path.pdf Aumasson,Phan]
Line 68: Line 72:
 
<sup>(1)</sup>The Fugue team commented on these distinguishers in [http://ehash.iaik.tugraz.at/uploads/d/d7/Fugue_designers_reply_to_AumassonPhan_Distinguisher.txt this note] using [http://ehash.iaik.tugraz.at/uploads/c/c8/Fig7.pdf this figure].
 
<sup>(1)</sup>The Fugue team commented on these distinguishers in [http://ehash.iaik.tugraz.at/uploads/d/d7/Fugue_designers_reply_to_AumassonPhan_Distinguisher.txt this note] using [http://ehash.iaik.tugraz.at/uploads/c/c8/Fig7.pdf this figure].
  
 +
 +
<bibtex>
 +
@misc{nistTU10,
 +
  author = {Meltem Sönmez Turan, Erdener Uyan},
 +
  title = {Practical Near-Collisions for Reduced Round Blake, Fugue, Hamsi and JH},
 +
  howpublished = {Second SHA-3 Candidate Conference},
 +
  year = {2010},
 +
  url = {http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/TURAN_Paper_Erdener.pdf},
 +
  abstract = {A hash function is near-collision resistant, if it is hard to find two messages with hash values that differ in only a small number of bits. In this study, we use hill climbing methods to evaluate the near-collision resistance of some of the round SHA-3 candidates. We practically obtained (i) 184/256-bit near-collision for the 2-round compression function of Blake-32; (ii) 192/256-bit near-collision for the 2-round compression function of Hamsi-256; (iii) 820/1024-bit near-collisions for 10-round compression function of JH. We also observed practical collisions and near-collisions for reduced versions of F-256 function used in Fugue.}
 +
}
 +
</bibtex>
  
 
<bibtex>
 
<bibtex>
Line 78: Line 93:
 
     abstract = {We would like to report our analysis results on the final round algorithm of
 
     abstract = {We would like to report our analysis results on the final round algorithm of
 
Fugue-256 (i.e., the function called "G"):
 
Fugue-256 (i.e., the function called "G"):
−
 
 
The attached pdf note shows an example differential characteristic of
 
The attached pdf note shows an example differential characteristic of
 
probability 1, on 15 intermediate rounds of G, as well as an extended
 
probability 1, on 15 intermediate rounds of G, as well as an extended
Line 84: Line 98:
 
18-round G. It also shows how differences propagate on an
 
18-round G. It also shows how differences propagate on an
 
augmented-round version of G (i.e. if more G2 rounds were added).
 
augmented-round version of G (i.e. if more G2 rounds were added).
−
 
 
A detailed analysis as well as further observations will be reported
 
A detailed analysis as well as further observations will be reported
 
in a subsequent paper.
 
in a subsequent paper.
Line 90: Line 103:
 
}
 
}
 
</bibtex>
 
</bibtex>
−
 
−
 
  
 
<bibtex>
 
<bibtex>

Revision as of 19:02, 6 December 2010

1 The algorithm


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

(1)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
Retrieved from "https://ehash.iaik.tugraz.at/index.php?title=Fugue&oldid=3646"