# Question about second preimage resistance of hash function combiner

Let $\Pi=(Gen_1,H_1)$ and $\Pi=(Gen_2,H_2)$ be two hash functions. Define $(Gen, H)$ so that $Gen$ runs $Gen_1$ and $Gen_2$ obtaining $s_1$ and $s_2$ respectively. Then let $H^{s_1,s_2}(x)=H^{s_1}(x)\|H^{s_2}(x)$, is it second pre-image resistant if at least one of $H^{s_1}$ and $H^{s_2}$ is second pre-image resistant?

I have found the paper Multicollisions in iterated functions, application to cascaded constructions.by Antoine Joux and it showed that the hash function $H^{s_1,s_2}(x)$ is not secure. But does this approach work for every hash function?

• I can't understand the question. What does your notation $H^{s_1}(x)$ mean? Does it mean repeatedly applying $H$, $s_1$ times? If so, what does the notation $H^{s_1,s_2}(x)$ mean? What's $s_1$? I suggest editing the question to clarify.
– D.W.
Commented Sep 28, 2014 at 3:28
• @D.W.$s_1$ means the output of generator $Gen_1$ Commented Sep 28, 2014 at 16:28
• possible duplicate of Guarding against cryptanalytic breakthroughs: combining multiple hash functions
– D.W.
Commented Sep 28, 2014 at 16:48
• @D.W. Not exactly, I have read it. But it cannot solve my problem completely. Commented Sep 28, 2014 at 17:50

The answer you are looking for is that a pre-image/2nd pre-image attack on two combined hash functions is at least as difficult as an attack on the stronger of the two hash functions.

Take a look at Joux's paper on multi-collisions. There is a section on pre-image attacks for concatenated outputs. (I suggest reading the entire thing. It's one of those rare short, to the point, easy to read papers.)

The attack described in the paper has complexity of:

$n_g2^{{n_f}/2} + 2^{n_f} + 2^{n_g}$

For two hash functions of length $n_f$ bits and $n_g$ bits where $n_f \leq n_g$

• For second preimages I agree fully. For first preimages it depends on the precise definition you're using. Commented Sep 28, 2014 at 15:56
• @CodesInChaos how do you mean? Commented Sep 28, 2014 at 16:27
• A (1st) pre-image "attack on two combined hash functions" can be made to be "at least as difficult as an attack on the stronger of the two hash functions", but it is far from clear that the OP's combiner does so. $\;$
– user991
Commented Sep 28, 2014 at 16:37
• It's pretty obvious that collisions and second pre-images of the concatenation imply the same attack against both hashes and are at least as strong as the stronger. On the other hand, concatenating a pre-image resistant hash with the leading bits of the message is practically bad concerning "it's hard to recover the message from a hash", even if it might still fulfill some definitions of pre-image security. Commented Sep 28, 2014 at 16:52