# collision resistance of a composed hash function

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!

• 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. Jul 23 '19 at 5:57
• @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)$... Jul 23 '19 at 11:54
• Or, are you asking "if we assume a random (or not deliberately malformed) $H$, how difficult would this be?" Jul 23 '19 at 22:18
• @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? Sep 2 '19 at 13:21

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.