Fugue - Revision history

JAumasson: /* Building blocks */ added Gauravaram et al. results

2011-07-12T07:05:41Z

‎Building blocks: added Gauravaram et al. results

JAumasson: /* Building blocks */ added Gauravaram et al. bib item

2011-07-12T06:52:19Z

‎Building blocks: added Gauravaram et al. bib item

JAumasson: added missing Aumasson/Phan result

2011-01-12T07:46:26Z

added missing Aumasson/Phan result

Mschlaeffer: Cryptanalysis updated

2010-12-06T17:02:15Z

Cryptanalysis updated

Fmendel at 12:55, 5 July 2010

2010-07-05T12:55:03Z

Crechberger: Added Aumasson/Phan distinguisher of output transformation

2010-06-21T11:10:20Z

Added Aumasson/Phan distinguisher of output transformation

JAumasson: typo

2010-04-30T07:00:40Z

typo

JAumasson: moved DK's results to the bottom table (as isnt "according to NIST's req..").

2010-04-29T07:39:57Z

moved DK's results to the bottom table (as isnt "according to NIST's req..").

JAumasson: correct placement of rec sec par

2010-04-29T07:10:34Z

correct placement of rec sec par

Crechberger: added SAC2009 paper

2010-04-12T15:52:51Z

added SAC2009 paper

@@ Line 58: / Line 58: @@
 |- style="background:#efefef;"
 | 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]
 |-

← Older revision		Revision as of 06:52, 12 July 2011
Line 74:		Line 74:
	<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{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>		<bibtex>

@@ Line 64: / Line 64: @@
 |-
 | distinguisher<sup>(1)</sup> || output transformation || 256 ||    || 1  || - || [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]
 |-

@@ Line 58: / Line 58: @@
 |- style="background:#efefef;"
 | Type of Analysis || Hash Function Part || Hash Size (n) || Parameters/Variants || Compression Function Calls || Memory Requirements ||   Reference
 |-
 | 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].
 <bibtex>
@@ Line 78: / Line 93: @@
      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
@@ Line 84: / Line 98: @@
 -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.
@@ Line 90: / Line 103: @@
+}
 </bibtex>
 <bibtex>

@@ Line 40: / Line 40: @@
 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" style="text-align:center"
+{| 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
@@ Line 55: / Line 55: @@
 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" style="text-align:center"
+{| 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

@@ Line 59: / Line 59: @@
 | Type of Analysis || Hash Function Part || Hash Size (n) || Parameters/Variants || Compression Function Calls || Memory Requirements ||   Reference
 |-
-| internal collision || hash functoin || 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 || 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]

@@ Line 34: / Line 34: @@
 A description of the tables is given [http://ehash.iaik.tugraz.at/wiki/Cryptanalysis_Categories#Individual_Hash_Function_Tables here].
 === 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" style="text-align:center"

@@ Line 45: / Line 45: @@
 | 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]
 |-
 |}
@@ Line 63: / Line 65: @@
 |-
 |}