1
$\begingroup$

Given a collision-resistant hash function $H(x)$, say SHA256, and I devise another hash function by $H'(x)=\sum^{m}_{1}H(x||i) \mod p$. The summation is defined on finite field of prime order $p$.

Is the new hash function $H'(x)$ still collision resistant? How hard is it to find a collision? Any advice would be greatly appreciated!

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ I don't think there's anything that can be said without stronger assumptions on $H$ than just collision resistance. In particular, even for $m=2$, it's easy to construct artificial $H$ (by tweaking an existing collision-resistant hash for a few inputs) that are collision resistant, but for which $H'$ has trivial collisions. $\endgroup$
    – Ilmari Karonen
    Commented Jul 23, 2019 at 5:57
  • 2
    $\begingroup$ @IlmariKaronen: I believe that's the answer: "$H'$ is not necessarily collision resistant because (assuming there exists a collision resistant hash function) we can devise an $H$ which is collision resistant, but $H'$ is not". Trivial example: assuming $H^*$ is a collision resistant hash function, define $H(x) = p \times H^*(x)$... $\endgroup$
    – poncho
    Commented Jul 23, 2019 at 11:54
  • $\begingroup$ Or, are you asking "if we assume a random (or not deliberately malformed) $H$, how difficult would this be?" $\endgroup$
    – poncho
    Commented Jul 23, 2019 at 22:18
  • $\begingroup$ @poncho, sorry for this very late reply. In my case, we could just assume $H$ to be sha256. Then how hard the $H'$ can be? $\endgroup$
    – aphasiayc
    Commented Sep 2, 2019 at 13:21

1 Answer 1

Reset to default
2
$\begingroup$

Counterexample [from poncho in comments]: let $H_0\colon \{0,1\}^* \to \{0,1\}^{256}$; then $H(x) := p \cdot H_0(x)$, where $H_0(x)$ is interpreted as an integer in little-endian, is obviously collision-resistant but $H'(x) := \sum H(\cdots) \bmod p$ is identically zero and therefore very much not collision-resistant no matter what goes in the ellipsis.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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