Associative standard cryptographic hash function

I am looking for a standard hash function which satisfies the following property:

A hash function $H(a,b) = F(h(a),h(b))$ with $h$ (within $F$) any standard cryptographic hash function and $F$ an associative function.

Is there any standard hash function(e.g. RIPEMD-160, SHA1) for which I can easily implement the associative function (like xor-ing or something similar)?

-

migrated from stackoverflow.comJun 29 at 22:08

This question came from our site for professional and enthusiast programmers.

I guess the mods are a bit busy, I've got quite a few flags pending, could you post this on crypto or indicate if the other Q/A answered your question? –  owlstead May 19 at 6:28
Are restrictions on $a$ and $b$ allowed (like a fixed size or such)? –  Paŭlo Ebermann Jun 29 at 22:17
Do you expect $H$ to be a cryptographical hash function, and in particular, have collision resistance? I ask, because if so, you'll need to take a lot of care in picking $F$; most of the associative functions we deal with in crypto are also commutitive at least much of the time; in this case, you want a function that hardly ever commutes; otherwise you can find $a, b$ with $H(a,b)=H(b,a)$. –  poncho Jun 30 at 4:00

One of the simplest associative functions that isn't commutative is concatenation:

$$H(a,b) = h(a) || h(b)$$

Yes, it doubles the output length, but it is as strong as $h$ against collisions. I offer this partly as a serious suggestion (it's simple) and partly to illustrate that your requirements are quite broad.

-
Probably the simplest collision-resistant answer to the question as currently worded! –  fgrieu Jun 30 at 10:00
Simple and sufficient for my beginner needs. –  Mircea Ionica Jul 1 at 9:05

If you don't need $H$ to be collision-resistant, you can use

$$H(a,b) = h(a) \times h(b) \bmod p$$

where $p$ is a large prime such that $p-1$ has a large divisor (and in particular, the discrete log problem modulo $p$ is hard), and with $h:\{0,1\}^* \to \mathbb{Z}/p\mathbb{Z}$ a hash function that outputs numbers in the range $[0,p-1]$.

If $h$ is a cryptographic-strength hash function, this will be one-way (preimage-resistant) in the random oracle model. As poncho explains, it won't be collision-resistant, because $H(a,b)=H(b,a)$.

You could also consider

$$H(a,b) = h_0(a) \times h_1(b) \bmod p$$

where $h_0,h_1$ are two separate cryptographic hash functions (e.g., $h_b(x) = h(b,x)$). This will be one-way and collision-resistant. I don't know whether it will meet your needs, though, because it's not exactly of the form you mention.

See also MuHash, as described here: Does collision resistance stay when extending a hash function to a set domain?

You might also consider a generalization of this that provides associativity but not commutativity. Let $\mathbb{G}$ be any non-commutative group. Then one candidate construction is

$$H(a,b) = h(a) \times h(b) \bmod p$$

where $h:\{0,1\}^* \to \mathbb{G}$ a hash function that outputs group elements.

This gives a candidate construction for each non-commutative group. Will it be secure? I don't know, but I expect that will depend upon $\mathbb{G}$. It seems plausible that with a suitable choice of $\mathbb{G}$, you might be able to design a hash function $H$ that is secure, i.e., one-way and collision-resistant (at least when we model $h$ as a random oracle).

I haven't tried to come up with a specific candidate, but one plausible choice might be letting $\mathbb{G}$ be a suitable set of $2 \times 2$ matrices over a some finite field $\mathbb{F}$, so that $\mathbb{G} = SL_2(\mathbb{F})$. See, e.g., hashing with SL2: Non-commutitive and nonassociative algebraic structures in cryptography for a related scheme. I haven't worked out all the details, but this might give you enough ideas to come up with a candidate scheme that meets all of your requirements.

-