3
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – user599464 Aug 14 at 20:01
  • $\begingroup$ 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$? $\endgroup$ – yyyyyyy Aug 14 at 20:15
  • $\begingroup$ @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. $\endgroup$ – user599464 Aug 14 at 20:20
  • $\begingroup$ Collision is inevitable. $\endgroup$ – kelalaka Aug 14 at 20:27
  • 1
    $\begingroup$ 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? $\endgroup$ – kodlu Aug 15 at 1:29
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ thanks a lot for the answer. Is there any other commutative operator that would make finding collisions harder? (multiplication?) $\endgroup$ – user599464 Aug 15 at 20:19
  • $\begingroup$ 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. $\endgroup$ – kodlu Aug 15 at 21:49
  • $\begingroup$ 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$. $\endgroup$ – kodlu Aug 15 at 21:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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