# Difference between revisions of "Fugue"

Mschlaeffer (talk | contribs) |
(→Building blocks: added Gauravaram et al. results) |
||

(19 intermediate revisions by 4 users not shown) | |||

Line 3: | Line 3: | ||

* Author(s): Shai Halevi and William E. Hall and Charanjit S. Jutla | * 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 http://domino.research.ibm.com/comm/research_projects.nsf/pages/fugue.index.html] | * Website: [http://domino.research.ibm.com/comm/research_projects.nsf/pages/fugue.index.html http://domino.research.ibm.com/comm/research_projects.nsf/pages/fugue.index.html] | ||

− | * | + | * NIST submission package: |

+ | ** round 1/2: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/documents/Fugue_Round2_Update.zip Fugue_Round2_Update.zip] (old versions: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/Fugue.zip Fugue.zip], [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/FugueUpdate.zip FugueUpdate.zip], [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/documents/Fugue_Round2.zip Fugue_Round2.zip]) | ||

+ | |||

+ | |||

+ | <bibtex> | ||

+ | @misc{sha3Halevi09, | ||

+ | author = {Shai Halevi and William E. Hall and Charanjit S. Jutla}, | ||

+ | title = {The Hash Function Fugue}, | ||

+ | url = {http://domino.research.ibm.com/comm/research_projects.nsf/pages/fugue.index.html/$FILE/fugue_09.pdf}, | ||

+ | howpublished = {Submission to NIST (updated)}, | ||

+ | year = {2009}, | ||

+ | } | ||

+ | </bibtex> | ||

<bibtex> | <bibtex> | ||

Line 12: | Line 24: | ||

howpublished = {Submission to NIST}, | howpublished = {Submission to NIST}, | ||

year = {2008}, | year = {2008}, | ||

+ | } | ||

+ | </bibtex> | ||

+ | |||

+ | |||

+ | == 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 [http://ehash.iaik.tugraz.at/wiki/Cryptanalysis_Categories#Individual_Hash_Function_Tables 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) | ||

+ | |||

+ | === 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. | ||

+ | |||

+ | {| border="1" cellpadding="4" cellspacing="0" class="wikitable sortable" style="text-align:center" | ||

+ | |- style="background:#efefef;" | ||

+ | | Type of Analysis || Hash Size (n) || Parameters || Compression Function Calls || Memory Requirements || Reference | ||

+ | |- | ||

+ | | || |||| || || | ||

+ | |- | ||

+ | |} | ||

+ | |||

+ | |||

+ | === 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). | ||

+ | |||

+ | {| border="1" cellpadding="4" cellspacing="0" class="wikitable sortable" style="text-align:center" | ||

+ | |- style="background:#efefef;" | ||

+ | | 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 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 || output transformation || 256 || (2,5,0.5), keyed || 2<sup>8</sup> || - || [http://ehash.iaik.tugraz.at/uploads/c/cd/Fugue_path.pdf Aumasson,Phan] | ||

+ | |- | ||

+ | | internal collision || hash function || 256 || (2,5,13) || 2<sup>352</sup> || 2<sup>352</sup> || [http://cryptolux.org/mediawiki/uploads/9/99/Struct2.pdf Khovratovich] | ||

+ | |- | ||

+ | | internal collision || hash function || 512 || (4,8,13) || 2<sup>480</sup> || 2<sup>480</sup> || [http://cryptolux.org/mediawiki/uploads/9/99/Struct2.pdf Khovratovich] | ||

+ | |- | ||

+ | |} | ||

+ | <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{fugueGKBW11, | ||

+ | author = {Praveen Gauravaram and Lars R.Knudsen and Nasour Bagher and Lei Wei}, | ||

+ | title = {Improved Security Analysis of Fugue-256 (a second round SHA-3 candidate)}, | ||

+ | howpublished = {Proceedings of ACISP (short paper), 2011}, | ||

+ | year = {2011}, | ||

+ | url = {http://www2.mat.dtu.dk/pg-projects/Fugue-256-analysis-v1.pdf}, | ||

+ | abstract = {Fugue is a cryptographic hash function designed by Halevi, Hall and Jutla and was one of the fourteen hash algorithms of the second round of NIST's SHA3 hash competition. We consider Fugue-256, the 256-bit instance of Fugue. Fugue-256 updates a state of 960 bits with a \textit{round transformation} \textbf{R} parametrized by a 32-bit message word. Twice in every state update, this transform invokes an AES like round function called \textbf{SMIX}. Fugue-256 relies on a \textit{final transformation} \textbf{G} to output digests that look random. \textbf{G} has 18 rounds where each round invokes \textbf{SMIX} twice and finally the 960-bit output of the \textbf{G} transform is mapped with a transform $\tau$ to a 256-bit digest. \\ In this paper, we present some improved as well as new analytical results of Fugue-256 (with length-padding). First we improve Aumasson and Phans' integral distinguisher on the 5.5 rounds of the \textbf{G} transform to 16.5 rounds, thus showing \textit{weak} diffusion in the \textbf{G} transform. Next we improve the designers' meet-in-the-middle preimage attack on Fugue-256 from $2^{480}$ time and memory to $2^{416}$. Next we study the security of Fugue-256 against free-start distinguishers and free-start collisions. In this direction, we use an improved variant of the differential characteristic of the \textbf{G} transform shown by the designers to present an efficient distinguisher for the $\tau(\mathbf{G})(.)$ transform showing another \textit{weak} diffusion property of \textbf{G}. We then extend this distinguisher to some interesting practical free-start distinguishers and free-start collisions for the length padded Fugue-256 in $2^{33}$ complexity. Finally, we show that free-start collision attacks on the length-padded Fugue-256 can be found in just $\mathcal{O}(1)$ \textit{without} relying on the differential properties of the \textbf{G} transform and even \textit{without} inverting it.} | ||

+ | } | ||

+ | </bibtex> | ||

+ | |||

+ | <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> | ||

+ | @misc{nistAP10, | ||

+ | author = {Jean-Philippe Aumasson and Raphael C.-W. Phan}, | ||

+ | title = {Analysis of Fugue-256}, | ||

+ | howpublished = {Posting to NIST hash mailing list}, | ||

+ | year = {2010}, | ||

+ | url = {http://ehash.iaik.tugraz.at/uploads/c/cd/Fugue_path.pdf}, | ||

+ | abstract = {We would like to report our analysis results on the final round algorithm of | ||

+ | Fugue-256 (i.e., the function called "G"): | ||

+ | The attached pdf note shows an example differential characteristic of | ||

+ | probability 1, on 15 intermediate rounds of G, as well as an extended | ||

+ | characteristic that can be used as a distinguisher for the full | ||

+ | 18-round G. It also shows how differences propagate on an | ||

+ | augmented-round version of G (i.e. if more G2 rounds were added). | ||

+ | A detailed analysis as well as further observations will be reported | ||

+ | in a subsequent paper. | ||

+ | }, | ||

+ | } | ||

+ | </bibtex> | ||

+ | |||

+ | <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> | </bibtex> |

## Latest revision as of 08: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

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 |

observations | hash | 256 | (2,5,13) | - | - | Gauravaram et al. |

meet-in-the-middle preimage | hash | 256 | (2,5,13) | 2^{416} |
2^{416} |
Gauravaram et al. |

distinguisher | output transformation | 256 | (2,5,11.5), keyed | 2^{8} |
- | 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 | 2^{8} |
- | Aumasson,Phan |

internal collision | hash function | 256 | (2,5,13) | 2^{352} |
2^{352} |
Khovratovich |

internal collision | hash function | 512 | (4,8,13) | 2^{480} |
2^{480} |
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

Bibtex**Author :**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

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**