Paper 2011/630

Indifferentiability Security of the Fast Wide Pipe Hash: Breaking the Birthday Barrier

Dustin Moody, Souradyuti Paul, and Daniel Smith-Tone

Abstract

A hash function secure in the indifferentiability framework (TCC 2004) is able to resist all meaningful generic attacks. Such hash functions also play a crucial role in establishing the security of protocols that use them as random functions. To eliminate multi-collision type attacks on the MD mode (Crypto 1989), Lucks proposed widening the size of the internal state of hash functions. More specifically, he suggested that hash functions h:{0,1}*->{0,1}^n use underlying primitives of the form C:{0,1}^a -> {0,1}^{2n} (Asiacrypt 2005). The Fast Wide Pipe (FWP) hash mode was introduced by Nandi and Paul at Indocrypt 2010, as a faster variant of Lucks' Wide Pipe mode. Despite the higher speed, the proven indifferentiability bound of the FWP mode has so far been only up to the birthday barrier of n/2 bits. The main result of this paper is the improvement of the FWP bound to 2n/3 bits (up to an additive constant). The 2n/3-bit bound for FWP comes with two important implications. Many popular hash modes use primitives with a=2n, that is C:{0,1}^{2n}->{0,1}^{2n}. For this important case, the FWP becomes the _only_ mode to achieve indifferentiability security of more than n/2 bits; thus we solve a longstanding open problem. Secondly, among n-bit hash modes with a>2n, the FWP mode has the highest rate among all modes which have beyond-birthday-barrier security. To obtain the bound of 2n/3 bits, we follow the usual technique of constructing games with simulators, with certain BAD events to distinguish between the games. However, we introduce some novel ideas. In designing the BAD events, we used multi-collisions in addition to collisions. We also allowed the query-response graphs, maintained by the simulators, to grow for two phases every iteration, rather than just one phase. Finally, our carefully chosen set of sixteen BAD events establish an isomorphism of simulator graphs, from which the 2n/3-bit bound follows. We also provide evidence that extending the bound beyond 2n/3 bits may be possible if we allow the simulator-graph to grow for three (or more) phases every iteration. Another noteworthy feature of our proof -- that may be of independent interest -- is that we work with only three games rather than a long sequence games.

Note: The results of the paper are now compared with more modes (e.g. HAMSI) than before, and a few more references on related work were added after taking into account third-party comments and remarks.