Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose we truncate only 40 bits of sha1 hash output.hence it is 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?


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.

Just hash about 2^20 times, then you'll get one 40 bit prefix collision. – CodesInChaos Nov 4 '12 at 17:28
I know that.Do we really have to brute force on 2^20 or we can get collision in less than that?. – Cryptic Nov 4 '12 at 17:32
I don't think there is a faster way. But 2^20 SHA-1 invocations take less than a second. – CodesInChaos Nov 4 '12 at 17:34 u know any crypto library which we can use as an api and brute force rather than rewriting the algo. – Cryptic Nov 4 '12 at 17:46
can u give me any two messages which are colliding? – Cryptic Nov 4 '12 at 20:23
echo -n "06b2f82fd81b2c20" | sha1sum

echo -n "02c60cb75083ceef" | sha1sum

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.

+1 for posting your methodology without anyone asking for it. Also, wow, I would never guess you can get a collision that quickly for a 40bit only version of SHA1. – Marcin Nov 7 '12 at 22:33
Mind sharing your code? I wrote my own program to do this in Node.js, and if I wait several minutes it might just be able to crack seven characters. I would expect some performance loss versus C, but not that much. – Stuart P. Bentley Feb 14 '13 at 15:30
@StuartP.Bentley Doesn't your program search for preimages not collisions? A 40 bit prefix collision costs about as much to find as a 20 bit prefix preimage. – CodesInChaos Oct 1 '14 at 10:51
@CodesInChaos Right you are, the function David Schwartz describes looks for any partial keys that match, not a specific key. That explains the massive time disparity. – Stuart P. Bentley Oct 1 '14 at 11:01

python code:

import hashlib, sys

hashDict = {}  
total = 10000000

for i in xrange(1,total):
    hashd = hashlib.sha1(str(i)).hexdigest()
    relev = hashd[:10]
    if relev in hashDict:
        print " *** Collision found ", hashDict[relev], " and ", i
    hashDict[relev] = i

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.

$ time python
 *** Collision found  2404582  and  3768367

real    0m8.963s
user    0m8.328s
sys     0m0.632s

$ echo -n 2404582 | sha1sum
68534f44ba8eafe729342b51257becc45e17fa30  -
$ echo -n 3768367 | sha1sum
68534f44bacea590eb1734194a66fdf2a65a1100  -

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