Paper 2008/075

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

Jonathan J. Hoch and 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.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
hash functionscryptographic combinersindifferentiability
Contact author(s)
yaakov hoch @ weizmann ac il
2008-02-27: received
Short URL
Creative Commons Attribution


      author = {Jonathan J.  Hoch and Adi Shamir},
      title = {On the Strength of the Concatenated Hash Combiner when All the Hash Functions are Weak},
      howpublished = {Cryptology ePrint Archive, Paper 2008/075},
      year = {2008},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.