4
$\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$
5
  • 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$ Aug 14, 2019 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, 2019 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$ Aug 14, 2019 at 20:20
  • $\begingroup$ Collision is inevitable. $\endgroup$
    – kelalaka
    Aug 14, 2019 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, 2019 at 1:29

1 Answer 1

3
$\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$
4
  • $\begingroup$ thanks a lot for the answer. Is there any other commutative operator that would make finding collisions harder? (multiplication?) $\endgroup$ Aug 15, 2019 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, 2019 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, 2019 at 21:53
  • $\begingroup$ What about EC points? An EC public key is just a big secret random number times a generator. So, sha256(obj[0])*G = p0. You can compute p0,p1,p2, and -p1. p0+p1+p2+-p1 = p0+p2 ... does this have the same problems as just adding or xor the hashes? I want to checksum a large set of database records, and subtract deleted records from the checksum. (garbage-collected blockchain, etc) $\endgroup$
    – Rob
    Feb 7, 2021 at 2:50

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.