Tiger (hash)
Encyclopedia
In cryptography
, Tiger is a cryptographic hash function
designed by Ross Anderson and Eli Biham
in 1995 for efficiency on 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 is a variant where the message is padded by first appending a byte with the hexadecimal value of 0x80 as in MD4
, MD5
and SHA
, rather than with the hexadecimal value of 0x01 as in the case of Tiger. The two variants are otherwise identical.
Although fast in software, Tiger's large S-boxes (4 S-boxes, each with 256 64-bit entries totals 8 KiB) make implementations in hardware or small microcontroller
s difficult.
form, where it is referred to as TTH (Tiger Tree Hash). TTH is used by many clients on the Direct Connect and Gnutella
file sharing networks.
Tiger was considered for inclusion in the OpenPGP standard, but was abandoned in favor of RIPEMD
-160.
byte order (this print order is also used by SHA-1 and SHA-2 hash outputs, for example, as it allows also humans to read the number from left to right).
Therefore in the example below the 192-bit (24-byte) Tiger hashes are represented as 48 hexadecimal
digits in big-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 dog") =
6d12a41e72e644f017b6f0e2f7b44c6285f06dd5d2c5b075
Tiger2("The quick brown fox jumps over the lazy dog") =
976abff8062a2e9dcea3a1ace966ed9c19cb85558b4976d8
Even a small change in the message will (with overwhelming probability) result in a completely different hash, e.g. changing d to c:
Tiger("The quick brown fox jumps over the lazy cog") =
a8f04b0f7201a0d728101c9d26525b31764a3493fcd8458f
Tiger2("The quick brown fox jumps over the lazy cog") =
09c11330283a27efb51930aa7dc1ec624ff738a8d9bdd3df
The hash of the zero-length string is:
Tiger("") =
3293ac630c13f0245f92bbb1766e16167a4e58492dde73f3
Tiger2("") =
4441be75f6018773c206c22745374b924aa8313fef919f41
John Kelsey
and Stefan Lucks
have found a collision-finding attack on 16-round Tiger with a time complexity equivalent to about 244 compression function invocations and another attack that finds pseudo-near collisions in 20-round Tiger with work less than that of 248 compression function invocations. 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 262 and 244 evaluations of the Tiger compression function, respectively.
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
, Tiger is a cryptographic hash function
Cryptographic hash function
A cryptographic hash function is a deterministic procedure that takes an arbitrary block of data and returns a fixed-size bit string, the hash value, such that an accidental or intentional change to the data will change the hash value...
designed by Ross Anderson and Eli Biham
Eli Biham
Eli Biham is an Israeli cryptographer and cryptanalyst, currently a professor at the Technion Israeli Institute of Technology Computer Science department. Starting from October 2008, Biham is the dean of the Technion Computer Science department, after serving for two years as chief of CS graduate...
in 1995 for efficiency on 64-bit
64-bit
64-bit is a word size that defines certain classes of computer architecture, buses, memory and CPUs, and by extension the software that runs on them. 64-bit CPUs have existed in supercomputers since the 1970s and in RISC-based workstations and servers since the early 1990s...
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
SHA-2
In cryptography, SHA-2 is a set of cryptographic hash functions designed by the National Security Agency and published in 2001 by the NIST as a U.S. Federal Information Processing Standard. SHA stands for Secure Hash Algorithm. SHA-2 includes a significant number of changes from its predecessor,...
family, no distinguishing initialization values are defined; they are simply prefixes of the full Tiger/192 hash value.
Tiger2 is a variant where the message is padded by first appending a byte with the hexadecimal value of 0x80 as in MD4
MD4
The MD4 Message-Digest Algorithm is a cryptographic hash function developed by Ronald Rivest in 1990. The digest length is 128 bits. The algorithm has influenced later designs, such as the MD5, SHA-1 and RIPEMD algorithms....
, MD5
MD5
The MD5 Message-Digest Algorithm is a widely used cryptographic hash function that produces a 128-bit hash value. Specified in RFC 1321, MD5 has been employed in a wide variety of security applications, and is also commonly used to check data integrity...
and SHA
Sha
For other uses, see Sha .Sha is a letter of the Cyrillic alphabet. It commonly represents the voiceless postalveolar fricative , like the pronunciation of ⟨sh⟩ in "sheep", or the somewhat similar voiceless retroflex fricative . It is used in every variation of the Cyrillic alphabet, for Slavic and...
, rather than with the hexadecimal value of 0x01 as in the case of Tiger. The two variants are otherwise identical.
Algorithm
Tiger is designed using the nearly universal Merkle-Damgård paradigm. 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 (4 S-boxes, each with 256 64-bit entries totals 8 KiB) make implementations in hardware or small microcontroller
Microcontroller
A microcontroller is a small computer on a single integrated circuit containing a processor core, memory, and programmable input/output peripherals. Program memory in the form of NOR flash or OTP ROM is also often included on chip, as well as a typically small amount of RAM...
s difficult.
Usage
Tiger is frequently used in Merkle hash treeHash tree
In cryptography and computer science Hash trees or Merkle trees are a type of data structure which contains a tree of summary information about a larger piece of data – for instance a file – used to verify its contents. Hash trees are a combination of hash lists and hash chaining, which in turn are...
form, where it is referred to as TTH (Tiger Tree Hash). TTH is used by many clients on the Direct Connect and Gnutella
Gnutella
Gnutella is a large peer-to-peer network which, at the time of its creation, was the first decentralized peer-to-peer network of its kind, leading to other, later networks adopting the model...
file sharing networks.
Tiger was considered for inclusion in the OpenPGP standard, but was abandoned in favor of RIPEMD
RIPEMD
RIPEMD-160 is a 160-bit message digest algorithm developed in Leuven, Belgium, by Hans Dobbertin, Antoon Bosselaers and Bart Preneel at the COSIC research group at the Katholieke Universiteit Leuven, and first published in 1996...
-160.
Examples
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. Actually the specification of Tiger do not define the way the output of Tiger is printed, however its testvectors for NESSIE are using the quasi-standard printing method for hashes which is the big endianEndianness
In computing, the term endian or endianness refers to the ordering of individually addressable sub-components within the representation of a larger data item as stored in external memory . Each sub-component in the representation has a unique degree of significance, like the place value of digits...
byte order (this print order is also used by SHA-1 and SHA-2 hash outputs, for example, as it allows also humans to read the number from left to right).
Therefore in the example below the 192-bit (24-byte) Tiger hashes are represented as 48 hexadecimal
Hexadecimal
In mathematics and computer science, hexadecimal is a positional numeral system with a radix, or base, of 16. It uses sixteen distinct symbols, most often the symbols 0–9 to represent values zero to nine, and A, B, C, D, E, F to represent values ten to fifteen...
digits in big-endian byte order. The following demonstrates a 43-byte ASCII
ASCII
The American Standard Code for Information Interchange is a character-encoding scheme based on the ordering of the English alphabet. ASCII codes represent text in computers, communications equipment, and other devices that use text...
input and the corresponding Tiger hashes:
Tiger("The quick brown fox jumps over the lazy dog") =
6d12a41e72e644f017b6f0e2f7b44c6285f06dd5d2c5b075
Tiger2("The quick brown fox jumps over the lazy dog") =
976abff8062a2e9dcea3a1ace966ed9c19cb85558b4976d8
Even a small change in the message will (with overwhelming probability) result in a completely different hash, e.g. changing d to c:
Tiger("The quick brown fox jumps over the lazy cog") =
a8f04b0f7201a0d728101c9d26525b31764a3493fcd8458f
Tiger2("The quick brown fox jumps over the lazy cog") =
09c11330283a27efb51930aa7dc1ec624ff738a8d9bdd3df
The hash of the zero-length string is:
Tiger("") =
3293ac630c13f0245f92bbb1766e16167a4e58492dde73f3
Tiger2("") =
4441be75f6018773c206c22745374b924aa8313fef919f41
Cryptanalysis
Unlike MD5 or SHA-0/1, there are no known attacks on the full 24-round Tiger except for pseudo-near collision. 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
John Kelsey (cryptanalyst)
John Kelsey is a cryptographer currently working at NIST. His research interests include cryptanalysis and design of symmetric cryptography primitives , analysis and design of cryptographic protocols, cryptographic random number generation, electronic voting, side-channel attacks on cryptography...
and Stefan Lucks
Stefan Lucks
Stefan Lucks is a researcher in the fields of communications security and cryptography. Lucks is known for his attack on Triple DES, and for extending Lars Knudsen's Square attack to Twofish, a cipher outside the Square family, thus generalising the attack into integral cryptanalysis...
have found a collision-finding attack on 16-round Tiger with a time complexity equivalent to about 244 compression function invocations and another attack that finds pseudo-near collisions in 20-round Tiger with work less than that of 248 compression function invocations. 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 262 and 244 evaluations of the Tiger compression function, respectively.
See also
- Comparison of cryptographic hash functionsComparison of cryptographic hash functionsThe following tables compare general and technical information for a number of cryptographic hash functions.- General information :Basic general information about the cryptographic hash functions: year, designer, references, etc.- Compression function :...
- List of hash functions
- SerpentSerpent (cipher)Serpent is a symmetric key block cipher which was a finalist in the Advanced Encryption Standard contest, where it came second to Rijndael. Serpent was designed by Ross Anderson, Eli Biham, and Lars Knudsen....
— A block cipher by the same authors