# finding collision for truncated SHA1 hash output

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?

-
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
ok.thnks.do 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

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
sys.exit(0)
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 tct.py *** Collision found 2404582 and 3768367 real 0m8.963s user 0m8.328s sys 0m0.632s$ echo -n 2404582 | sha1sum
68534f44ba8eafe729342b51257becc45e17fa30  -
\$ echo -n 3768367 | sha1sum
68534f44bacea590eb1734194a66fdf2a65a1100  -

-
Is your indentation correct? Don't you need to indent the two lines after the if statement? –  CodesInChaos Oct 1 '14 at 10:54
@CodesInChaos Thanks, fixed. I had to hand-repair several lines when I pasted into this post but I missed those. Not sure why crypto.SE is behaving this way suddenly (normally it preserves indentation for me). –  Fixee Oct 1 '14 at 19:37
echo -n "06b2f82fd81b2c20" | sha1sum
e42d65afd2bc126a2e8e609257287084c43fc06a

echo -n "02c60cb75083ceef" | sha1sum
e42d65afd277988908c01bc539c9d71aff728322


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