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 this webpage from the National Center for Biotechnology Information.

• It'll take me some time to understand (and perhaps implement) these answers. I don't know enough to accept either answer at the moment. I appreciate your replies, fgrieu and cygnusv! Mar 25, 2015 at 22:11

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<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.

• Very interesting :) How does $\pi$ come up? Mar 25, 2015 at 10:07
• @cygnusv: I have used $\pi$ to come up with a nothing-up-my-sleeves prime $p$. Any irrational mathematical constant will do, with some adjustments to the integers in the expression of $p$.
– fgrieu
Mar 25, 2015 at 10:25

It seems to me that you don't need a cryptographic hash function, that is, a function that provides preimage resistance, collision resistance, etc. or at least to the degree that cryptographic applications require.

Anyway, it seems that you could use a hash function that follows the Merkle-Damgard construction, but without doing the length padding at the end. Note that this is completely unsecure for cryptographic purposes.

This construction breaks the input into smaller pieces (e.g., characters of a string) and combines these pieces sequentially. Being sequential, it seems like a good candidate for you, since you want to compute the hash of the concatenation of two inputs.

For instance, the Java hashCode function for Strings follows this construction. The hash of string $s$ of lenght $n$ is:

$h(s)=\sum_{i=0}^{n-1}s_i \cdot 31^{n-1-i}$

Assuming you know the length of the original input (for example by attaching $n$ to the resulting hash), then you can combine two hashes easily. Assume the hash of string $z$ of lenght $m$ is:

$h(z)=\sum_{i=0}^{m-1}z_i \cdot 31^{m-1-i}$

Then it is easy to check that the hash of $s||z$ would be:

$h(s||z)=\sum_{i=0}^{m-1}s_i \cdot 31^{n+m-1-i} + \sum_{i=0}^{m-1}z_i \cdot 31^{m-1-i}$

$\qquad\quad= 31^m \cdot \sum_{i=0}^{m-1}s_i \cdot 31^{n-1-i} + \sum_{i=0}^{m-1}z_i \cdot 31^{m-1-i}$

$\qquad\quad= 31^m \cdot h(s) + h(z)$

Then, your "hash combining function" could be:

$g(h_1, h_2) = 31^{l_2}\cdot h_1 + h_2$

where $l_2$ is the length of the input of $h_2$.

• Is it $h(s)=\big(\sum_{i=0}^{n-1}s_i \cdot 31^{n-1-i}\big)\bmod 2^b$, for $b=32$? If so, we have a severe risk of collision after a mere $100,000$ strings of identical length. Also you need to somewhat embed $l_2$ into $h_2$.
– fgrieu
Mar 25, 2015 at 9:43
• Yes, that's true, although this solution could be modified for a larger output, for instance, 256 bits. One could reserve the first 32 bits for the embedding the length of the input, and the rest (224 bits) for the hash itself. Then, instead of the prime 31, we would use the prime 223, and the modulus would be $2^{224}$. Mar 25, 2015 at 10:01
• Right. Your solution becomes closer to mine, and simpler, which is a virtue; however it is more prone to collisions for messages differing by few bytes, in particular changing the two bytes 0100 to 00DF, 0101 to 00E0 etc, in any string, leaves its hash unchanged.
– fgrieu
Mar 25, 2015 at 10:23

A "sequence characteristic polynomial" with a fixed point to evaluate at, chosen at random, might be useful. IACR preprint 2008/357.

Consider the sequence as a set of pairs $(s_i, p_i)$ of nucleotides $s_i$ at position $p_i$. Let a bivariate polynomial $f(x, y) = \prod_i (1 + x s_i + y p_i)$ over integers. One might also consider a residue modulo proper low-degree polynomial.

Such a characteristic polynomial is natural for splitting/gluing sequences, maybe for keeping variants (contigs), and small "difference of sequences". In particular, it results in polynomials of a low degree for errors. Well, it does not easy fit the idea of simple hash combining yet.