Which fingerprinting/hashing algorithms support compounding?

Question

The definition of fingerprinting algorithms in Wikipedia describe a property called compounding as you can see here as:

Some fingerprinting algorithms allow the fingerprint of a composite file to be computed from the fingerprints of its constituent parts.

I suspect compounding is not a commonly used term for describing this capability. I have failed to find any other algorithm that allows

hash(x + y) = hash(x) + hash(y) 

Wikipedia is not always the most reliable source of information but the article for fingerprinting seems to imply that there are algorithms other than Rabin's fingerprinting method that support compounding. I'm probably not using the right terms for search but I could not find any.

So are there any hash functions (or fingerprinting algorithms) out there that supports this property?

Answer 1

This falls into a general class of hash functions known as homomorphic hash functions.

Your question is not entirely clear about what definition you are using for $+$. If you want the hash function to satisfy $h(x+y)=h(x)+h(y)$ where both instances of the $+$ operator refers to addition in a suitable group (e.g., addition of integers, xor), then such a hash is called linear. A CRC hash is an example of a linear hash function.

It's important to distinguish concatenation from addition. If you are looking for a hash that satisfies

$h(x||y) = h(x)+ h(y)$,

where $||$ denotes concatenation and $+$ denotes addition, then that's a different beast. I don't know of any standard name for it. This is a very restrictive property. Such hash function will always necessarily have the form

$h(x) = \sum_i h(x_i),$

where $x_i$ is the $i$th character of the string $x$. Consequently, the only way to achieve such a property is as follows: you choose some lookup table that maps from a single character to an integer; then you apply this to all the characters in the string and sum them up. Unfortunately, such a hash is less than ideal, as a hash function, as any two strings that have the same characters in a different will yield the same hash value. Thus if you use this as a hash function for a hash table, you might find an increased rate of collisions. However, it would be easy to construct such a hash function.

There are other generalizations. For instance, maybe you want a hash function with the property that

$h(x||y) = F(h(x), h(y))$

where $F$ is some associative function. There are standard constructions of such a hash. For instance, CRCs achieve this (though here $F$ depends on the length of $x$).

I suggest you also look at rolling hashes, the Rabin-karp rolling hash, Buzhash, AdHash, and MulHash. See also the following resources:

• https://crypto.stackexchange.com/q/17935/351

• https://crypto.stackexchange.com/q/11420/351

• the answers to https://crypto.stackexchange.com/q/1558/351

Answer 2

All the hash function mentioned below are not cryptographic hash function. This might give you an idea what I am talking.

If $+$ is addition, then you have very limited choices. As

hash(x + y) = hash(x) + hash(y) 

for all $x,y$ if and only if hash is a linear function.

If the first $+$ is concatenation, then Rabin–Karp string hashing is a good choice. Consider the following hash $h: \mathbb F^* \to \mathbb F$ ($\mathbb F$ should be a finite field) $$ h(x) = \sum_{i=1}^{|x|} x_i p^i $$ if $p\in\mathbb F$ is randomly chosen and $|x| \ll |\mathbb F|$, $h$ is a good hashing for same input length. For any $x,y \in \mathbb F^n$, $\Pr[h(x) = h(y)] \leq n/|\mathbb F|$. It's easy to find collision between inputs of different length. So you might want to pad the input length as part of the hash value. $$ \hat h(x) = (h(x),|x|) $$
As $h$ is linear, it's easy to compute hash of coord-wise addition, $$ h(x+y) = h(x) + h(y). $$ It's also easy to compute the hash of concatenation, $$ h(x \text{ concat } y) = h(x) + p^{|x|} h(y). $$

Answer 3

A parity bit and simple modular checksum have the property. If you know the length of the first, or maybe second, message then you can do so with CRCs even, but the polynomial division involved takes as long as redoing a checksum.

Any cryptographic or secure hash function should not allow this because it'd enable a combined replay and extension attack. And it'd leak considerable information about message contents.

If you need stranger hash function properties then you could ask cstheory perhaps.