I'm searching Why the SHA-1 is collision resistance? Anybody could help me with the proof or say me where I can find this proof?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
There is no such proof, on the contrary it has been proven that SHA-1 does not possess the ideal 80 bit collision resistance. Rather it is down to around 61 bits of resistance, uncomfortably close to being practically exploitable, and even if no further weaknesses are found advances in computing power are almost guaranteed to make it reasonably practical within a decade or two.
This weakness is only to collision attacks, that is attacks where the attacker can construct two different data pieces that has the same hash value, and thereby break some security measure, in some use cases that is relevant and SHA-1 is therefore problematic, in other cases it isn't and we can afford to be a bit more relaxed about the use of SHA-1 as its pre-image resistance doesn't seem likely to drop to a critical level any time soon.
In any case though, for new applications you are best advised to avoid using SHA-1 and earlier, instead use for instance one of the SHA-2 functions.
As for the theoretical foundation, SHA-1 is a Merkle–Damgård construction, such a construction is proven to be a perfect hash given that the one-way compression function it is built on can give some similar guarantees. It was presumably for this reason that Merkle–Damgård constructions became popular, but ultimately it is the one-way compression function that is the critical part, the Merkle–Damgård proof only tells us that the much simpler container format is not borked. You can find loads of cryptanalysis reports for any popular hash function, but unless you are a pretty sharp mathematician with a lot of time to kill they are probably not going to be of any use to you.
Great question, I'd love to see more proofs as well. This is pretty cool:
This is a very easy to follow and interesting proof based on the Merkle-Damgard construction (used for SHA1) that if you have a collision resistance function for a short message -> you have a collision resistance function for long messages. (He does this by using the proof by contra positive, by showing that a collision on the big message implies a collision on the short message.)
He then goes on to create collision resistant functions for short messages.
I'm not sure if this completely solves what you're looking for, however it has a lot of easy to digest but detailed introductory information which should help get you on your way / supplement other material you might find.