Is the sum of hashes a suitable hash for sets?

Question

Let $H: X \rightarrow \{0, 1\}^b$ denote a cryptographically secure, $b$-bits hash function on a set $X$. Let $H^*: \mathbb{P}(X) \rightarrow \{0, 1\}^b$ be a function on the power set of $X$ defined by \begin{equation} H^*(\{x_1, \ldots, x_n\}) = \sum_i H(x_i) \end{equation} where the sum is intended as wrapping addition over $b$-bit integers.

I am wondering if $H^*$ is cryptographically secure on $\mathbb{P}(X)$.

I easily see that other aggregation mechanisms (such as XOR-ing all hashes together) are easily prone to collisions. I also see how, if the same element of $X$ could appear multiple times in the collection being hashed, one could build a collision by simple integer division. But, if all the elements of $X$ being hashed are distinct, I can’t easily see an attack on this construction.

Answer 1

Contrary to what other people say, this is actually (when modified slightly) fine. You seem interested in the problem of homomorphic hashing. Note that while fully homomorphic encryption refers to being (ring)-homomorphic, i.e. with respect to something like $(\mathbb{F}_2, +, \times)$, homomorphic hashing refers to being homomorphic with respect to the monoid $(\mathbb{P}(X), \cup)$, i.e. precisely your notion of homomorphism.

Anyway, constructions of homomorphic hashes have been known for quite a while. See this for a semi-recent discussion of things. Something almost exactly like your proposal actually is secure (it is called "LtHash", and dates back to the 90s). The "trick" here is that one hashes onto $\mathbb{Z}_q^n$ for $n$ large. One can then reduce the collision resistance of the hash to a standard lattice problem (the Short Integer Solution problem), which (when appropriately parameterized) is thought to be hard. Note that the setting of $n = 1$ (your actual case) is likely insecure though, at least without setting $q$ to be quite large.

Answer 2

Edit: I misinterpreted the algebraic domain, but the answer can be adapted, see below.

The complexities exhibited are exponential, but reduced, and in applications such as hash functions, LWE, LPN where similar structures are used, these reduced complexities are of interest.

$H^\star$ is definitely insecure. Like most attacks on hash functions you will generate random inputs looking for collisions. Here let's consider addition modulo $2^b-1,$ as you suggest.

If $n$ is small compared to $2^b,$ there are still shortcuts which reduce the complexity substantially. Here is an attack finding a collision on such a function. Given some desired hash output $H_0,$ assume we have a random set of $v=2^{b/n}$ hashes, of the form $$H^\star(\{x_{1,i},\ldots,x_{n,i}\}),\quad i=1,\ldots,v\quad(1).$$ Since here are $v^n=2^b$ possible $n-$sums of the form (1) these sums we have assembled will will hit your $H_0$ with constant probability since the hash target space has size $2^{b}.$

Explanation: We have a finite domain, and balls in bins process with $2^b$ possible inputs.

If $n=2$ this would essentially be the birthday problem with complexity $O(2^{b/2}).$ By reduction to the case when $n=2^s$ is a power of 2, Wagner gave an $$O(2^{b/(1+s)}=O(2^{b/(1+\lceil \log n\rceil)})$$ recursive solution for the case of XOR but this can be adapted to any finite group, including addition modulo $2^b-1.$ See also chapter 8 of the book Algorithmic Cryptanalysis by Antoine Joux.

Answer 3

As a illustration that $H^*$ is sizably less secure than a $b$-bit hash, I give a collision attack with $\mathcal O(2^{b/3})$ hashes and $\mathcal O(b\,2^{b/3})$ memory. For simplicity, assume $b$ is a multiple of $3$, and the addition in the computation of $H^*$ is carried modulo $2^b$.

• Choose an easily computable function $X(i)$ mapping integers $i$ to $x_i\in X$; we'll note $H_i$ for $H(X(i))$.
• Set a table $T$ to empty, that will holds pairs $(i,H_i)$ indexed for search according to key $H_i\bmod2^{b/3}$.
• Set a table $U$ to empty, that will holds triplets $(i,j,(H_i+H_j\bmod2^b)/2^{b/3})$ such that $H_i+H_j\bmod2^{b/3}=0$, indexed to detect triplets with the same third element.
• For increasing $i$
  • compute $H_i$
  • search for an $H_j$ already in table $T$ with key $(-H_i)\bmod2^{b/3}$
  • If none is found, enter $(i,H_i)$ in table $T$ (to conserve memory at the expense of a little more hashes: except if the number of entries with key $H_i\bmod2^{b/3}$ is already some small threshold, e.g. 3)
  • Otherwise, remove $(j,H_j)$ from table $T$ and enter $(i,j,(H_i+H_j\bmod2^b)/2^{b/3})$ in table $U$, while testing for collision with an entry already in $U$ having the same third element. In that exceptional case we have $H^*(\{X(i),X(j)\})$ colliding with that earlier and different $H^*(\{X(i'),X(j')\})$ already in $U$, and stop with that collision.

Each new entry in $U$ costs a small constant number of hashes, and since the value we want to collide is $2b/3$-bit, we need $\mathcal O(2^{b/3})$ hashes.

As the saying attributed to the NSA by Bruce Schneier goes: Attacks only get better; they never get worse, and I see room for improvement. Independently, the attack can be adapted to other moduli (like $2^b-1$ or the largest $b$-bit prime) at moderate extra cost.