Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
I have a small number of hashes.
I would like to combine them into a single hash.
XORing the hashes ignores their order, which is important. Also, it could lead to a result of zero if there were an even number of identical items hashed.
Would rotating each hash (by a distance equal to the item's position) before XORing be secure?
First of all, if the order is not important then rotating a hash value depending on the order before using it would of course be counter-intuitive. Now the hash of a specific element is fully dependent on the order.
Generally I would not advice XOR-ing hashes.
Single rotation won't work especially if you combine multiple hashes - as you've indicated it would be easy to find a collision where two hashes cancel each other out. But you've already covered this.
XOR-ing would also make collisions easier to calculate, because the XOR of two hash values can also create a collision. Of course this won't change the order of finding a collision, but a XOR is still significantly faster than calculating a hash.
I could also imagine a scheme where you XOR (rotated) hashes that have a similar highest bit set. I think this could quickly create hashes that have the initial bits set to all zero. You could also XOR hashes that have a small Hamming distance. Either of these methods would create a set of hashes that have more than a normal amount of bits set to zero. It seems likely that these have less collision resistance than the initial hash. The fact that you can also use rotated hashes for this would make it even easier to create such attacks.
Instead you could think of sorting the hashes before you hash them (using a binary compare). That way you get a unique hash for a unique set where the order is ignored, even if it can contain identical elements. The disadvantage is that you cannot calculate a new hash value by adding a hash value after the final hash calculation is performed.
This can be viewed as a special case of the generalized birthday problem, as described by Wagner. Given $k$ lists of $n$-bit values, the problem is to choose one element from each list such that the $k$ chosen values xor to zero.
Note that rotations would not prevent this reduction, since the problem deals with arbitrary lists of values; they aren't required to be outputs of the same hash function. The only assumption is that the values are uniformly random.
Wagner describes an algorithm which takes $\mathcal{O}(k \cdot 2^{n / (1 + \log{k})})$ time, so we can treat that as an upper bound on the hardness of the problem, but faster algorithms may be possible.
