1
$\begingroup$

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?

|improve this question
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – D.W. Sep 28 '14 at 3:28
  • $\begingroup$ @D.W.$s_1$ means the output of generator $Gen_1$ $\endgroup$ – CryptoLover Sep 28 '14 at 16:28
  • $\begingroup$ possible duplicate of Guarding against cryptanalytic breakthroughs: combining multiple hash functions $\endgroup$ – D.W. Sep 28 '14 at 16:48
  • $\begingroup$ @D.W. Not exactly, I have read it. But it cannot solve my problem completely. $\endgroup$ – CryptoLover Sep 28 '14 at 17:50
4
$\begingroup$

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$

|improve this answer
$\endgroup$
  • $\begingroup$ For second preimages I agree fully. For first preimages it depends on the precise definition you're using. $\endgroup$ – CodesInChaos Sep 28 '14 at 15:56
  • $\begingroup$ @CodesInChaos how do you mean? $\endgroup$ – user13741 Sep 28 '14 at 16:27
  • $\begingroup$ 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. $\;$ $\endgroup$ – user991 Sep 28 '14 at 16:37
  • $\begingroup$ 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. $\endgroup$ – CodesInChaos Sep 28 '14 at 16:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.