Suppose we truncate only 40 bits of sha1 hash output.hence it is insecure.how can we find two message as input which gives first 40 bits of hash as same value i.e we have to find collision for first 40 bits of hash output?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
locked by e-sushi♦ Dec 17 '15 at 0:50
This question exists because it has historical significance, but it is not considered a good, on-topic question for this site, so please do not use it as evidence that you can ask similar questions here. This question and its answers are frozen and cannot be changed. More info: help center.
Notice the first ten characters of the SHA1 hash match, indicating a 40-bit match. Other pairs are 0534164decf1166c, 06670357183cba13 and 0addd115537e4b39, 09a3cbdd0d00773b.
Note that I am hashing these hexadecimal strings in ASCII with no terminator. So the SHA1 hash is the hash of 16 ASCII bytes.
This was found with a brute force search. I arbitrarily picked 16 hexadecimal digits, generated them randomly, and computed the SHA1 hash of each one, storing them in a tree indexed by the first 40-bits of the hash. The code wasn't particularly efficient, and took about four seconds of CPU time to produce 8 matches.
Could be made slicker, but I was just typing the first thing off the top of my head. For longer prefixes, we'd want to start using van Oorschot-Wiener techniques.