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?

Thanks in advance for any comments.

  • $\begingroup$ I believe the answer is no, as any hash function that has those properties would not exhibit the avalanche effect, and thus be insecure $\endgroup$ – Richie Frame Aug 3 '14 at 0:46
  • $\begingroup$ 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. $\endgroup$ – ddddavidee Aug 3 '14 at 7:38
  • 1
    $\begingroup$ 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? $\endgroup$ – Henrick Hellström Aug 3 '14 at 9:05
  • $\begingroup$ 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. $\endgroup$ – 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.


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.