Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

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

Published

Author(s)

Dustin Moody, Souradyuti Paul, Daniel C. Smith-Tone

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 im
Citation
Journal of Mathematical Cryptology
Volume
10
Issue
2

Keywords

Indifferentiability, birthday barrier, Fast wide pipe

Citation

Moody, D. , Paul, S. and Smith-Tone, D. (2016), Indifferentiability Security of the Fast Widepipe Hash: Breaking the Birthday Barrier, Journal of Mathematical Cryptology, [online], https://doi.org/10.1515/jmc-2014-0044 (Accessed March 28, 2024)
Created June 1, 2016, Updated November 10, 2018