The TIB3 Hash Algorithm

TIB3 is a family of hash algorithms developed by Daniel Penazzi and Miguel Montes, that has been submitted to the NIST cryptographic hash algorithm competition.

Here is the current version of the algorithm specification. It is the original submitted version with some english typos corrected, and with some fancy pdf bookmarks and links.

The original submission package can be found here, with the source code (little endian version) and test vectors. Compressed versions (14 MB): tgz, zip

Here are additional implementations

TIB3 Design

TIB3 design is conservative. It is based on a generalization of the Merkle-Damgård construction, and the compression function uses an ad-hoc block cipher with a modified Davies-Meyer structure. It shares some high level characteristics with SHA256, but with added security features so an attack on SHA256 is unlikely to extend to TIB3.
The main security features are:

  1. The underlying block cipher is an SPN with 16 rounds, and it uses, besides xors and sums, non-linear bijective Sboxes.
  2. Besides the usual previous hash and current message block, the compression function also uses the number of bits processed and the previous message block. Thus, each block is processed through 32 rounds.
  3. The last iteration is done using a different scheme than the intermediate ones, to prevent extension attacks.
  4. The expansion of the key is done in such a way that a backward recursion is unlikely to succeed.
TIB3 uses only logical operations and modular sums, so it fits comfortably in most environments (despite using Sboxes, TIB3 does not use table lookups since the Sboxes are realized with a bitsliced implementation).

TIB3 Performance

TIB3 is fast. The code is efficient in both 64-bit and 32-bit platforms. On the reference platform Core 2 Duo 2.4 GHz running Vista 64-bits, TIB3 hashes at about 290-300 MB/sec (7.68 cycles/byte) for the 224 and 256 versions and at about 350 MB/sec (6.24 cycles/byte) for the 384 and 512 versions for long messages. On a 32-bit platform, running Vista 32 bits, the 224 and 256 versions run at about 173 MB/sec (12.96 cycles/byte) for long messages, and the 384/512 versions at about 130 Mb/sec (17.68 cycles/byte).

NEW :Tweak on TIB3

NIST has indicated that it will allow the 15 candidates that go to the second round to do some minor tweak on their submissions. We have decided to announce now what our tweak would be if we are selected, to give ample time for analyisis.

We have decided to do a small tweak to TIB3 because we made a mistake in the diffusion of the cipher, which allows some differential paths confined to just one active Sbox to exist.

This makes the underlying block cipher of TIB3 to be weak, a fact that has been shown by Mendel and Schlaffer. While this does not translate into a lethal attack on the hash function, it is a concern.

The Tweak changes just part of the diffusion: The instruction A=A~+G, (where ~+ meant the parallel 32 bit addition of 64 bit registers) is changed into A=(G<<<37) xor (A<<<12) xor (A>>1) in the 256 case and something similar in the 512 case.

The underlying block cipher is now much more secure, and is still fast, although there is some price in speed paid:

For the 224/256 version, the speeds changes in the 64-bit implementation from 7.68 cycles per byte on the original version to 8.08 in the tweaked version. In the case of the 32-bit implementation, the speed changes from 12.96 cycles per byte to 14.24.

For the 384/512 version, the 64-bit optimized implementation goes down from 6.24 cycles per byte to 7.20 cycles per byte. The 32-bit implementation (in ANSI C) goes down from 17.68 cycles per byte to 19.36 cycles per byte.

The description of the Tweak, analysis of its security, with some test files, and the new .c files plus all the new KATS are here. A compressed version (15 MB): zip

If you want just the .pdf with an explanation of the tweak plus some analysis of the security, you can find it here

Note: a previous version of this page listed the tweak with a rotation of 13 on A instead of 12. That was a mistake. We thank the CHI team for pointing this to us.