Tiger - Revision history

Fmendel: Preimage Attacks on Reduced Tiger and SHA-2

2009-09-18T13:10:25Z

Preimage Attacks on Reduced Tiger and SHA-2

Fmendel: Preimages for Reduced-Round Tiger

2009-07-16T12:49:46Z

Preimages for Reduced-Round Tiger

Fmendel: Two Passes of Tiger Are Not One-Way

2009-07-09T11:41:44Z

Two Passes of Tiger Are Not One-Way

Fmendel: /* Best Known Results */

2008-03-11T10:57:25Z

‎Best Known Results

Fmendel: /* Collision Attacks */

2008-03-11T10:06:28Z

‎Collision Attacks

Fmendel: /* Collision Attacks */

2008-03-11T10:05:33Z

‎Collision Attacks

Tnad: /* Collision Attacks */

2008-03-11T08:16:45Z

‎Collision Attacks

Tnad: /* Collision Attacks */

2008-03-11T08:14:25Z

‎Collision Attacks

Fmendel: /* Specification */

2008-03-11T07:41:11Z

‎Specification

Fmendel at 16:31, 10 March 2008

2008-03-10T16:31:14Z

← Older revision		Revision as of 13:10, 18 September 2009
Line 112:		Line 112:

	=== Preimage Attacks ===		=== Preimage Attacks ===
		+
		+	<bibtex>
		+	@INPROCEEDINGS{fseIsobeS09,
		+	author = {Takanori Isobe and Kyoji Shibutani},
		+	title = {Preimage Attacks on Reduced Tiger and SHA-2},
		+	booktitle = {Fast Software Encryption},
		+	year = {2009},
		+	editor = {Dunkelman, Orr},
		+	volume = {5665},
		+	series = {LNCS},
		+	pages = {139-155},
		+	publisher = {Springer},
		+	url = {http://dx.doi.org/10.1007/978-3-642-03317-9}
		+	abstract = {This paper shows new preimage attacks on reduced Tiger and SHA-2.
		+	Indesteege and Preneel presented a preimage attack on Tiger reduced
		+	to 13 rounds (out of 24) with a complexity of 2^{128.5}. Our new
		+	preimage attack finds a one-block preimage of Tiger reduced to 16
		+	rounds with a complexity of 2^{161}. The proposed attack is based
		+	on meet-in-the-middle attacks. It seems difficult to find “independent
		+	words” of Tiger at first glance, since its key schedule function
		+	is much more complicated than that of MD4 or MD5. However, we developed
		+	techniques to find independent words efficiently by controlling its
		+	internal variables. Surprisingly, the similar techniques can be applied
		+	to SHA-2 including both SHA-256 and SHA-512. We present a one-block
		+	preimage attack on SHA-256 and SHA-512 reduced to 24 (out of 64 and
		+	80) steps with a complexity of 2^{240} and 2^{480}, respectively.
		+	To the best of our knowledge, our attack is the best known preimage
		+	attack on reduced-round Tiger and our preimage attack on reduced-step
		+	SHA-512 is the first result. Furthermore, our preimage attacks can
		+	also be extended to second preimage attacks directly, because our
		+	attacks can obtain random preimages from an arbitrary IV and an arbitrary
		+	target.},
		+	}
		+	</bibtex>

	<bibtex>		<bibtex>

@@ Line 128: / Line 128: @@
 In this article, we show a preimage attack on Tiger with two passes (16 rounds) with a complexity of about 2^174 compression function evaluations. Furthermore, we show how the attack can be extended to 17 rounds with a complexity of about 2^185. Even though the attacks are only slightly faster than brute force search, they present a step forward in the cryptanalysis of Tiger.
+}
 </bibtex>

@@ Line 113: / Line 113: @@
 === Preimage Attacks ===
 ----
 === Others ===

@@ Line 36: / Line 36: @@
 === Best Known Results ===
-The best Known attack is a 1-bit circular pseudo-near-collision for Tiger with a complexity of about 2<sup>47</sup> of Mendel and Rijmen. The best collision attack on Tiger was presented by Mendel et al. for Tiger reduced to 19 out of 24 rounds. The attack has a complexity of about 2<sup>62</sup>.
+The best known attack is a 1-bit circular pseudo-near-collision for Tiger with a complexity of about 2<sup>47</sup> of Mendel and Rijmen. The best collision attack on Tiger was presented by Mendel et al. for Tiger reduced to 19 out of 24 rounds. The attack has a complexity of about 2<sup>62</sup>.
 ----

@@ Line 77: / Line 77: @@
    volume    = {4329},
    isbn      = {3-540-49767-6},
-   abstract  = {Tiger is a cryptographic hash function with a 192-bit hash value which was proposed by Anderson and Biham in 1996. At FSE 2006, Kelsey and Lucks presented a collision attack on Tiger reduced to 16 (out of 24) rounds with complexity of about 244. Furthermore, they showed that a pseudo-near-collision can be found for a variant of Tiger with 20 rounds with complexity of about 248. In this article, we show how their attack method can be extended to construct a collision in the Tiger hash function reduced to 19 rounds. We present two different attack strategies for constructing collisions in Tiger-19 with complexity of about 262 and 269. Furthermore, we present a pseudo-near-collision for a variant of Tiger with 22 rounds with complexity of about 244.},
+   abstract  = {Tiger is a cryptographic hash function with a 192-bit hash value which was proposed by Anderson and Biham in 1996. At FSE 2006, Kelsey and Lucks presented a collision attack on Tiger reduced to 16 (out of 24) rounds with complexity of about 2^{44}. Furthermore, they showed that a pseudo-near-collision can be found for a variant of Tiger with 20 rounds with complexity of about 2^{48}. In this article, we show how their attack method can be extended to construct a collision in the Tiger hash function reduced to 19 rounds. We present two different attack strategies for constructing collisions in Tiger-19 with complexity of about 2^{62} and 2^{69}. Furthermore, we present a pseudo-near-collision for a variant of Tiger with 22 rounds with complexity of about 2^{44}.},
+}
 </bibtex>

@@ Line 61: / Line 61: @@
    url        = {http://dx.doi.org/10.1007/978-3-540-76900-2_33},
    abstract  = {Tiger is a cryptographic hash function with a 192-bit hash value. It was proposed by Anderson and Biham in 1996. Recently, weaknesses have been shown in round-reduced variants of the Tiger hash function. First, at FSE 2006, Kelsey and Lucks presented a collision attack on Tiger reduced to 16 and 17 (out of 24) rounds with a complexity of about $2^44$ and a pseudo-near-collision for Tiger reduced to 20 rounds. Later, Mendel et al. extended this attack to a collision attack on Tiger reduced to 19 rounds with a complexity of about $2^62$. Furthermore, they show a pseudo-near-collision for Tiger reduced to 22 rounds with a complexity of about $2^44$. No attack is known for the full Tiger hash function. In this article, we show a pseudo-near-collision for the full Tiger hash function with a complexity of about $2^47$ hash computations and a pseudo-collision (free-start-collision) for Tiger reduced to 23 rounds with the same complexity.},
+}
 </bibtex>

@@ Line 66: / Line 66: @@
 <bibtex>
 @inproceedings{fseKelseyL06,
    author    = {John Kelsey and Stefan Lucks},
    title     = {Collisions and Near-Collisions for Reduced-Round Tiger},

← Older revision		Revision as of 08:14, 11 March 2008
Line 64:		Line 64:
	</bibtex>		</bibtex>

		+	<bibtex>
		+	@inproceedings{fseKelseyL06,
		+	owner = {tnad},
		+	author = {John Kelsey and Stefan Lucks},
		+	title = {Collisions and Near-Collisions for Reduced-Round Tiger},
		+	pages = {111-125},
		+	url = {http://dx.doi.org/10.1007/11799313_8},
		+	booktitle = {FSE},
		+	publisher = {Springer},
		+	series = {LNCS},
		+	volume = {4047},
		+	year = {2006},
		+	isbn = {3-540-36597-4},
		+	abstract = {We describe a collision-finding attack on 16 rounds of the
		+	Tiger hash function requiring the time for about 244 compression function
		+	invocations. This extends to a collision-finding attack on 17 rounds of the
		+	Tiger hash function in time of about 249 compression function invocations.
		+	Another attack generates circular near-collisions, for 20 rounds of Tiger
		+	with work less than that of 249 compression function invocations. Since Tiger
		+	has only 24 rounds, these attacks may raise some questions about the security
		+	of Tiger. In developing these attacks, we adapt the ideas of message modification
		+	attacks and neutral bits, developed in the analysis of MD4 family hashes,
		+	to a completely different hash function design.},
		+	}
		+	</bibtex>
	----		----

@@ Line 5: / Line 5: @@
 * max. message length: < 2<sup>64</sup> bits
 * compression function: 512-bit message block, 192-bit chaining variable
-* Specification:
+* Specification: [http://www.cs.technion.ac.il/~biham/Reports/Tiger/ Tiger: A Fast New Cryptographic Hash Function]
 <bibtex>
   @inproceedings{fseAndersonB96,

@@ Line 35: / Line 35: @@
 === Best Known Results ===
 ----
@@ Line 44: / Line 46: @@
 === Collision Attacks ===
 ----