View source for Tiger (hash function)

{{short description|cryptographic hash function}}
{{Infobox cryptographic hash function
| name           = Tiger
| image          =
| caption        =
<!-- General -->
| designers      = [[Ross J. Anderson|Ross Anderson]] and [[Eli Biham]]
| publish date   = 1996
| series         =
| derived from   =
| derived to     =
| related to     =
| certification  =
<!-- Detail -->
| digest size    = 192, 128, 160
| structure      =
| rounds         = 24
| cryptanalysis  =
}}
In [[cryptography]], '''Tiger'''<ref>{{cite web
| url=https://www.cs.technion.ac.il/~biham/Reports/Tiger/tiger/tiger.html
| title=Tiger: A Fast New Hash Function
| author=Ross Anderson and Eli Biham
| work=Fast Software Encryption 3
| location=[[Cambridge, UK|Cambridge]]
| date=1996-02-08
| access-date=2017-03-03}}</ref> is a [[cryptographic hash function]] designed by [[Ross J. Anderson|Ross Anderson]] and [[Eli Biham]] in 1995 for efficiency on [[64-bit computing|64-bit]] platforms. The size of a Tiger hash value is 192 bits. Truncated versions (known as Tiger/128 and Tiger/160) can be used for compatibility with protocols assuming a particular hash size. Unlike the [[SHA-2]] family, no distinguishing initialization values are defined; they are simply prefixes of the full Tiger/192 hash value.

'''Tiger2'''<ref>{{cite web
| url=https://www.cs.technion.ac.il/~biham/Reports/Tiger/tiger2-test-vectors-nessie-format.dat
| title=Tiger2 Test Vectors
| work=Project [[NESSIE]]
| date=2005-02-25
| access-date=2017-03-03}}</ref> is a variant where the message is padded by first appending a byte with the hexadecimal value of 0x80 as in [[MD4]], [[MD5]] and [[Secure Hash Algorithm|SHA]], rather than with the hexadecimal value of 0x01 as in the case of Tiger. The two variants are otherwise identical.

==Algorithm==
Tiger is based on [[Merkle–Damgård construction]]. The [[one-way compression function]] operates on 64-bit words, maintaining 3 words of state and processing 8 words of data. There are 24 rounds, using a combination of operation mixing with XOR and addition/subtraction, rotates, and [[S-box]] lookups, and a fairly intricate key scheduling algorithm for deriving 24 round keys from the 8 input words.

Although fast in software, Tiger's large S-boxes (four S-boxes, each with 256 64-bit entries totaling 8 [[KiB]]) make implementations in hardware or  [[microcontroller]]s difficult.{{citation needed|date=April 2020}}

==Usage==
Tiger is frequently used in [[Merkle tree|Merkle hash tree]] form, where it is referred to as TTH ([[Merkle tree#Tiger tree hash|Tiger Tree Hash]]). TTH is used by many clients on the [[Direct Connect (protocol)|Direct Connect]] and [[Gnutella]] file sharing networks, and can optionally be included in the [[BitTorrent]] metafile <ref>{{cite web
| url=http://wiki.depthstrike.com/P2P:Protocol:Specifications:Optional_Hashes#TTH_Root
| title=P2P:Protocol:Specifications:Optional Hashes: TTH Root
| first=Harold
| last=Feit
| date=2012-02-12
| access-date=2017-11-18}}</ref> for better content availability.

Tiger was considered for inclusion in the [[OpenPGP]] standard, but was abandoned in favor of [[RIPEMD]]-160.<ref>{{cite web
| first=Jon
| last=Callas
| author-link=Jon Callas
| title=Re: re-consideration of TIGER
| date=2004-08-18
| url=https://archive.cert.uni-stuttgart.de/openpgp/2004/08/msg00005.html
| archive-url=https://web.archive.org/web/20140714145102/http://archive.cert.uni-stuttgart.de/openpgp/2004/08/msg00005.html
| archive-date=2014-07-14
| url-status=live}}</ref><ref>{{cite web
| url=https://crypto.stackexchange.com/a/11285
| title=How do you use the Tiger hash function with GPG?
| first=Thomas
| last=Pornin
| date=2013-10-25}}</ref>

==OID==
{{IETF RFC|2440}} refers to TIGER as having no [[Object identifier|OID]], whereas the [[GNU Coding Standards]] list TIGER as having OID <code>1.3.6.1.4.1.11591.12.2</code>.<ref>{{cite web
| url=https://www.gnu.org/prep/standards/html_node/OID-Allocations.html
| title=Program Behavior for All Programs: OID Allocations
| publisher=[[GNU]]
| access-date=2017-11-18}}</ref> In the [[IPSEC]] subtree, HMAC-TIGER is assigned OID <code>1.3.6.1.5.5.8.1.3</code>.<ref>{{cite web
| url=https://oidref.com/1.3.6.1.5.5.8.1.3
| title=Reference record for OID 1.3.6.1.5.5.8.1.3 – hmacTIGER
| date=1998-10-18
| access-date=2017-11-18}}</ref> No OID for TTH has been announced yet.

==Byte order==
The specification of Tiger does not define the way its output should be printed but only defines the result to be three ordered 64-bit integers. The "testtiger" program at the author's homepage was intended to allow easy testing of the test source code, rather than to define any particular print order. The protocols [[Direct Connect (protocol)|Direct Connect]] and [[Advanced Direct Connect|ADC]] as well as the program <code>tthsum</code> use little-endian byte order, which is also preferred by one of the authors.<ref>{{cite web
| url=https://metacpan.org/pod/distribution/Digest-Tiger/Tiger.pm#NOTE
| title=Digest::Tiger Module
| publisher=[[CPAN]]
| access-date=2017-03-03}}</ref>

==Examples==
In the example below, the 192-bit (24-byte) Tiger hashes are represented as 48 [[hexadecimal]] digits in [[little-endian]] byte order. The following demonstrates a 43-byte [[ASCII]] input and the corresponding Tiger hashes:

 Tiger("The quick brown fox jumps over the lazy {{Background color|#87CEEB|d}}og") =
 6d12a41e72e644f017b6f0e2f7b44c6285f06dd5d2c5b075
 
 Tiger2("The quick brown fox jumps over the lazy {{Background color|#87CEEB|d}}og") =
 976abff8062a2e9dcea3a1ace966ed9c19cb85558b4976d8

Even a small change in the message will (with very high probability) result in a completely different hash, e.g. changing {{mono|d}} to {{mono|c}}: 
<!-- This sentence is confusing in context. It says 'changing d to c' but then both examples are of 'c'. Perhaps a '(compare to above values)' would be helpful? -->

<!-- Both these examples should have "cog". The examples above have "dog". -->
 Tiger("The quick brown fox jumps over the lazy {{Background color|#87CEEB|c}}og") =
 a8f04b0f7201a0d728101c9d26525b31764a3493fcd8458f
 
 Tiger2("The quick brown fox jumps over the lazy {{Background color|#87CEEB|c}}og") =
 09c11330283a27efb51930aa7dc1ec624ff738a8d9bdd3df

The hash of the zero-length string is:

 Tiger("") =
 3293ac630c13f0245f92bbb1766e16167a4e58492dde73f3
 
 Tiger2("") =
 4441be75f6018773c206c22745374b924aa8313fef919f41

==Cryptanalysis==
Unlike MD5 or SHA-0/1, there are no known effective attacks on the full 24-round Tiger<ref name="reduced-round"/> except for pseudo-near collision.<ref>{{Cite conference
 | first1 = Florian
 | last1 = Mendel
 | first2 = Rijmen
 | last2 = Vincent
 | title = Cryptanalysis of the Tiger Hash Function
 | book-title = ASIACRYPT 2007
 | pages = 536–550
 | publisher = Springer Berlin / Heidelberg
 | doi = 10.1007/978-3-540-76900-2_33| doi-access = free
 }}</ref> While MD5 processes its state with 64 simple 32-bit operations per 512-bit block and SHA-1 with 80, Tiger updates its state with a total of 144 such operations per 512-bit block, additionally strengthened by large S-box look-ups.

[[John Kelsey (cryptanalyst)|John Kelsey]] and [[Stefan Lucks]] have found a collision-finding attack on 16-round Tiger with a time complexity equivalent to about 2<sup>44</sup> compression function invocations and another attack that finds pseudo-near collisions in 20-round Tiger with work less than that of 2<sup>48</sup> compression function invocations.<ref name="reduced-round">{{cite journal
| url=http://th.informatik.uni-mannheim.de/People/Lucks/papers/Tiger_FSE_v10.pdf
| title=Collisions and Near-Collisions for Reduced-Round Tiger
| authors=John Kelsey and Stefan Lucks
| journal=Fast Software Encryption 13
| location=[[Graz]]
| year=2006
| archive-url=https://web.archive.org/web/20160304042512/http://th.informatik.uni-mannheim.de/People/Lucks/papers/Tiger_FSE_v10.pdf
| archive-date=2016-03-04
| url-status=dead}}</ref> Florian Mendel et al. have improved upon these attacks by describing a collision attack spanning 19 rounds of Tiger, and a 22-round pseudo-near-collision attack. These attacks require a work effort equivalent to about 2<sup>62</sup> and 2<sup>44</sup> evaluations of the Tiger compression function, respectively.<ref>{{cite journal
| url=https://online.tugraz.at/tug_online/voe_main2.getvolltext?pCurrPk=20716
| title=Update on Tiger
| authors=Florian Mendel, Bart Preneel, Vincent Rijmen, Hirotaka Yoshida, and Dai Watanabe
| journal=Indocrypt 7
| location=[[Kolkata]]
| format=PDF
| year=2006}}</ref>

==See also==
* [[Hash function security summary]]
* [[Comparison of cryptographic hash functions]]
* [[List of hash functions]]
* [[Serpent (cipher)|Serpent]] – a block cipher by the same authors

==References==

<references/>

== External links ==
* {{url|https://www.cs.technion.ac.il/~biham/Reports/Tiger/|The Tiger home page}}

{{Cryptography navbox | hash}}

[[Category:Cryptographic hash functions]]