Skip to main content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

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
Created June 1, 2016, Updated November 10, 2018