Eric Christopher Seidel

 

Home

 

About

 

Development

 

Academic Work

 

MacDomain

Tiger Hash Algorithm

The Demonstration

This is a demonstration of the Tiger Hash algorithm designed by Eli Biham and Ross Anderson. The demo allows the user to specify an arbitrary string value to hash, and then step through the hashing process one round at a time. This can be particularly useful anyone seeking a better understanding of the algorithm. Short explanatory text is also included below the variable output for each round. I encourage users to read the "Using the Applet" section below to answer any questions.

I have also made available the Java source of this implementation. Thanks to Cryptix for the use of their very clean Tiger Java implementation. (Warning: the Cryptix code included here functions quite different than the original does. Java Tiger implementers should be sure to reference the original cryptix source.)

Furthermore, I have made available here a short presentation (Keynote , PDF or PowerPoint) I gave on the Tiger hashing algorithm.

Click below to open the applet window. The applet should appear in a separate window. Closing this window will also close the applet window.

Your browser does not support Java, so nothing is displayed.

Using the Applet

To use the applet, first enter text in the "input" box. Leaving the input box empty will also work fine, but will hash an empty string.

Click either "Step through algorithm" or "Run hashing algorithm" to step through the algorithm one round at a time, or run the algorithm to completion.

You can also use the table on the left hand side to move forward or back through the algorithm, simply click on any of the rounds to have the algorithm jump to that round.

For explanation of the individual steps of the algorithm, please read the section "Tiger Overview" below.

Tiger Overview

The Tiger algorithm is rather complicated as hashing algorithms go. However, despite this minor complexity Tiger boasts several advantages over other common hash functions. Most notably:

Speed

Especially on 64-bit architectures, Tiger is designed for speed. Tiger employs a Time Memory Trade-Off, using 4 small lookup-tables or S-Boxes, similar to DES or other block ciphers.

Security

Through the use of the s-boxes, Tiger allows for quicker avalanche than either of the other popular hash functions. Tiger's 192 default length also allows a larger collision space.

 

How Tiger works:

The original paper describing Tiger's implementation. can be found at: http://www.cs.technion.ac.il/~biham/Reports/Tiger/

Setup

Tiger is designed to be "out of the box" compatible with MD4, MD5 applications, thus it shares a similar structure to MD4/MD5 for block division and padding.

The message is first padded to 512-bits. First by appending a single 1 bit, followed by 0s. The message is padded out to 448 (mod 512) bits. This is followed by a little-endian 64-bit representation of the length.

The message is then divided into 512-bit (64-byte) blocks, each of which is processed individually.

Algorithm Stages

The algorithm uses the following stages:

  1. Save ABC (carry values)
  2. Pass 1 (Rounds 1-8)
  3. Key Schedule 1
  4. Pass 2 (Rounds 9 - 16)
  5. Key Schedule 2
  6. Pass 3 (Rounds 17-24)
  7. Feed-Forward (calculate next carry values)

The following section contains C-style pseudo-code demonstrating how each of the algorithm stages could be implemented:

A single pass

Each pass is comprised of 8 individual rounds. Each of the 3 passes uses a different multiplier, but executes each series of 8 rounds in the same format. x0 is defined to be the first 64-bit word of the 512-bit block, x1-7 likewise.

pass(a,b,c,mul) :
round(a,b,c,x0,mul);
round(b,c,a,x1,mul);
round(c,a,b,x2,mul);
round(a,b,c,x3,mul);
round(b,c,a,x4,mul);
round(c,a,b,x5,mul);
round(a,b,c,x6,mul);
round(b,c,a,x7,mul);
The Round Function

Each round consists of the following: (c1 refers to the first byte of x, c2-8 refer to the remaining bytes respectively. s1, s2, s3, s4 refer to the four s-boxes)

round(a,b,c,x,mul) :
c = c ^ x
a = a - (s1[c1] ^ s2[c3] ^ s3[c5] ^ s4[c7])
b = b + (s4[c2] ^ s3[c4] ^ s2[c6] ^ s1[c8])
b = b * mul

Notice, all three carry words are affected by the value of the key at each round. c is affected directly by an XOR, a and b are affected by the XOR of the resulting lookups from the individual bytes. The final multiply of b by the given multiplier is used to re-distribute the bits among s-box look-ups.

Key Scheduling

Key scheduling is used for rotating the 512 input bits among the 8 64-bit words between each of the 3 passes. The first pass is done without any translation. The key-schedule function is given below:

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

Key scheduling is perhaps the most complex part of the Tiger algorithm. It's purpose is clear: to distribute the input bits amongst themselves. Its method is not particularly clear however. Regrettably the justification for the individual actions in the key schedule function are also not explained in the accompanying paper.

Feed-Forward

The final piece of the algorithm is the simple feed-forward function, used for propagating the hashed bits between the 512-bit blocks of the message:

feed_forward():
carryA = carryA ^ a;
carryB = carryB - b;
carryC = carryC + c;

Further details and various implementations of Tiger can be found at the author's hompage.

since 2/02

Last updated: Tuesday, November 18, 2003 1:00 PM