Difference between revisions of "Fugue"
m |
Crechberger (talk | contribs) (added SAC2009 paper) |
||
| Line 45: | Line 45: | ||
| Type of Analysis || Hash Size (n) || Parameters || Compression Function Calls || Memory Requirements || Reference | | Type of Analysis || Hash Size (n) || Parameters || Compression Function Calls || Memory Requirements || Reference | ||
|- | |- | ||
| − | | || || || || || | + | | internal collision || 256 || (2,5,13) || 2<sup>352</sup> || 2<sup>352</sup> || [http://cryptolux.org/mediawiki/uploads/9/99/Struct2.pdf Khovratovich] |
| − | |- | + | |- |
| + | | internal collision || 512 || (4,8,13) || 2<sup>480</sup> || 2<sup>480</sup> || [http://cryptolux.org/mediawiki/uploads/9/99/Struct2.pdf Khovratovich] | ||
| + | |- | ||
|} | |} | ||
| Line 63: | Line 65: | ||
|- | |- | ||
|} | |} | ||
| + | |||
| + | |||
| + | <bibtex> | ||
| + | @misc{sacKhovratovich09, | ||
| + | author = {Dmitry Khovratovich}, | ||
| + | title = {Cryptanalysis of hash functions with structures}, | ||
| + | howpublished = {Proceedings of Selected Areas in Cryptography}, | ||
| + | year = {2009}, | ||
| + | url = {http://cryptolux.org/mediawiki/uploads/9/99/Struct2.pdf}, | ||
| + | abstract = {Hash function cryptanalysis has acquired many methods, | ||
| + | tools and tricks from other areas, mostly block ciphers. In this paper | ||
| + | another trick from block cipher cryptanalysis, the structures, is used for | ||
| + | speeding up the collision search. We investigate the memory and the time | ||
| + | complexities of this approach under different assumptions on the round | ||
| + | functions. The power of the new attack is illustrated with the crypt- | ||
| + | analysis of the hash functions Grindahl and the analysis of the SHA-3 | ||
| + | candidate Fugue (both functions as 256 and 512 bit versions). The collision attack on Grindahl-512 is the first collision attack on this function. | ||
| + | }, | ||
| + | } | ||
| + | </bibtex> | ||
Revision as of 17:52, 12 April 2010
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.
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.
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)
| Type of Analysis | Hash Size (n) | Parameters | Compression Function Calls | Memory Requirements | Reference |
| internal collision | 256 | (2,5,13) | 2352 | 2352 | Khovratovich |
| internal collision | 512 | (4,8,13) | 2480 | 2480 | Khovratovich |
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 |
Dmitry Khovratovich - Cryptanalysis of hash functions with structures
