# Finding collisions in SHA1

I am trying to find two collisions in SHA1 for the 50 least significant bits. I was wondering if there was a way to efficiently do this without having to brute force all of the possible hash outputs?

It seems like trying to look for two same hash outputs is easier than trying to find a message that hashes and matches to a hash output I already have. (i.e. trying to break preimage resistance rather than second preimage resistance) But this still seems like I would need to brute force all the possibilities

• how many supercomputers do you have? – Richie Frame Feb 17 '16 at 4:18
• @RichieFrame: actually, I'd expect a search for a 50 bit collision to take a few seconds on a laptop... – poncho Feb 17 '16 at 4:24
• @poncho for brute force yes, but to do it "efficiently" without brute force will probably take a crap load of memory – Richie Frame Feb 17 '16 at 6:48

With 50 bits, you expect to have to hash around $2^{25}$ values, or about 30 million or so; if you're unlucky, you might run into 50 or 100 million before hitting a collision. That many entries easily fits into memory, and so this works out fairly well.