3
$\begingroup$

I have been reading about SHA1 and SHA256 and how they actually hash a string of text to a unique hashed message. But what I dont understand is what makes them resistant to collisions.

Whats the best way to find a hash collision? What makes a hash algorithm resistant to collisions? If we find 1 collision because it has to be caused by a particular input, cant we just discount that SHA result as a possible candidate for a problematic hash and assume most other results will be fine?

Improve this question
$\endgroup$
2

1 Answer 1

Reset to default
5
$\begingroup$

Collisions will always happen because of the infinite sized input space and finite sized output space (the pigeonhole principle). So the goal is that collisions can not be found in any less time then simply trying random inputs until a collision is found - it's not possible to have a compressing hash function where collisions do not exist, they must exist and so we have to settle for making them hard to find instead.

What makes a hash algorithm resistant to collisions?

The first thing is actually the padding of the message. If this is not done, collisions are usually trivial to produce.

The output of the function for any input should be unpredictable. Any degree of predictability in the output can be used to search for collisions faster then brute force.

In the worst case, the hash is completely linear and collisions can be computed from a simple expression.

In the best case, the value of any particular bit in the hash output cannot be guessed with probability better then 50%.

The exact, specific, best way to produce a hash function that produces unpredictable outputs doesn't really have an exact answer. There are a variety of ways to attempt to predict the output of the function, such as linear and differential cryptanalysis for example. Hash functions are designed with these kinds of attacks in mind.

Ideally the authors of the function would determine what the best possible attack is, then simply configure the function parameters to be large enough to where the attack does not apply anymore. While it is hard to know what the best possible attack is, with the right design strategy you can ensure a high level of resistance against the known classes of attacks.

What is the best way to find a hash collision

This depends on the particular hash function in question.

  • If it is a non-cryptographic hash, there may exist a simple expression that will allow you to calculate collisions outright with no search effort required.
  • If it is SHA1 you are curious about, then you would want to read about the recent attacks on SHA1
  • If it is some other hash function, then you would need to locate some pre-existing research that analyzes it (or perform such analysis yourself if it is a construction of your own).

If we find 1 collision because it has to be caused by a particular input, cant we just discount that SHA result as a possible candidate for a problematic hash and assume most other results will be fine?

It's not really clear what you are asking: It sounds like you are testing some other hash function and wondering if, despite finding a collision, it's safe to "assume" it's not broken somehow and other collisions can't be found.

If that is the case, then no, it is not safe (or reasonable) to make that assumption. If the hash is padded correctly and has an sufficiently large output size, then you should never witness a collision for it. If you do, then other collisions will probably follow eventually (attacks get better, not worse).

Improve this answer
$\endgroup$
5
  • $\begingroup$ "compressing hash function" :Is it shown that a non compressing function hasn't any collisions ie. 2^n unique inputs always generate 2^n unique outputs if n <= block width? $\endgroup$
    – Paul Uszak
    Jun 23, 2017 at 1:11
  • 1
    $\begingroup$ @PaulUszak It's pretty simple: If output space <= input space, then collisions cannot be avoided; If output space >= input space, then it is possible to map each element of the input space to a unique element of the output space. If output space >= input space is the case, then the function is invertible in that each output is produced by exactly 1 input. Such a "hash function" might not even be one-way. $\endgroup$
    – Ella Rose
    Jun 23, 2017 at 1:36
  • $\begingroup$ I mean has someone published a proof that eg. 2^160 sequential inputs starting at 0 produces exactly 2^160 outputs from SHA-1? Is there perhaps a relationship to avalanche effect for this proof? Should I formally ask this? $\endgroup$
    – Paul Uszak
    Jun 23, 2017 at 1:57
  • $\begingroup$ @PaulUszak Regarding your Should I formally ask this? — Well, that paper/proof thingy reads like a valid question to me… so why not? After all, this is a Q&A site. ;) $\endgroup$
    – e-sushi
    Jun 23, 2017 at 2:17
  • 3
    $\begingroup$ @PaulUszak I have no idea offhand if someone has done so, and would agree with e-sushi that your question should probably be a question rather then a comment on an answer, as it would probably warrant an answer on it's own. But I doubt that SHA1 behaves that way (it would be surprising if it did) $\endgroup$
    – Ella Rose
    Jun 23, 2017 at 2:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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