<p>You don't specify how long $m_1$ and $m_2$ are. If $|m_1| = |m_2| &gt; 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$). </p>

<p>Or are you asking to find <em>any</em> 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$.</p>

CC BY-SA 3.0
2011-08-29T19:22:05.433Z
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$.
Cyker
CC BY-SA 3.0
2011-08-02T03:15:14.720Z
2011-08-02T03:15:14.720Z
user6584
<p>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.?</p>

CC BY-SA 3.0
2011-07-20T10:32:42.060Z
Most schemes obey the [MD construction](http://en.wikipedia.org/wiki/Merkle%E2%80%93Damg%C3%A5rd_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.)
Sadeq Dousti
<cr.crypto-security>
Recovery of preimage of hash function given part of it
Cyker
# Recovery of preimage of hash function given part of it

(Asked by: username_0 on 2011-07-20)

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.?

**Tags:** cr.crypto-security

> **Comments:**
> **username_1**: Most schemes obey the [MD construction](http://en.wikipedia.org/wiki/Merkle%E2%80%93Damg%C3%A5rd_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.)  

---

## 1 answers

### Answer by username_2 on 2011-08-02. Score: 3 | Accepted answer

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$.

> **Comments:**
> **username_0**: 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$.  

---

