The Tiger Algorithm

The Tiger Algorithm

Introduction

Tiger is a cryptographic hash function with a 192-bit digest, which is 24 bytes or 48 hexadecimal digits. Ross Anderson and Eli Biham designed it in 1995 with one goal: to be fast on the 64-bit processors that were just appearing, and still not slow on 32-bit ones. Most hash functions of that time worked on 32-bit words. Tiger works on 64-bit words from the start.

Its speed comes from large lookup tables. Tiger has four S-boxes, each with 256 entries of 64 bits, which makes 8 KiB of tables. Every round reads eight of these entries. Tables of this size suit a desktop processor, and they are a real cost on a small device. Two other ideas keep the function simple: it uses only a few operations per round, and it spreads each message word over the state with a short key schedule. A well-known use of Tiger is the Tiger Tree Hash, which file-sharing programs use to check large files. The FAQ covers the difference between Tiger and Tiger2, and why two programs can print different digests.

Table of Contents

• History and Standards
• Padding
• The Structure
• One Round
• Passes and Key Schedule
• The S-boxes
• Interactive Visualizer
• A Worked Example
• Python Implementation
• Security Status
• FAQ
• References

History and Standards

Anderson and Biham published Tiger at the Fast Software Encryption workshop in Cambridge in 1996. They put the paper, reference code, and test vectors on a web page. Tiger was designed for speed on the DEC Alpha, one of the leading 64-bit machines of its time. Truncated forms, Tiger/128 and Tiger/160, also exist for protocols that need shorter hashes.

In response to many requests, the designers later published Tiger2. It differs from Tiger only in the padding method, which is the same as in MD5 and SHA. Tiger was considered for OpenPGP, but RIPEMD-160 was chosen instead. Today, Tiger is mostly a historic design, with a niche use in the Tiger Tree Hash.

Padding

Tiger is a Merkle-Damgard hash that works on 64-byte blocks. It pads like MD4 and MD5, with one difference in the first byte:

1. Append one byte, 0x01 for Tiger or 0x80 for Tiger2.
2. Append zero bytes until the length is 8 bytes short of a multiple of 64.
3. Append the original message length in bits, as an 8-byte little-endian number.

A message of 55 bytes or fewer needs one block. A message of 56 to 119 bytes needs two.

The first release of the reference code used 0x80 by mistake. John Lull found the typo, and the designers corrected the code to use 0x01. The test results on their page are for the corrected version. Tiger2 later made the 0x80 choice official.

The Structure

The state is three 64-bit words, a, b, and c. They start with fixed values:

a = 0x0123456789ABCDEF
b = 0xFEDCBA9876543210
c = 0xF096A5B4C3B2E187

Each 64-byte block is read as eight little-endian 64-bit words x0 to x7. The compression function runs three passes. Each pass has eight rounds, one for each message word, so there are 24 rounds in all. Between passes, a key schedule changes the message words. At the end, a feed-forward step combines the new state with the old one.

One Round

A round takes the three state words, one message word x, and a multiplier mul. The round then performs these four steps:

c = c xor x
a = a - ( T1[c0] xor T2[c2] xor T3[c4] xor T4[c6] )
b = b + ( T4[c1] xor T3[c3] xor T2[c5] xor T1[c7] )
b = b * mul

Here c0 to c7 are the eight bytes of c after the first line has XORed in the message word, with c0 the least significant. T1 to T4 are the four S-boxes. All arithmetic is modulo 2^64. So the round cuts c into bytes, uses each byte to look up a 64-bit value, and mixes four values into a by subtraction and four into b by addition. The multiplication by 5, 7, or 9 spreads the changes across all bits of b.

After every round, the roles of the three words rotate. The first round uses (a, b, c), the second uses (b, c, a), and the third uses (c, a, b). Then the pattern repeats. This means each word gets a turn at every role.

Passes and Key Schedule

One pass has eight rounds, one for each of x0 to x7, and a fixed multiplier. The multipliers are 5 for the first pass, 7 for the second, and 9 for the third. After a pass, the registers rotate once more, so that (a, b, c) becomes (c, a, b).

Before the second and third passes, the key schedule changes the eight message words, so that each pass sees them in a different form:

x0 = x0 - (x7 xor 0xA5A5A5A5A5A5A5A5)
x1 = x1 xor x0
x2 = x2 + x1
x3 = x3 - (x2 xor ((not x1) << 19))
x4 = x4 xor x3
x5 = x5 + x4
x6 = x6 - (x5 xor ((not x4) >> 23))
x7 = x7 xor x6
x0 = x0 + x7
x1 = x1 - (x0 xor ((not x7) << 19))
x2 = x2 xor x1
x3 = x3 + x2
x4 = x4 - (x3 xor ((not x2) >> 23))
x5 = x5 xor x4
x6 = x6 + x5
x7 = x7 - (x6 xor 0x0123456789ABCDEF)

This is a small, fast mixing step, with shifts of 19 and 23 bits and two fixed constants. It makes sure that a change in one message word affects every word before the next pass.

After the three passes, the feed-forward uses the state from before the block:

a = a xor a_old
b = b - b_old
c = c + c_old

The feed-forward mixes the old state back in with three different operations, XOR, subtraction, and addition. After the last block, the three words, written as little-endian bytes, are the digest.

The S-boxes

The S-boxes are what make Tiger fast and also what make it special. A table of 1024 random-looking 64-bit numbers is a lot to publish. So the designers explained how they made them, and the generator is short:

1. Start with table entries where each of the eight bytes of entry i equals i mod 256.
2. Run Tiger’s own compression function on a fixed 64-byte sentence, Tiger - A Fast New Hash Function, by Ross Anderson and Eli Biham, using the S-boxes as they are at that moment.
3. Use the eight bytes of the resulting state words to choose entries to swap, byte by byte, inside each S-box.
4. Repeat for five passes over all 256 entries of the four tables.

Nothing in the generator is secret, and nothing is random. Anyone can rebuild all 1024 values from the sentence. In spirit, this is a “nothing up my sleeve” design, because anyone can check where the tables come from. The Python code below includes this generator, so it does not need any table.

Interactive Visualizer

The visualizer above runs this exact algorithm. Choose Tiger or Tiger2, type any message of up to 119 bytes, and click Hash. The log shows the padding, the start of each block, all 24 rounds with the three state words and the message word, the two key schedules, the rotation after each pass, and the feed-forward. When it ends, the page tells you how many of the 192 digest bits change when one bit of your message is flipped.

A Worked Example

This follows the message abc, with Tiger.

Padding. The three bytes 61 62 63 get the byte 01, zeros, and the length 24 bits, which is 0x18. The whole padded block is:

61626301000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001800000000000000

As little-endian words, x0 = 0000000001636261, x1 to x6 are zero, and x7 = 0000000000000018. With Tiger2, the padding byte is 80 and x0 is 0000000080636261.

Round 1. The state is a = 0123456789abcdef, b = fedcba9876543210, and c = f096a5b4c3b2e187. First, c is XORed with x0, which gives f096a5b4c2d183e6. The table lookups use the bytes of this new value, not of the old c. Its bytes, from c0 to c7, are e6 83 d1 c2 b4 a5 96 f0. The four S-box entries for a are 08df828745d9179e, 58bc7a66c232bd5e, 1ecbba0714e2a97b, and 3691e03f52a0f9d1. Their XOR is 7839a2d9c1a9fa6a, and subtracting it gives the new a = 88e9a28dc801d385. The four entries for b are 57dfeff845c6d3c3, cae321fbc819d504, 9e0523c9971d311d, and bb434a2dee7269e7, with the XOR b87aa7e7f4b05e3d. Adding it to b gives b75762806b04904d, and multiplying by 5 gives b = 94b4ec821716d181.

Pass 1. After eight rounds and the rotation, the registers are c784865bbf7be530 37f11e8ec9aac83a 57a5f77163b42fd9. The first key schedule then turns x0 into d1d1d3010b52e8de, x1 into 6f3f0a02c642d3c6, and x7 into becc915b9f1f302b.

Pass 2 and 3. After the second pass, the registers are c2e2faf87bfcba9d b513cad692e835e8 63d14c6d4a005add. After the third pass, they are f37b848f0dbf66c5 51576fda7619eacf a2c8d5e0586047ca.

Feed-forward. XORing a with the starting a, subtracting the starting b from b, and adding the starting c to c gives the final state f258c1e88414ab2a 527ab541ffc5b8bf 935f7b951c132951. This matches the three words in the designers’ own test results. Written as little-endian bytes, the digest is:

2aab1484e8c158f2bfb8c5ff41b57a525129131c957b5f93

The designers print each word with its most significant byte first, which gives F258C1E88414AB2A as the first word. The byte string above is the same value, with each word reversed. The Tiger2 digest of abc is f68d7bc5af4b43a06e048d7829560d4a9415658bb0b1f3bf.

Other messages. The empty message gives 3293ac630c13f0245f92bbb1766e16167a4e58492dde73f3 with Tiger and 4441be75f6018773c206c22745374b924aa8313fef919f41 with Tiger2. The sentence The quick brown fox jumps over the lazy dog gives 6d12a41e72e644f017b6f0e2f7b44c6285f06dd5d2c5b075 with Tiger and 976abff8062a2e9dcea3a1ace966ed9c19cb85558b4976d8 with Tiger2. Flipping one bit of abc changes 97 of the 192 bits. The sentences ... lazy dog and ... lazy cog differ in 108 bits.

Python Implementation

This is a complete Tiger and Tiger2, including the S-box generator. The program builds the tables when it starts, which takes a fraction of a second.

# tiger.py
#
# Tiger, a 192-bit hash function by Ross Anderson and Eli Biham (1995), made
# for fast hashing on 64-bit processors. It uses four S-boxes with 256 entries of
# 64 bits each. Rather than listing those 1024 numbers, this file makes them
# the way the designers did: it starts with the identity and shuffles the
# S-boxes with Tiger's own compression function, using a fixed sentence.
#
# Tiger2 differs only in the padding byte: 0x80 instead of 0x01.

MASK = 0xFFFFFFFFFFFFFFFF

# the starting state, three 64-bit words
INITIAL = [0x0123456789ABCDEF, 0xFEDCBA9876543210, 0xF096A5B4C3B2E187]

# the sentence that seeds the S-box generator (exactly 64 bytes)
SEED = b"Tiger - A Fast New Hash Function, by Ross Anderson and Eli Biham"


def byte_of(x, k):
    return (x >> (8 * k)) & 0xFF


def tiger_round(sb, a, b, c, x, mul):
    """One round. The eight bytes of c pick eight S-box entries, four for a and four for b."""
    c ^= x
    a = (a - (sb[byte_of(c, 0)] ^ sb[256 + byte_of(c, 2)] ^ sb[512 + byte_of(c, 4)] ^ sb[768 + byte_of(c, 6)])) & MASK
    b = (b + (sb[768 + byte_of(c, 1)] ^ sb[512 + byte_of(c, 3)] ^ sb[256 + byte_of(c, 5)] ^ sb[byte_of(c, 7)])) & MASK
    return a, (b * mul) & MASK, c


def tiger_pass(sb, a, b, c, x, mul):
    """Eight rounds, one for each message word. The roles of a, b and c rotate from round to round."""
    for i in range(8):
        if i % 3 == 0:
            a, b, c = tiger_round(sb, a, b, c, x[i], mul)
        elif i % 3 == 1:
            b, c, a = tiger_round(sb, b, c, a, x[i], mul)
        else:
            c, a, b = tiger_round(sb, c, a, b, x[i], mul)
    return a, b, c


def key_schedule(x):
    """Mix the eight message words so that the next pass sees them in a different form."""
    x = list(x)
    x[0] = (x[0] - (x[7] ^ 0xA5A5A5A5A5A5A5A5)) & MASK
    x[1] ^= x[0]
    x[2] = (x[2] + x[1]) & MASK
    x[3] = (x[3] - (x[2] ^ ((~x[1] << 19) & MASK))) & MASK
    x[4] ^= x[3]
    x[5] = (x[5] + x[4]) & MASK
    x[6] = (x[6] - (x[5] ^ (~x[4] & MASK) >> 23)) & MASK
    x[7] ^= x[6]
    x[0] = (x[0] + x[7]) & MASK
    x[1] = (x[1] - (x[0] ^ ((~x[7] << 19) & MASK))) & MASK
    x[2] ^= x[1]
    x[3] = (x[3] + x[2]) & MASK
    x[4] = (x[4] - (x[3] ^ (~x[2] & MASK) >> 23)) & MASK
    x[5] ^= x[4]
    x[6] = (x[6] + x[5]) & MASK
    x[7] = (x[7] - (x[6] ^ 0x0123456789ABCDEF)) & MASK
    return x


def words(block):
    return [int.from_bytes(block[8 * i:8 * i + 8], "little") for i in range(8)]


def compress(sb, state, block):
    """Three passes of eight rounds, with the multipliers 5, 7 and 9, then the feed-forward."""
    a, b, c = state
    x = words(block)
    for number, mul in enumerate((5, 7, 9)):
        if number:
            x = key_schedule(x)
        a, b, c = tiger_pass(sb, a, b, c, x, mul)
        a, b, c = c, a, b
    return [a ^ state[0], (b - state[1]) & MASK, (c + state[2]) & MASK]


def generate_sboxes():
    """Start from the identity, then swap bytes between S-box entries, steered by the compression function."""
    sb = [sum(((i & 255) << (8 * col)) for col in range(8)) for i in range(1024)]
    state = list(INITIAL)
    counter = 2
    for _ in range(5):
        for i in range(256):
            for base in range(0, 1024, 256):
                counter += 1
                if counter == 3:
                    counter = 0
                    state = compress(sb, state, SEED)
                for col in range(8):
                    j = base + byte_of(state[counter], col)
                    p, q = byte_of(sb[base + i], col), byte_of(sb[j], col)
                    sb[base + i] = (sb[base + i] & ~(0xFF << (8 * col)) & MASK) | (q << (8 * col))
                    sb[j] = (sb[j] & ~(0xFF << (8 * col)) & MASK) | (p << (8 * col))
    return sb


SBOXES = generate_sboxes()


def pad(message, tiger2=False):
    """Append 0x01 (0x80 for Tiger2), zeros up to 56 mod 64, and the 64-bit little-endian bit length."""
    padded = message + (b"\x80" if tiger2 else b"\x01") + bytes((55 - len(message)) % 64)
    return padded + (8 * len(message) % 2**64).to_bytes(8, "little")


def tiger(message, tiger2=False):
    state = list(INITIAL)
    padded = pad(message, tiger2)
    for i in range(0, len(padded), 64):
        state = compress(SBOXES, state, padded[i:i + 64])
    return b"".join(w.to_bytes(8, "little") for w in state)


if __name__ == "__main__":
    for text in (b"", b"abc", b"Tiger"):
        print("Tiger(%r) = %s" % (text.decode(), tiger(text).hex()))
    print("Tiger2('abc') = " + tiger(b"abc", tiger2=True).hex())

Running it produces this output:

Tiger('') = 3293ac630c13f0245f92bbb1766e16167a4e58492dde73f3
Tiger('abc') = 2aab1484e8c158f2bfb8c5ff41b57a525129131c957b5f93
Tiger('Tiger') = dd00230799f5009fec6debc838bb6a27df2b9d6f110c7937
Tiger2('abc') = f68d7bc5af4b43a06e048d7829560d4a9415658bb0b1f3bf

I checked this code against several independent sources before writing it up. The generator reproduces all 1024 entries of the designers’ sboxes.c, and it uses the sentence and the five passes from their gen-sboxes.c. I only read those C files and did not run them. The digests match the nine test results and the 64 KiB test of the designers, and the libgcrypt vectors for Tiger and Tiger2, including one million repetitions of the letter a and a million-byte counting pattern.

Security Status

No collision attack on the full 24 rounds is known. Most published results reach only part of the rounds. In 2006, John Kelsey and Stefan Lucks found a collision attack on 16 and 17 rounds, at a cost of about 2^44 compression calls, and pseudo-near collisions on 20 rounds. Also in 2006, Florian Mendel and colleagues extended these to a collision attack on 19 rounds, at about 2^62, and pseudo-near collisions on 22 rounds, at about 2^44.

In 2007, Mendel and Vincent Rijmen reached the full function. They found a pseudo-near-collision for all 24 rounds at a cost of about 2^47 hash computations, and a pseudo-collision for 23 rounds at the same cost. The word “pseudo” means that the attacker may choose the starting values of the three state words. A near-collision means that two outputs differ in only a few bits. So this is a weakness of the compression function, and it is not a collision of the hash with its normal starting values.

The digest has 192 bits, so a birthday search needs about 2^96 hashes to find a collision. Tiger is also a Merkle-Damgard hash, so it allows length extension. Use HMAC when you need a keyed hash.

Tiger has seen much less analysis than SHA-2 or SHA-3. For new systems, use SHA-256, SHA-3, or BLAKE2. Tiger remains useful for compatibility, mostly through the Tiger Tree Hash.

FAQ

What is the difference between Tiger and Tiger2?

Only the first padding byte. Tiger appends 0x01, and Tiger2 appends 0x80, as MD5 and SHA do. Everything else is the same, but the digests are completely different.

Why do two programs print different digests for the same message?

The specification defines the output as three 64-bit integers, not as a byte string. The designers print each integer with its most significant byte first. Many libraries and programs, such as Direct Connect, use little-endian bytes instead. The two forms differ only in the byte order inside each word.

What is the Tiger Tree Hash?

It is a Merkle tree built from Tiger. The file is cut into 1024-byte pieces, each piece is hashed, and the hashes are combined pairwise up to a single root hash. File-sharing systems such as Direct Connect and Gnutella use the root to check a file, and each branch to check a single part.

Where do the S-box values come from?

The designers made them with a generator that runs Tiger’s own compression function on a fixed sentence and uses its output to shuffle the tables. Anyone can repeat the process, and the Python code in this guide does.

Is Tiger secure?

No practical attack on the full function is known. It has had less public analysis than modern standards, though, and a 192-bit digest gives only 96 bits of collision resistance. Choose a current standard for new designs.

References

1. Anderson, R. and Biham, E. “Tiger: A Fast New Hash Function.” Fast Software Encryption (FSE) 1996, Lecture Notes in Computer Science 1039, Springer. Available at: https://www.cs.technion.ac.il/~biham/Reports/Tiger/

2. Kelsey, J. and Lucks, S. “Collisions and Near-Collisions for Reduced-Round Tiger.” Fast Software Encryption (FSE) 2006, Lecture Notes in Computer Science 4047, Springer.

3. Mendel, F., Preneel, B., Rijmen, V., Yoshida, H., and Watanabe, D. “Update on Tiger.” INDOCRYPT 2006, Lecture Notes in Computer Science 4329, Springer.

4. Mendel, F. and Rijmen, V. “Cryptanalysis of the Tiger Hash Function.” ASIACRYPT 2007, Lecture Notes in Computer Science 4833, Springer. Available at: https://doi.org/10.1007/978-3-540-76900-2_33

5. Wikipedia. “Tiger (hash function).” Available at: https://en.wikipedia.org/wiki/Tiger_(hash_function)