Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)?

share|improve this question

migrated from Jun 29 '14 at 22:08

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

Are restrictions on $a$ and $b$ allowed (like a fixed size or such)? – Paŭlo Ebermann Jun 29 '14 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 '14 at 4:00
up vote 10 down vote accepted

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.

share|improve this answer
Probably the simplest collision-resistant answer to the question as currently worded! – fgrieu Jun 30 '14 at 10:00
Simple and sufficient for my beginner needs. – Mircea Ionica Jul 1 '14 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.

share|improve this answer

In general, any type of algebraic identity on $H(a,b)$ in terms of $H(a)$ and $H(b)$ opens up a number of potential attack vectors such as meeting in the middle that make the hash not cryptographically secure. You can look at why we are using triple DES instead of double DES. Therefore, standard cryptographic hash functions are unlikely to have such a property.

If you need hash functions in a not security sensitive way, there are possibilities, like Algebraic Signatures (which you can find with Google Scholar).

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.