# Cryptographically Secure Hash Algorithm with Very Specific Property

First of all, I apologize if this is a stupid question, but I don't have any background in cryptography.

I'm looking for a secure hash algorithm $H$ with the property $H(K_1+n)\oplus H(K_2+n)=H(K_1\oplus K_2 + n)$. Would it be feasible to implement a hash algorithm like this, and could a hash algorithm even be secure if it had this property? If not, would a hash algorithm with the property $H(K_1\oplus n)\oplus H(K_2 \oplus n)\oplus H(K_3\oplus n)=H(K_1\oplus K_2\oplus K_3\oplus n)$ be any better?

-
I believe the answer is no, as any hash function that has those properties would not exhibit the avalanche effect, and thus be insecure –  Richie Frame Aug 3 '14 at 0:46
As it has been told you it is not possible for a cryptographic hash function. Maybe you could check an other kind of family functions. –  ddddavidee Aug 3 '14 at 7:38
1. What exactly do the operators $\oplus$ and $+$ signify? Bitwise xor and string concatenation, or something else? 2. Are the $K_i$ values supposed to be of a fixed bit length, or do you want the relation to hold for inputs of any length? –  Henrick Hellström Aug 3 '14 at 9:05
Maybe you should back up and state why you are trying to construct a function with these properties? What are you hoping to achieve? If you are looking for a function which is transitive for some set of values and a shared constant, you might want to look at prime-modulus operations, eg. Diffie Hellman. –  Jeff-Inventor ChromeOS Aug 5 '14 at 9:55

No such function with either property would meet the requirements of a secure hash function; either of those properties would make it easy to find preimages, that is, given a value $H(x)$, you can find a value $y$ with $H(y) = H(x)$.

First off, I assume that $n$ is a constant for the hash function; if we were to assume that the first property holds for any $n$, then it is easy to see that the only function that has that property is $H(x)=0$ for all $x$.

To find a preimage of a function with the first property, we would compute the hashes:

$$H(1 + n)$$ $$H(2 + n)$$ $$H(4 + n)$$ $$H(8 + n)$$ $$...$$ $$H(2^k + n)$$

Then, when given a value $H(x)$, we use Gaussian Elimination to find a subset of the above list ${a, b, c, ..., z}$ with $H(a + n) \oplus H(b + n) \oplus H(c + n) \oplus ... \oplus H(z+n) = H(x)$ Then, because of the property, we know that $H(a \oplus b \oplus c \oplus ... \oplus z + n) = H(x)$.

With a function with the second property, it is only slightly trickier. In that case, we would compute the list:

$$H(1 + n) \oplus H(0 + n)$$ $$H(2 + n) \oplus H(0 + n)$$ $$H(4 + n) \oplus H(0 + n)$$ $$H(8 + n) \oplus H(0 + n)$$ $$...$$ $$H(2^k + n) \oplus H(0 + n)$$

and proceed as previously.

-

Assuming $\oplus$ denotes XOR and $+$ denotes concatenation, I believe your first requirement would imply that $H$ would be identical for all inputs of same length, which is obviously not secure.

The second requirement is better. It would be satisfied if $H$ was linear. I am not sure if the requirement implies $H$ has to be linear, but it does look like it.

A cryptographic hash is not secure if it is linear. So you are not going to find a secure cryptographic hash satisfying the criteria.

However if you could use a message authentication code instead of hash, then there are possibilities.

Bucket hashing is a MAC which is linear and is proven to be secure. It is also one of the fastest provably secure MACs.

-