3
$\begingroup$

I'm wondering if there is any collision-resistant hash function $h^s(\cdot)$ satisfying that there is a fixed value $c$ such that, for each $s$, a value $x_s$ satisfying $h^s(x_s) = c$ is known. This would not contradict the collision-resistance property, nor preimage-resistance, but I have not been able to come up with any construction of this kind.

Does anyone know if this is possible, and if so, can point me to a particular construction?

Thanks


Some context...

I'm working on an exercise which asks to analyze the security of Merkle–Damgård transform when no $IV$ is used (or, equivalently, when it is set as the first block of the message). If a hash function like that I mention can be constructed, then I can build collisions on this construction.

$\endgroup$
3
$\begingroup$

Take any standard hash function family $\{h_s(\cdot)\}_s$, a point $c$ and a list of inputs $(x_s)_s$ and define $h'_s : x \mapsto h_s(x)$ if $x\neq x_s$, and $c$ otherwise. As you said, it does not contradict collision resistance or preimage resistance - in other words, you can prove that if $(h_s)_s$ is a family of (say) collision-resistant hash functions, then so is $(h'_s)_s$. If you have a collision on Merkle-Damgård applied to $(h'_s)_s$ without $IV$, then you are done. The existence of any collision-resistant hash function implies the existence of a hash with the properties you want, via this trivial method.

$\endgroup$
  • $\begingroup$ I see, thanks for the answer! this is very trivial of course, but I didn't see it. I worked on the collisions based on the existence of such hash function, but I saw a mistake in my argument. Now, I am convinced that this variation of MD is still collision-resistant, which can be seen by following an identical (if not the same) proof to the usual MD construction (because, where is the $IV$ used in this proof anyway? by working "backwards" any collision on MD can be turned into a collision of $h$). Anyway, thanks for the help! $\endgroup$ – Cristina Feb 8 '17 at 0:56
  • $\begingroup$ I've never looked at the detail of the MD construction, but there are several questions on crypto.stackexchange on the need for an IV in MD, see for example this and this. $\endgroup$ – Geoffroy Couteau Feb 8 '17 at 1:03
  • $\begingroup$ Thanks for the reference, I already took a look at all of them (and many resources outside crypto SE as well), but yeah, I think I'll stick to my conclusion. Again, thank you for the answer and comments. $\endgroup$ – Cristina Feb 8 '17 at 1:08

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.