0
$\begingroup$

I am searching for a hash function which has these attributes:

  • low Avalanche Effect, similiar files should get similiar outputs
  • low number of collisions (if I have 0*10000 in one file, and 0*99999 + 1 in another the hash should differ and should not collide to easily)

The use case is "bruteforcing" a file hashed by the function, so I give a input file of 0*10000 and then bruteforce the input file.

By reducing the avalanche effect I hope that I can speed up the process by analyzing the difference (fc5e038d38a57032085441e7fe7010b0 is the output hash of the original file and as my bruteforce gets near the original file the hash should have less and less difference like fc5e038d38a57032085441e7XXXXXXX)

Is this even mathematically possible? Wouldn't a hash with these properties lead to a ton of collisions especially when I bruteforce it?

$\endgroup$
  • $\begingroup$ The dots contradicts! $\endgroup$ – kelalaka May 17 at 0:01
1
$\begingroup$

Sure. The probability of collisions depends on:

  1. How your symbols in the messages are distributed: Do messages have particular structure? Do some elements occur more often than the others?
  2. How long the hash code is.
  3. The structure of the hash code algorithm itself: Does it produce some hash codes more often than the others?

If all symbols are equally distributed and algorithm produces hash codes that are also equally distributed, then collision depends only on the hash code length. If hash code length is 512 bits, then the collision probability (with above mentioned assumptions) is $2^{-512}$.

The simplest function that fits your requirements is following:

hash(M) = M mod 2^512

If fits your requirements fully. To calculate it, you only need the last 64 bytes of the message. It means it is extremely fast. And the collision rate is the same as that of SHA-512.

If it is extremely fast, why nobody uses it? Namely because of your requirements: If has no avalanche effect. Hash codes are used normally to detect changes in the message. If there is no avalanche effect, changes will not be detected (in my example changes will be detected only in the last 64 bytes of the message, not in the previous bytes). I'm wondering for what purpose would you use such hash code.

To brute-forcing: If you exclude the avalanche effect, it means you will use only small part of the message to create the hash code. This means that also an attacker will consider only a small part of the message to brute-force. Means, brute-forcing will pretty easy.

| improve this answer | |
$\endgroup$
  • $\begingroup$ thank you very much! $\endgroup$ – Altay Akkus May 17 at 11:09
  • $\begingroup$ but if it only needs the last 64 bytes of a message, wouldn't it collide with all files that have the same last 64 bytes? Let's say I have 1000 bytes of A, the hash function computes a hash for 64 As. But now I have input 100 bytes of B and 900 bytes of A and I would still get the same output? I think I am getting something wrong here :D $\endgroup$ – Altay Akkus May 17 at 11:13
  • $\begingroup$ @AltayAkkus: No, your getting it perfectly right :) But the same number of collisions happens for any other good hash function of the same length. Out of all 1000 byte messages, how many will give the same hash for SHA-512 (which is considered very good)? 2^(1000*8)/2^512 = 2^7488 = 10^2254. This is a huge number. Compare it the number of atoms in the Universe which is merely 10^86. So, for every hash code produced by SHA-512 there are 10^2254 messages of 1000 byte length that produce the same hash code... $\endgroup$ – mentallurg May 17 at 19:40
  • $\begingroup$ @AltayAkkus: ... For my function it is obvious, that there are many collisions. For SHA-512 it becomes clear only after calculation. Again, what is wrong here? Nothing. Except that you cannot use function without avalanche effect for check of message integrity. If there is no avalanche effect, it is easy to create another message that produces the same hash code. Where as for functions wit avalanche effect it is very hard to create another message that produces the same hash code, because in the worst case you have to try at least 2^512 different messages. $\endgroup$ – mentallurg May 17 at 19:45

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.