Structural Properties of Cryptographic Sequences - Computational Intelligence in Security for Information Systems - page 183

Improving the Message Expansion of the Tangle
Hash Function

Rafael Alvarez, Jose-Francisco Vicent, and Antonio Zamora

Dpto. de Ciencia de la Computacion e Inteligencia Artificial
Universidad de Alicante (Campus de San Vicente)
Ap. Correos 99, E-03080, Alicante, Spain
{ ralvarez,jvicent,zamora } @dccia.ua.es

Abstract. Tangle is an iterative one-way hash function based on the
Merkle-Damgard scheme strengthened by a message dependent round
function. It was submitted to the NIST SHA-3 competition, being accepted
for first round evaluation. We propose an alternative message expansion
scheme for Tangle in order to thwart the collision attacks found during
such evaluation. Based on the fact that differences at the beginning of the
expanded message contribute to better avalanche, the improved message
expansion scheme presents much better properties than the original ver-
sion while maintaining very good performance characteristics.

Keywords: hash cryptography digest sha-3 expansion avalanche tangle.

1 Introduction

Tangle is an iterative one-way hash function based on the Merkle-Damgard
scheme (see [3]) strengthened by a message dependent round function combined
with an 8

×

8 Sbox look-up (see [1]) and a matrix pseudorandom generator based
message expansion function.
With a compression function that natively accepts a 4096 bit long message
block as input and produces a 1024 bit digest as output, it supports six different
digest sizes (224, 256, 384, 512, 768 and 1024 bits) through output truncation;
differing in the number of rounds and the initial values but sharing the same
compression function.
It supports the same interface as SHA-2 (see [7]), accepting messages up to
2128 bits in length and padding the message in a similar way to obtain a message
with a length multiple of 4096 bits.
The design is primarily for 32-bit microprocessors and little-endian memory
organization since they were the most common scenario at that time but meant
to be satisfactorily implementable in different architectures.
It was submitted to the NIST's SHA-3 (see [8]) competition and accepted for
first round evaluation, appearing to have relatively high performance in relation
to many other contestants. Unfortunately, collisions were found for all hash sizes
([9]) and was not suitable for second round evaluation.

Partially supported by the grant GRE09-02 of the University of Alicante.