NIST logo

Publication Citation: Indifferentiability Security of the Fast Widepipe Hash: Breaking the Birthday Barrier

NIST Authors in Bold

Author(s): Dustin Moody; Daniel C. Smith-Tone; Souradyuti Paul;
Title: Indifferentiability Security of the Fast Widepipe Hash: Breaking the Birthday Barrier
Published: December 02, 2012
Abstract: A hash function secure in the indi fferentiability framework is able to resist all generic attacks. Such hash functions also play a crucial role in the security of the protocols that use hash functions as random functions. The rate of a hash mode is the fraction of input used for the message injection; higher rate indicates higher efficiency. The main result of this paper is the solution to a longstanding open problem in the hash function literature: we show that an iterative hash function (with message-block and hash-digest n bits each) can achieve both rate 1 efficiency and an indiff erentiability security bound more than n/2 bits. This result generalizes in a natural way to obtain the best security bounds for other rates too. To eliminate the multi-collision-type attacks on the Merkle-Damgard mode, Lucks designed the Widepipe (WP) hash mode that uses a larger state, which, however, reduces the mode's rate. Since then a number of novel hash modes (including those submitted to the NIST SHA-3 hash function competition e.g. JH, Sponge and Groestl) have been proposed. Surprisingly, none of the rate 1 hash modes, so far, achieved an indifferentiability bound beyond the birthday barrier of n/2 bits. The Fast Widepipe hash mode (which achieves the rate 1 efficiency and the birthday-barrier security) was introduced by Nandi and Paul, as a faster variant of the WP mode. In this paper, we improve the security of the FWP mode to 2n/3 bits, making it the fi rst rate 1 mode with the beyond-birthday-barrier indifferentiability security. Our technique mainly involves the detection of a carefully chosen set of 16 bad events, occurring with low probabilities, to establish an isomorphism of certain query-response graphs built by the simulators. This isomorphism result helps us to linearly bound the size of the simulators' graphs, from which the above bound follows. More interestingly, our experimental data gives evidence that the bound could possibly be improved up to n bits.
Conference: The 18th Annual International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2012
Location: Beijing, -1
Dates: December 2-6, 2012
Keywords: Hash modes; indifferentiability;
Research Areas: Math
PDF version: PDF Document Click here to retrieve PDF version of paper (1MB)