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 Dates: December 2-6, 2012
Conference Location: Beijing, -1
Conference Title: The 18th Annual International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2012
Pub Type: Conferences
Hash modes, indifferentiability