# Is it feasible to find n hashes that sum up to a given hash?

Consider two sets $$A=\{a_1,a_2,\cdots,a_n\}, B=\{b_1,b_2,\cdots,b_m\}$$;

We can calculate the hash sum of those sets:

$$HASHSUM(𝐴)=(ℎ𝑎𝑠ℎ(a_1)+ ℎ𝑎𝑠ℎ(𝑎_2)+\cdots +ℎ𝑎𝑠ℎ(𝑎_𝑛))$$ and $$HASHSUM(𝐵)=(ℎ𝑎𝑠ℎ(𝑏_1) + ℎ𝑎𝑠ℎ(𝑏_2)+ \cdots + ℎ𝑎𝑠ℎ(𝑏_𝑚)).$$

Is it possible that set $$𝐴$$ does not equal the set $$𝐵$$, yet $$HASHSUM(𝐴)=HASHSUM(𝐵)?$$ Specifically, if $$n$$ (not necessarily $$m$$) is a small number ($$<20$$).

• very similar question here: crypto.stackexchange.com/questions/55185/… Main difference is + instead of xor and small n. The other thread seems to suggest that for large m and n it is possible. It is not clear to me wether a large m alone is sufficient. – user599464 Aug 14 '19 at 20:01
• Are you really asking about existence or do you want a method to find $b_1,\dots,b_m$ given $a_1,\dots,a_n$? – yyyyyyy Aug 14 '19 at 20:15
• @yyyyyyy I want to know if an attacker practically will be able to find 𝑏1,…,𝑏𝑚 given 𝑎1,…,𝑎𝑛. Basically I want to use this to create identifiers for sets and I want to make sure there is no collusion. – user599464 Aug 14 '19 at 20:20
• Collision is inevitable. – kelalaka Aug 14 '19 at 20:27
• What domain is your hash function mapping to? Is it the (positive integers) where you consider the integer corresponding to an output bit pattern? In that case is the + operation modular (i.e., $\pmod {2^{256}}$) for SHA-256 for example or straight integer summation? – kodlu Aug 15 '19 at 1:29

## 1 Answer

Let the hash length be $$d$$. If we consider finite groups, like addition modulo $$2^d,$$ this problem is well understood. Fix $$k=n+m.$$ If the vectors are randomly generated and form a list of size roughly at least $$2^{d/k},$$ there exists a solution with constant probability bounded away from zero. This is because a list of size $$M$$ contains $$F:=\binom{M}{k}$$ subsets of size $$k,$$ and thus as $$\{a_1,\ldots,a_n,b_1,\ldots,b_m \}$$ ranges over these subsets the function $$f(a_1,\ldots,a_n,b_1,\ldots,b_m):=(a_1+ \cdots + a_n)-(b_1+\cdots+b_m)$$ hits $$F$$ pseudorandom points from $$\mathbb{Z}_{2^d}.$$

This is a $$F$$ balls into $$2^d$$ bins problem and if $$F\geq 2^d,$$ the probability that $$f$$ misses the bin corresponding to $$0 \in \{0,1\}^d$$ is roughly $$e^{-1}\approx 0.37.$$ Taking $$M=\Omega((n+m) 2^{d/(n+m)})$$ is enough here. However, finding the solution is computationally more expensive.

Wagner (see here ) has a recursive binary tree based algorithm for the $$k-$$ XOR problem $$x_1\oplus \cdots \oplus x_k=0 \qquad (1)$$ with $$k=2^s,$$ with time and memory complexity essentially $$O(k 2^{d/(1+s)}).$$ This algorithm can be applied with addition, and will solve your problem if $$k=n+m\geq d,$$ since a solution will exist in that case.

Here we have $$+$$ instead of $$\oplus,$$ which is not a problem since we can use $$-b_i'=2^n-b_i$$ and use addition throughout. The upshot is, you need $$F\geq d/(n+m).$$ So if $$d=256,$$ and $$n=20,$$ you need $$m\geq 236,$$ and you will have complexity $$O(k 2^{d/(s+1)}).$$

Note: For the integer case without modular reduction, this is equivalent to a knapsack problem for which, the best algorithms are of very high complexity. Even though your outputs are in $$[0,2^d-1]$$ addition means your target set is much bigger. I believe the best complexity for finding a solution (if it exists, no guarantees since there is no finite domain) would then be $$O(2^{(n+m)/4}),$$ memory and $$O(2^{(n+m)/2})$$ time, from memory (Shamir Schroeppel?).

• thanks a lot for the answer. Is there any other commutative operator that would make finding collisions harder? (multiplication?) – user599464 Aug 15 '19 at 20:19
• If the domain is finite (mod 2^n) , not really, since multiplication is a group operation. In addition any zero appearing in a product leads to a zero product increasing chances of a collision at zero. – kodlu Aug 15 '19 at 21:49
• over the integers, products are more "spread out" so yes. If the hash output is restricted to $[0,2^n-1]$ then balancing $m$'and $n$ increases probability of collision, compared to the unbalanced case. But if $n$ and hence $m$ are small the likelihood of collision will be small (you had said $n<20$. – kodlu Aug 15 '19 at 21:53