Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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 stackoverflow.com Jun 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? –  Maarten Bodewes - 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
1  
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

2 Answers 2

up vote 4 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 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.

share|improve this answer

Your Answer

 
discard

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.