Difference between revisions of "Tiger"

From The ECRYPT Hash Function Website
 
m (Preimage Attacks on Reduced Tiger and SHA-2)
 
(15 intermediate revisions by 2 users not shown)
Line 1: Line 1:
−
{{Template:HashFunctions}}
+
== Specification ==
 +
 
 +
 
 +
* digest size: 192/160/128 bits
 +
* max. message length: < 2<sup>64</sup> bits
 +
* compression function: 512-bit message block, 192-bit chaining variable
 +
* Specification: [http://www.cs.technion.ac.il/~biham/Reports/Tiger/ Tiger: A Fast New Cryptographic Hash Function]
 +
<bibtex>
 +
@inproceedings{fseAndersonB96,
 +
  author    = {Ross J. Anderson and Eli Biham},
 +
  title    = {TIGER: A Fast New Hash Function},
 +
  pages    = {89-97},
 +
  editor    = {Dieter Gollmann},
 +
  booktitle = {FSE},
 +
  publisher = {Springer},
 +
  series    = {LNCS},
 +
  volume    = {1039},
 +
  year      = {1996},
 +
  isbn      = {3-540-60865-6},
 +
  abstract  = {Among those cryptographic hash function which are not based on block ciphers,
 +
              MD4 and Snefru seemed initially quite attractive for applications requiring fast
 +
              software hashing. However collisions for Snefru were found in 1990, and recently a collision of MD4
 +
              was also found. This casts doubt on how long these functions' variants, such as
 +
              RIPE-MD, MD5, SHA, SHA1 and Snefru-8, will remain unbroken. Furthermore, all
 +
              these functions were designed for 32-bit processors, and cannot be implemented
 +
              efficiently on the new generation of 64-bit processors such as the DEC Alpha.
 +
              We therefore present a new hash function which we believe to be secure; it is
 +
              designed to run quickly on 64-bit processors, without being too slow on existing machines.},
 +
  url      = {http://dx.doi.org/10.1007/3-540-60865-6}
 +
}
 +
</bibtex>
 +
 
 +
== Cryptanalysis ==
 +
 
 +
 
 +
=== 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>.
 +
 
 +
----
 +
 
 +
=== Generic Attacks ===
 +
* [[GenericAttacksMerkleDamgaard| Generic Attacks on the Merkle-Damgaard Construction ]]
 +
 
 +
----
 +
 
 +
=== Collision Attacks ===
 +
 
 +
<bibtex>
 +
@inproceedings{asiacryptMendelR07,
 +
  author    = {Florian Mendel and Vincent Rijmen},
 +
  title    = {Cryptanalysis of the Tiger Hash Function},
 +
  booktitle = {ASIACRYPT},
 +
  year      = {2007},
 +
  editor    = {Kaoru Kurosawa},
 +
  publisher = {Springer},
 +
  series    = {LNCS},
 +
  volume    = {4833},
 +
  isbn      = {978-3-540-76899-9},
 +
  pages    = {536-550},
 +
  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>
 +
 
 +
<bibtex>
 +
@inproceedings{indocryptMendelPRYW06,
 +
  author    = {Florian Mendel and Bart Preneel and Vincent Rijmen and Hirotaka Yoshida and Dai Watanabe},
 +
  title    = {Update on Tiger},
 +
  booktitle = {INDOCRYPT},
 +
  year      = {2006},
 +
  pages    = {63-79},
 +
  url        = {http://dx.doi.org/10.1007/11941378_6},
 +
  editor    = {Rana Barua and Tanja Lange},
 +
  publisher = {Springer},
 +
  series    = {LNCS},
 +
  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 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>
 +
 
 +
<bibtex>
 +
@inproceedings{fseKelseyL06,
 +
  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>
 +
----
 +
 
 +
=== Second 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>
 +
@inproceedings{africacryptMendel09,
 +
  author    = {Florian Mendel},
 +
  title    = {Two Passes of Tiger Are Not One-Way},
 +
  year      = {2009},
 +
  pages    = {29-40},
 +
  url        = {http://dx.doi.org/10.1007/978-3-642-02384-2_3},
 +
  publisher  = {Springer},
 +
  series    = {LNCS},
 +
  booktitle = {AFRICACRYPT},
 +
  publisher = {Springer},
 +
  volume    = {5580},
 +
  abstract = {Tiger is a cryptographic hash function proposed by Anderson and Biham in 1996 and produces a 192-bit hash value. Recently, weaknesses have been shown in round-reduced variants of the Tiger hash function. Collision attacks have been presented for Tiger reduced to 16 and 19 (out of 24) rounds at FSE 2006 and Indocrypt 2006. Furthermore, Mendel and Rijmen presented a 1-bit pseudo-near-collision for the full Tiger hash function at ASIACRYPT 2007. The attack has a complexity of about 2^47 compression function evaluations. While there exist several collision-style attacks for Tiger, the picture is different for preimage attacks. At WEWoRC 2007, Indesteege and Preneel presented a preimage attack on Tiger reduced to 12 and 13 rounds with a complexity of 2^64.5 and 2^128.5, respectively.
 +
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>
 +
 
 +
<bibtex>
 +
@inproceedings{DBLP:conf/weworc/IndesteegeP07,
 +
  author    = {Sebastiaan Indesteege and
 +
              Bart Preneel},
 +
  title    = {Preimages for Reduced-Round Tiger},
 +
  year      = {2007},
 +
  pages    = {90-99},
 +
  url        = {http://dx.doi.org/10.1007/978-3-540-88353-1_8},
 +
  editor    = {Stefan Lucks and
 +
              Ahmad-Reza Sadeghi and
 +
              Christopher Wolf},
 +
  booktitle = {WEWoRC},
 +
  publisher = {Springer},
 +
  series    = {LNCS},
 +
  volume    = {4945},
 +
  abstract = {The cryptanalysis of the cryptographic hash function Tiger has, until now, focussed on finding collisions. In this paper we describe a preimage attack on the compression function of Tiger-12, i.e., Tiger reduced to 12 rounds out of 24, with a complexity of 2^63.5 compression function evaluations. We show how this can be used to construct second preimages with complexity 2^63.5 and first preimages with complexity 2^64.5 for Tiger-12. These attacks can also be extended to Tiger-13 at the expense of an additional factor of 2^64 in complexity. },
 +
}
 +
 
 +
 
 +
</bibtex>
 +
 
 +
----
 +
 
 +
=== Others ===

Latest revision as of 15:10, 18 September 2009

1 Specification

Ross J. Anderson, Eli Biham - TIGER: A Fast New Hash Function

FSE 1039:89-97,1996
http://dx.doi.org/10.1007/3-540-60865-6
Bibtex
Author : Ross J. Anderson, Eli Biham
Title : TIGER: A Fast New Hash Function
In : FSE -
Address :
Date : 1996

2 Cryptanalysis

2.1 Best Known Results

The best known attack is a 1-bit circular pseudo-near-collision for Tiger with a complexity of about 247 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 262.

2.2 Generic Attacks

2.3 Collision Attacks

Florian Mendel, Vincent Rijmen - Cryptanalysis of the Tiger Hash Function

ASIACRYPT 4833:536-550,2007
http://dx.doi.org/10.1007/978-3-540-76900-2_33
Bibtex
Author : Florian Mendel, Vincent Rijmen
Title : Cryptanalysis of the Tiger Hash Function
In : ASIACRYPT -
Address :
Date : 2007

Florian Mendel, Bart Preneel, Vincent Rijmen, Hirotaka Yoshida, Dai Watanabe - Update on Tiger

INDOCRYPT 4329:63-79,2006
http://dx.doi.org/10.1007/11941378_6
Bibtex
Author : Florian Mendel, Bart Preneel, Vincent Rijmen, Hirotaka Yoshida, Dai Watanabe
Title : Update on Tiger
In : INDOCRYPT -
Address :
Date : 2006

John Kelsey, Stefan Lucks - Collisions and Near-Collisions for Reduced-Round Tiger

FSE 4047:111-125,2006
http://dx.doi.org/10.1007/11799313_8
Bibtex
Author : John Kelsey, Stefan Lucks
Title : Collisions and Near-Collisions for Reduced-Round Tiger
In : FSE -
Address :
Date : 2006

2.4 Second Preimage Attacks

2.5 Preimage Attacks

Takanori Isobe, Kyoji Shibutani - Preimage Attacks on Reduced Tiger and SHA-2

Fast Software Encryption 5665:139-155,2009
http://dx.doi.org/10.1007/978-3-642-03317-9
Bibtex
Author : Takanori Isobe, Kyoji Shibutani
Title : Preimage Attacks on Reduced Tiger and SHA-2
In : Fast Software Encryption -
Address :
Date : 2009

Florian Mendel - Two Passes of Tiger Are Not One-Way

AFRICACRYPT 5580:29-40,2009
http://dx.doi.org/10.1007/978-3-642-02384-2_3
Bibtex
Author : Florian Mendel
Title : Two Passes of Tiger Are Not One-Way
In : AFRICACRYPT -
Address :
Date : 2009

Sebastiaan Indesteege, Bart Preneel - Preimages for Reduced-Round Tiger

WEWoRC 4945:90-99,2007
http://dx.doi.org/10.1007/978-3-540-88353-1_8
Bibtex
Author : Sebastiaan Indesteege, Bart Preneel
Title : Preimages for Reduced-Round Tiger
In : WEWoRC -
Address :
Date : 2007

2.6 Others

Retrieved from "https://ehash.iaik.tugraz.at/index.php?title=Tiger&oldid=3255"