[Resource Topic] 2008/075: On the Strength of the Concatenated Hash Combiner when All the Hash Functions are Weak

Welcome to the resource topic for 2008/075

On the Strength of the Concatenated Hash Combiner when All the Hash Functions are Weak

Authors: Jonathan J. Hoch, Adi Shamir


At Crypto 2004 Joux showed a novel attack against the concatenated hash combiner instantiated with \md iterated hash functions. His method of producing multicollisions in the \md design was the first in a recent line of generic attacks against the \md construction. In the same paper, Joux raised an open question concerning the strength of the concatenated hash combiner and asked whether his attack can be improved when the attacker can efficiently find collisions in both underlying compression functions. We solve this open problem by showing that even in the powerful adversarial scenario first introduced by Liskov (SAC 2006) in which the underlying compression functions can be fully inverted (which implies that collisions can be easily generated), collisions in the concatenated hash cannot be created using fewer than 2^{n/2} queries. We then expand this result to include the double pipe hash construction of Lucks from Asiacrypt 2005. One of the intermediate results is of interest on its own and provides the first streamable construction provably indifferentiable from a random oracle in this model.

ePrint: https://eprint.iacr.org/2008/075

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .