Suppose $m = m_1 \| m_2$ (concatenation, with $|m_1| = |m_2|$) and $h(m) = s$ (hash). Is it possible to recover the whole preimage $m$ in feasible time with non-negligible probability given $m_1$ (or $m_2$) and $s$? Is there such a guarantee that this can't be done theoretically or provided by concrete schemes such as SHA1/SHA256/SHA512, etc.?
4
$\begingroup$
$\endgroup$
-
2$\begingroup$ Most schemes obey the MD construction, in which a (conjectured) collision-intractable function is iteratively applied to the input. I think if you apply the same construct, you may be able to prove that even if m1 (or m2) is known, no feasible algorithm can find m with non-negligible probability. (Though I must admit that I haven't worked out the details of such proof.) $\endgroup$ – M.S. Dousti Jul 20 '11 at 10:32
3
$\begingroup$
$\endgroup$
You don't specify how long $m_1$ and $m_2$ are. If $|m_1| = |m_2| > s$, then there is no way to recover $m$ given $s=h(m)$ (or $m_1$ given $m_2$ and $s=h(m_1\|m_2$) simply because there are exponentially many solutions to the equation $h(X)=s$ (resp., $h(X \| m_2) = s$).
Or are you asking to find any solution, not necessarily the original one? Even in this case, the above property (namely, existence of multiple solutions) can be used to show that solving either of the stated problems is hard if $h$ is collision resistant. In fact, this remains true even if $|m_1|=|m_2|=s$.
-
$\begingroup$ OK. For simplicity we just assume $|m_1| = |m_2| = |s|$. And we need to find the original solution. As you said, there might be multiple solutions to $h(X\|m_2) = s$. But what I want is that there is only negligible chance to find the original $X = m_1$, given $h, m_2, s$. $\endgroup$ – Cyker Aug 29 '11 at 19:22
