1
$\begingroup$

Is hashing the individual items, and then XOR-ing the results together, a good way of uniquely hashing an arbitrary unordered set of items?

I am thinking of using hash-then-XOR since I want some sort of function that can compute the hash of a set incrementally: given the $H(S)$, I want to be able to calculate $H(S \cup \{x\})$ and $H(S \setminus \{x\})$ without knowing the elements of $S$. In my particular application it's assured that already existing elements will not be added to sets, and nonexisting elements will not be deleted from sets.

With hash-then-XOR, whenever an element is inserted or removed, its hash can simply be XORed onto the set hash, allowing identical sets formed by arbitrarily different series of insertions and removals to arrive at the same hash. This is due to XOR being commutative, associative, and its own inverse.

Is this sort of set hashing scheme secure, in the sense of preimage, collision, and second-preimage security? If not, can some other more secure scheme (perhaps hash-then-modular-addition?) have the same sort of incremental properties as hash-then-XOR? I am specifically asking for an incremental set hashing algorithm, where the hash can be updated as elements are removed and added to the set, without knowing the whole set. Schemes such as hashing a lexicographically sorted set won't work in this case.

$\endgroup$
  • $\begingroup$ a quick search for "hash unordered" will turn up crypto.stackexchange.com/questions/54544/…, which explains why this is a weak construction (i.e. given a sufficient set of hashes it is possible to find enough linearly independent hashes to be able to force collisions). Seems like a duplicate to me. $\endgroup$ – jadb Aug 21 '18 at 19:40
  • $\begingroup$ The answer there is unhelpful, as hashing the elements after sorting and concatenating them is not usable if you want to calculate the hash incrementally and independent of any insertion order. $\endgroup$ – ithisa Aug 21 '18 at 19:45
  • 1
    $\begingroup$ A solution for multisets will also work for sets $\endgroup$ – Future Security Aug 21 '18 at 19:53

Browse other questions tagged or ask your own question.