10
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Are restrictions on $a$ and $b$ allowed (like a fixed size or such)? $\endgroup$ – Paŭlo Ebermann Jun 29 '14 at 22:17
  • 1
    $\begingroup$ 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)$. $\endgroup$ – poncho Jun 30 '14 at 4:00
10
$\begingroup$

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.

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

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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