8
$\begingroup$

Suppose I have a set of elements, with known hash (e.g. SHA-2). How can I calculate the hash of the set? With it I mean an unordered set, so the order of elements is undefined and shall not play any role in determining the hash of the set.

In theory any commutative operation applied to the hashes should be fine, but I have the strong feeling that XORing all of them together is quite unsafe. An attacker could add an element to the set to produce a hash collision, although finding an element with that wanted hash is as hard as breaking the hash of the whole set.

Anything better solution than the trivial one of sorting the elements into a list, calculating their hashes and then calculating the hash of the hash list?

I think Merkle trees can't help here if they are based on some sort of ordering of the elements.

$\endgroup$
8
$\begingroup$

A well known technique to form the hash of an unordered set given hashes of the elements, is to order the hashes lexicographically, concatenate them in this order, and hash the result. The order of the elements in the original set does not influence the result, and this demonstrably inherits the properties of the hash (collision-resistance, preimage resistance, security in the ROM). The reader is left to decides if this is the trivial one of sorting the elements. That has serious drawbacks: the hashes must be stored; this is not an online algorithm.

This would be fixed by XORing the hashes of the elements of the set, but (as conjectured in the question) this gives a weak hash. In particular, if the hash is $b$-bit, then after a little more than $b$ elements we likely can find $b$ hashes that are linearly independent (w.r.t. bitwise XOR), and then by XORing some of these hashes we can form any value desired; that's a first-preimage attack.


Update: Meir Maor's comment pointed this very relevant paper: Dwaine Clarke, Srinivas Devadas, Marten van Dijk, Blaise Gassend, G. Edward Suh, Incremental Multiset Hash Functions and Their Application to Memory Integrity Checking, in proceedings of AsiaCrypt 2013. It builds hash functions for multisets, and their results apply directly to sets, which are multisets with multiplicity restricted to $\{0,1\}$ .

Based on their MSet-Mu-Hash construction, the following works, requires no sorting, and can be computed with constant memory as the hashes of elements of the set are made available:

  • Choose a nothing-up-my-sleeves 2049-bit public prime $p$ with $(p-1)/2$ also prime, e.g. $p=\lfloor2^{2047}\pi+494382\rfloor$ ; we assume the discrete logarithm modulo $p$ is hard, about as much as breaking SHA-256 collision resistance.
  • Expand each given SHA-256 hash $H_i$ of an element of the set into a 2048-bit bitstring $S_i$, e.g. as $S_i=\operatorname{H}(H_i\|K_1)\|\operatorname{H}(H_i\|K_2)\|\operatorname{H}(H_i\|K_3)\|\operatorname{H}(H_i\|K_4)$ where $\operatorname{H}$ is SHA-512 and the four $K_j$ are short distinct public arbitrary constants.
  • Compute the product modulo $p$ of the $S_i$ (converted to integer per big-endian convention); this can be done jointly with the previous step. The product will be $1$ for the empty set.
  • Hash the product (converted to a 2056-bit string per big-endian convention) with SHA-256 in order to produce the final result.

Note: in order to avoid certain attacks in certain hypothetical proof-of-work protocols (see this) both when sorting or when using the modular multiplication combination, the one or two hashes used on top of the initial hash should be different (e.g. use a different initial constant).

$\endgroup$
  • $\begingroup$ Would hash-then-XOR be vulnerable to second-preimage attacks as well? $\endgroup$ – ithisa Aug 21 '18 at 19:47
  • $\begingroup$ @ithisa First-preimage attacks are strictly harder than second-preimage attacks. $\endgroup$ – Nicholas Pipitone Nov 27 '18 at 7:18

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.