Eric Christopher Seidel 


Tiger Hash Algorithm 

The DemonstrationThis 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.
Using the AppletTo 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 OverviewThe 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 64bit architectures, Tiger is designed for speed. Tiger employs a Time Memory TradeOff, using 4 small lookuptables or SBoxes, similar to DES or other block ciphers. Security Through the use of the sboxes, 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/ SetupTiger 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 512bits. 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 littleendian 64bit representation of the length. The message is then divided into 512bit (64byte) blocks, each of which is processed individually. Algorithm StagesThe algorithm uses the following stages:
The following section contains Cstyle pseudocode demonstrating how each of the algorithm stages could be implemented: A single passEach 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 64bit word of the 512bit block, x17 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 FunctionEach round consists of the following: (c1 refers to the first byte of x, c28 refer to the remaining bytes respectively. s1, s2, s3, s4 refer to the four sboxes) 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 redistribute the bits among sbox lookups. Key SchedulingKey scheduling is used for rotating the 512 input bits among the 8 64bit words between each of the 3 passes. The first pass is done without any translation. The keyschedule 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. FeedForwardThe final piece of the algorithm is the simple feedforward function, used for propagating the hashed bits between the 512bit 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. 


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