Partial collision for Reduced SHA1 hash

Question

i am doing a project to find two different sentence which give partial collision based on reduced sha1 hashing. My program will generate two different message. If the first 32bit of the hashing of the two sentence matches, the program will stop else it will repeat till collision is detected.

My program is working well, however the time take to search for collission is to slow. How can i speed iot up. I read up and found out that i can use birthday paradox, how do i implement that?

I did some search and get related answer however i am still confused on birthday paradox.

Probability of SHA1 collisions

SHA1 collision demo / example

http://www.metzdowd.com/pipermail/cryptography/2004-August/007409.html

http://www.freelists.org/post/hashcash/Hashcash-and-the-cracking-of-SHA1,2

This is how my program work:

Generate random number() // let say i generate 100 number
Generate random char1() // we will generate 100 char
Hash() // the first 100 char  
Generate random char2() // we will generate another 100 char
Hash2() // this 100 char again
Get the 32 bit of the random char1()
Get the 32 bit of the random char2()
compare the 32 bit for partial collision 
If they dont match we will keep on doing until partial collision is found.

• The time taken for the searching is too long compared to some other program which can find in millisecond.

Answer 1

If you're looking for partial collisions in a hash function by trying a random pair of inputs each time you're going to have to accept extremely long runtimes. For 32 bits and a perfect hash function that's a 1/(2^32) chance of a collision.

To exploit the birthday paradox you need to store the hashes you've generated and check the new hash against them all. This works because you're looking for a collision, you don't really care about what generated the hashes that eventually collided. Read up on how the birthday paradox works using humans and birthdays and make sure you understand that before applying it to hashing. By the math here you only need ~77,000 hashes to have a 50% chance of finding a collision amongst them for 32 bits.