4
$\begingroup$

Assuming I'm a bank which seeks for secure hash functions to use in the process of signing on digital contents.

I'd like to explain / prove why using each one of the following hash functions might be less secure than using SHA-1 (yes, I know SHA-1 no longer considered secure, but the question does consider it as one, or at least states "do not be less secure than sha-1").

  1. $h_{666}(m) = $ some new hash function with 666 bit long output.

  2. $h_{ib}(m)=h_{sha-1}(h_{md5}(m))$

  3. $h_{hm}(m)=h_{md5}(m) \oplus h_{sha-1}(m) \oplus h_{ib}(m) \oplus h_{666}(m)$, while the XORing operation here xors the matching bits between two outputs, padding with 0s the smaller ones.

I would say…

  1. I can tell that using new hash function is a bad idea since no one has yet to research and attack it, aside from the fact that more bits is less efficient. Apart from this explanation, I don't see other reason to disqualify this answer.

  2. md5 is broken and collisions can be made quite easy, so two different inputs to this function can collide and have the same input to the sha-1 function, which will result in collision between the final outputs.

  3. I have no clue how to disqualify this one. The intuition says 'xoring with bad hash functions is not a good idea', but I can't really justify my answer. I also think the padding doesn't actually affect anything, becuase if SHA-1 result is secure then padding 0s to it won't make it collide with other inputs suddenly.

Am I correct, or did I miss something obvious somewhere?

Edit

This is different from “Guarding against cryptanalytic breakthroughs: combining multiple hash functions” since here the idea is to combine unsecure hash with a secure one. This is not about just combining hashes.

$\endgroup$
  • 2
    $\begingroup$ There are various hash function combiners, but none of them preserve all the security properties, so if you go that route you need to know which security properties you need and choose an appropriate combiner. For example concatenation offers collision and second pre-image resistance, but not first pre-image resistance nor is the output indistinguishable from random. But I'd recommend using a single strong hash function (e.g. SHA-2 or SHA-3). $\endgroup$ – CodesInChaos May 29 '16 at 15:05
  • $\begingroup$ The last one is trivially broken for $h_{666} = h_{md5}(m) \oplus h_{sha-1}(m) \oplus h_{in}(m)$ $\endgroup$ – CodesInChaos May 29 '16 at 15:07
  • $\begingroup$ @CodesInChaos $h_{666}$ is unknown, I don't think the exercise is to fix it to some specific value. Plus in your suggestion the output is not 666 bit long... $\endgroup$ – Jjang May 29 '16 at 16:41
  • 2
    $\begingroup$ Out of fairness: Could you please ask your professor / teaching assistent / whomever to no longer use this particular exercise in the future as the learning effect is now kinda gone (with two Qs here on crypto and a complete answer). $\endgroup$ – SEJPM May 30 '16 at 20:46
  • 1
    $\begingroup$ @SEJPM Don't worry. Those are extra exercises, so no grade is given for them. It's totally for me to deepen my knowledge. $\endgroup$ – Jjang May 31 '16 at 5:34
4
$\begingroup$

I can tell that using new hash function is a bad idea since no one has yet to research and attack it, aside from the fact that more bits is less efficient. Apart from this explanation, I don't see other reason to disqualify this answer.

That one is largely correct, although more bits doesn't have to mean "less-efficient" as for example Skein-512 turned out to be faster than Skein-256 during the designer's tests.

MD5 is broken and collisions can be made quite easy, so two different inputs to this function can collide and have the same input to the SHA-1 function, which will result in collision between the final outputs.

This one sounds good.

I have no clue how to disqualify this one. The intuition says 'xoring with bad hash functions is not a good idea', but I can't really justify my answer. I also think the padding doesn't actually affect anything, becuase if SHA-1 result is secure then padding 0s to it won't make it collide with other inputs suddenly.

This one is actually quite interesting. The property in question here is pseudorandomness of the output. If you zero-pad, the shorter hash functions don't have an effect on the higher bits, so MD5 will only enhance the first 128-bit, SHA-1 and $h_{ib}$ will only enhance the first 160 bits and the remaining 506 bits are up to $h_{666}$. Now if $h_{666}$ isn't pseudo-random, neither will this construction (likely) be, because you can distinguish the output from a random value using only the 500 high bits, which is obviously bad, as we already established that $h_{666}$ isn't exactly trust-worthy.

$\endgroup$
  • 2
    $\begingroup$ Longer hashes are "less efficient" in the sense that they take more storage space, which can be an important concern. OTOH of that's a problem you can usually just truncate them. $\endgroup$ – Tgr Jun 14 '17 at 19:58

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.