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 '19 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 '19 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 '19 at 20:20
  • $\begingroup$ Collision is inevitable. $\endgroup$ – kelalaka Aug 14 '19 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 '19 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?).

| improve this answer | |
$\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 '19 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 '19 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 '19 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.