OSDev.org

I am writing a ropes datatype for Python(see http://code.google.com/p/google-highly- ... ail?id=218).

I need to get a hashing algorithm for this. I would like to be able to compute the hash of the parent from the hashes of the children. This way, I could cache the hash and make hashing extremely efficient. I was just wondering if any of you know of a hash function with the unique property that the hash of a+b can be computed from just the hash of a and the hash of b.

Thanks.

I think hashes cannot be made composable, since one of their powers is that you cannot swap both halves and end up with the same hash (within reasonable likelyhood). You can try a checksum though, you can easily make them composable.

I think hashes cannot be made composable, since one of their powers is that you cannot swap both halves and end up with the same hash (within reasonable likelyhood)

Depends on what you expect of a hash. If you want that property, devise a hash that has it.

Of course I will not attempt to prove the difficulty of coming up with a different plaintext that has the same hash. In fact, if you can find two texts of equal length with the same hash, you can replace them in a larger text and get the same result. (which I think does not hold for the average cryptographic hash)

the hashing algorithm need not be symmetric:
for instance if we transform each byte and composite them:

(a[0] rol 0) operator (a[1] rol 1) operator (a[2] rol 2)
you get a hash where hash(a+b) != hash (b+a)

now if operator is associative for each bit, we can compose the hashes as follows, since rotates get a distributive property under these conditions:

hash(a[0..n]) = hash(a[0..x]) operator (hash(a[x+1..n]) rol x+1)

and for operator, you could use end-around-carry addition or bitwise exclusive or. Or in fact anything that computes bit[n] = f(bit[n], bit[n+1], .., bit[n+k]) for each bit (required for making rotates distributive), and where a op b = b op a

f.ex a 4-bit hash on the following:
1001 1100 1100 0101
results in
1001 op 1001 op 0011 op 1010
xored becomes 1001
carry-added becomes 0001

in halves:
1001 op 1001, 1100 op 1010
xor: 0000, 0110
adc: 0011, 0111
then before composing them we rotate the second ones by 2:
xor: 0000, 1001 -> 1001
adc: 0011, 1101 -> 0001
which is exactly what we computed previously.

and swapping two halves:
1001 1100 1100 0101
1100 0101 1001 1100
1100 op 1010 op 0110 op 1001
xor: 1001 (which is the same by chance: f.ex 0010 1010 0001 0101 does not generate the same hash when swapped)
adc: 0111 (which is indeed different)

you could find many more (obscure) combinations of operators that work this way. Exponent and modulus might be an interesting candidate.

of course candy's suggestion works as well: if you don't modify the input based on location, any associative operator will make the hash composable. Of course you will get the side effect that hash(a.b) does equal hash(b.a)

ok, i'll stop now.