Tell me more ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.
up vote -4 down vote favorite

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?

share|improve this question
1  
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

1 Answer

up vote 6 down vote 
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.

share|improve this answer
+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 at 15:30

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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