Hash function such that fx(hash(s1),hash(s2)) = hash(concat(s1,s2)) First, I'm not a mathematician, so I may express this question awkwardly. Feel free to chuckle.

I'm wondering if there exists a hash function h such that for given strings s1 and s2, and string s3=concat(s1,s2), the hashes of s1 and s2 may be combined with a "hash combining function" g to give the hash of s3. That is g(h(s1),h(s2)) = h(s3).

For example, the string length function (as h) and addition function (as g) illustrate the property I'm after (even though string length would be a terrible hash function). For s1="abc" and s2="1234", s3="abc1234", h(s1) = 3, h(s2) = 4, and h(s3) = g(h(s1),h(s2)) = 7.

Merkle trees are similar in spirit to what I seek, except that I'd like the the intermediate hashes to be equal to the hash of the concatenation of underlying data (rather than a hash of child hashes).

For my intended uses, it is imperative that the hash function have an extremely low collision probability (akin to md5 or the sha series).

For what it's worth, the idea I'm considering is whether such a hash could be used to refer uniquely to a segment in graph of DNA sequence. Initially, the contiguous segment would be merely the hash of the segment, such as chromosome 1. As more is learned about large-scale genome variation, the contiguous segment might be decomposed into concatenated constituent segments, each of which is hashed. Users would refer to variation in sequence using the hash as an identifier, regardless of whether the sequence was contiguous or a virtual assembly of constituents. In this way, the hash value would effectively refer to both a path through these segments as well as the actual sequence of the concatenated fragments. For an example of such segments, see http://www.ncbi.nlm.nih.gov/assembly/GCF_000001405.28.
I'll consider only a non-adversarial model for the requirement of a low collision probability; that is, we are considering naturally-occurring strings only (which implies they are of bounded size; I'll limit it to $2^{64}-1$ bits, over 2305 Petabyte). However I'll consider that we need to reliably detect strings that differ only in a small consecutive segment. Caveat: in the following, hash is thus not used in its default meaning in cryptography.



My (new) proposed $h(s)$ is $256$-bit ($32$ bytes), among which the first $64$ bits are the number of bits in $s$ (truncated to the lower $64$ bits); and the $192$ last bits are a $192$-bit Cyclic Redundancy Check (CRC) of $s$, that is as the coefficients of $s(x)\bmod p(x)$, where $s(x)$ is the binary polynomial with coefficients the bits of $s$, and $p(x)$ is a fixed $192$-bit primitive polynomial. Conversions from bitstring to integer or polynomial, and back, are big-endian (the last bit corresponds to the least significant bit of integer or constant term of polynomial).

We define $g(h_1,h_2)$ as follows:


from $h_1$ and $h_2$ we get the integers $l_1$ and $l_2$ as the first $64$ bits, and build the first $64$ bits of $g(h_1,h_2)$ as $l_1+l_2$;
from $h_1$ and $h_2$ we get the polynomials $m_1(x)$ and  $m_2(x)$ which coefficients are the last $192$ bits, and build the last $192$ bits of $g(h_1,h_2)$ as the coefficients of
$$m_1(x)\cdot x^{l_2}+m_2(x)\bmod p(x)$$


The desired $g(h(s_1),h(s_2))=h(s_1\|s_2)$ holds, and its computation is fast, independently of the length of the original strings, noticing that $x^{l_2}\bmod p(x)$ is quickly computed by pre-computing $q_j(x)=x^{2^j}\bmod p(x)$ for $0\le j&lt;64$, and multiplying modulo $p(x)$ those $q_j(x)$ corresponding to the bits set in $l_2$.

The hash of any bitstring $s$ of at most $192$ bits is its length $l$ (in binary over $64$ bits), followed by $192-l$ 0 bits, followed by $s$. For longer bitstrings, we can either use the definition, or use $g(h(s_1),h(s_2))=h(s_1\|s_2)$; both allow computing the hash of an arbitrary bitstring in time roughly proportional to its length.

A practical implementation of $h$ on a modern $64$-bit CPU can use a table of $2048$ pre-computed $192$-bit values ($8$ tables each $256$ entries each $3$ words of $64$ bits), and each additional $8$ bytes of $s$ will require only $8$ fetches of $3$-word entries, and few simple operations dominated by $24$ wordwise XOR. That's very fast.

It is trivial to make collisions, but that can not occur between bitstrings of different length, or which differ only in a small segment (of size no more than $192$ bits).

One suitable $p(x)$ is $x^{192}+x^{149}+x^{97}+x^{46}+1$, taken from Jörg Arndt's Table of weight-5 binary primitive polynomials with (roughly) equally spaced coefficients. We might however want to use a random primitive polynomial, which gives even better insurance that no collision occurs between naturally occurring strings (argument: with neither knowledge of the polynomial nor example hashes, it is computationally impossible to find distinct strings with sizable odds of hash collision).



My original (and in retrospect overly complex) proposed $h(s)$ is $256$-bit ($32$ bytes), among which the first $64$ bits are the number of bits in $s$, and the $192$ last bits are $2^s\bmod p$, where $p$ is a fixed $192$-bit prime such that $(p-1)/2$ is prime and $2^{(p-1)/2}\bmod p=p-1$.

Because $2^s\bmod p=2^{s\bmod(p-1)}\bmod p$, we can compute the hash of a string in time about proportional to its length, by first reducing $s$ modulo $p-1$.

We define $g(h_1,h_2)$ as follows:


from $h_1$ and $h_2$ we get the integers $l_1$ and $l_2$ as the first $64$ bits, and build the first $64$ bits of $g(h_1,h_2)$ as $l_1+l_2$;
from $h_1$ and $h_2$ we get the integers $m_1$ and $m_2$ as the last $192$ bits, and build the last $192$ bits of $g(h_1,h_2)$ as
$$m_1^{2^{l_2}\bmod(p-1)}\cdot m_2\bmod p$$


The desired $g(h(s_1),h(s_2))=h(s_1\|s_2)$ holds, and its computation is fast, independently of the length of the original strings.

A suitable choice of $p$ is $\lfloor325\cdot\pi\cdot2^{182}\rfloor+78356$, that is in hexadecimal ff41208fd469fe8cfdcfdb1b1a977095890fed10d7b6f8a3 (Note: $325$ was selected so that the leftmost byte of $p$ is FF, $78356$ is the lowest integer so that $p$ matches the other requirements).

Examples (with this choice of $p$)
The hash of the empty string is
0000000000000000000000000000000000000000000000000000000000000001
The hash of the one-byte string 00 is
0000000000000008000000000000000000000000000000000000000000000001
The hash of the one-byte string 4c is
0000000000000008000000000000000000000000000010000000000000000000
The hash of the one-byte string bf is
0000000000000008800000000000000000000000000000000000000000000000
The hash of the one-byte string c0 is
000000000000000800bedf702b960173023024e4e5688f6a76f012ef2849075d
The hash of the one-byte string c1 is
0000000000000008017dbee0572c02e6046049c9cad11ed4ede025de50920eba
The hash of the two-byte string c0c1 is
0000000000000010f4cf3a34057419042ee1a3d61690616770b8532f43255211

It is easy to find a collision, but it won't occur by accident, and only for strings of equal length. For example, the $24$-byte strings
000000000000000000000000000000000000000000000001 and
ff41208fd469fe8cfdcfdb1b1a977095890fed10d7b6f8a3 both hash to 
00000000000000C0000000000000000000000000000000000000000000000002.

The above has the property that it is slightly difficult to come up with a string having a given random value in the right part (first preimage resistance); that's the discrete log problem. By making $p$ much larger, or using a group derived from point addition on an elliptic curve of known order, we can make that very difficult. This is nice to have, but not useful in the context of the question.



The idea in that other answer as modified per this comment also works, but is prone to collisions for messages differing by few consecutive bytes, contrary to all the methods considered in the present answer.