2

An accepted way of combining two hashes from different objects is to use XOR. This makes sense, but as mentioned in the second comment by Thomas Pornin in the below post, XOR is commutative, which means that if you hash each element in a set and combine them with XOR, any order that you do it will always result in the same hash:

Why is XOR the default way to combine hashes?

What is a good way to combine hashes that you want to be order dependent? If it is specific to the size, what are some known techniques for 32 bit and for 64 bit?

Community
  • 1
  • 1
Trevor Sundberg
  • 1,584
  • 1
  • 14
  • 25
  • Side note, in a particular case I have an iteration variable 'i' going from 0 to the number of elements. Is there a good way to use 'i' to make an order dependent hash? – Trevor Sundberg Apr 12 '12 at 16:49
  • If you want to impose order, you could rotate (*not* shift) the partial hashes before xoring them into the aggregate. This if course can cause collisions (such as H(ABCD) == H(DABC)), but that's a part of the game... – wildplasser Apr 12 '12 at 17:59
  • Right now I'm doing something silly where I multiply 'i' by a huge prime, and xor that with the hash for every element. It does impose order, but I'm definitely no expert and I have no idea if that would cause any major collisions. – Trevor Sundberg Apr 12 '12 at 18:54
  • 1
    Multiplying each position by its own private prime is also a possibility. Very similar to Zobrist hashing. (BTW: you can *never* avoid collisions; you'd need at least as many bits in your hash than in the sum of the contibuting objects) – wildplasser Apr 12 '12 at 19:00
  • It's not that I want to avoid collisions entirely, so much as I want to avoid doing things that wildly increase the number of collisions :P – Trevor Sundberg Apr 12 '12 at 23:36

1 Answers1

1

To make the resulting hash order dependent, there has to be some sequential (i.e. non-static) aspect in the algorithm. The most common technique probably is that of Cyclic Redundancy Checks (CRC).

CRC can be implemented in hardware as a shift-register with XOR-ed feedback. Such a shift-register acts as deterministic random number generator. Provided the initial state is the same, it will always go through the same sequence of states. These states are used in CRC signature computation to XOR the data in a repeatable fashion.

To combine two hash values, you'd XOR them together with a third value from a CRC algorithm. This might be calculated or taken from a look-up table.-

Popular CRC codes:

09 bits (CRC-8)
17 bits (CRC-16)
33 bits (CRC-32)
65 bits (CRC-64)

Classless.Hasher provides more details.

C# implementations can be found in HashLib.

Axel Kemper
  • 10,544
  • 2
  • 31
  • 54